تاریخچه ی:
سایر مسائل
تفاوت با نگارش: 1
| ||V{maketoc}|| | | ||V{maketoc}|| |
- | ||__~~navy:@#13::: این مطلب از بخش آموزش وبسایت المپیاد یی رشد،انتخاب شده که با فرمت pdf نیز در [http://olympiad.roshd.ir|وبسایت المپیاد رشد]موجود میباشد. برای مشاهده این موضوعات در وبسایت المپیاد، به آدرس [http://olympiad.roshd.ir/computercontentlist.html|فهرست مطالب کامپیوتر] مراجعه کنید. همچنین میتوانید با کلیک ((مطالب علمی سایت المپیاد رشد|اینجا)) ، با ویژگیهای بخش آموزش این وبسایت آشنا شوید.:: #@~~__|| |
+ | ||__~~navy:@#13::: این مطلب از بخش آموزش وبسایت المپیاد کمپیو رشد،انتخاب شده که با فرمت pdf نیز در [http://olympiad.roshd.ir|وبسایت المپیاد رشد]موجود میباشد. برای مشاهده این موضوعات در وبسایت المپیاد، به آدرس [http://olympiad.roshd.ir/computercontentlist.html|فهرست مطالب کامپیوتر] مراجعه کنید. همچنین میتوانید با کلیک ((مطالب علمی سایت المپیاد رشد|اینجا)) ، با ویژگیهای بخش آموزش این وبسایت آشنا شوید.:: #@~~__|| |
| ^@#16: | | ^@#16: |
| !سایر مسائل جایگشتها (تبدیلها) | | !سایر مسائل جایگشتها (تبدیلها) |
| !!مثال | | !!مثال |
| چند عدد از اعداد طبیعی 1 تا 1000 وجود دارند که ارقام تکراری دارند؟ | | چند عدد از اعداد طبیعی 1 تا 1000 وجود دارند که ارقام تکراری دارند؟ |
| __حل.__ | | __حل.__ |
| با استفاده از اصل متمم ، نخست تعداد اعداد طبیعی کوچکتر از 1000 که رقم تکراری ندارند را بدست آورده و از کل اعداد کم میکنیم. اما تعداد اعداد طبیعی کمتر از 1000 که رقم تکراری ندارند: | | با استفاده از اصل متمم ، نخست تعداد اعداد طبیعی کوچکتر از 1000 که رقم تکراری ندارند را بدست آورده و از کل اعداد کم میکنیم. اما تعداد اعداد طبیعی کمتر از 1000 که رقم تکراری ندارند: |
| •اعداد طبیعی یک رقمی بدون رقم تکراری: 9 | | •اعداد طبیعی یک رقمی بدون رقم تکراری: 9 |
- | •اعداد طبیعی دو رقمی بدون رقم تکراری: {TEX()} {9\times 9=81} {TEX} |
+ | •((اعداد طبیعی)) دو رقمی بدون رقم تکراری: {TEX()} {9\times 9=81} {TEX} |
| برای رقم دهگان 9 حالت داریم (اعداد 1 تا 9 بدون صفر) | | برای رقم دهگان 9 حالت داریم (اعداد 1 تا 9 بدون صفر) |
| و برای رقم یکان هم تنها عدد رقم دهگان را نمیتوان استفاده کرد یعنی 9 حالت داریم. | | و برای رقم یکان هم تنها عدد رقم دهگان را نمیتوان استفاده کرد یعنی 9 حالت داریم. |
| •اعداد طبیعی 3 رقمی بدون رقم تکراری: حالت{TEX()} {9\times 9\times 8=648} {TEX} | | •اعداد طبیعی 3 رقمی بدون رقم تکراری: حالت{TEX()} {9\times 9\times 8=648} {TEX} |
| مانند قبل صدگان نمیتواند صفر بنشیند (9 حالت) | | مانند قبل صدگان نمیتواند صفر بنشیند (9 حالت) |
| در دهگان تمام صفر تا نه بجز رقم صدگان میتوانند بنشینند (9 حالت) | | در دهگان تمام صفر تا نه بجز رقم صدگان میتوانند بنشینند (9 حالت) |
| و در یکان تمام صفر تا نه به جز رقم صدگان و دهگان میتوانند بنشینند (8 حالت) | | و در یکان تمام صفر تا نه به جز رقم صدگان و دهگان میتوانند بنشینند (8 حالت) |
| پس کلاً {TEX()} {648+81+9=738} {TEX}عدد کمتر از 1000 بدون رقم تکراری داریم، پس تعداد اعدادی که رقم تکراری دارند برابر است با: | | پس کلاً {TEX()} {648+81+9=738} {TEX}عدد کمتر از 1000 بدون رقم تکراری داریم، پس تعداد اعدادی که رقم تکراری دارند برابر است با: |
| @@{TEX()} {1000-738=262} {TEX}@@ | | @@{TEX()} {1000-738=262} {TEX}@@ |
- | در اینجا میبایست به تعمیم فاکتوریل نیز بپردازیم. |
+ | در اینجا میبایست به تعمیم ((فاکتوریل)) نیز بپردازیم. |
| --- | | --- |
| تعریف میکنیم {TEX()} {0!=1} {TEX} که اگر در فرمول تبدیل (جایگشت) به فاکتوریل صفر رسیدیم مشکلی نداشته باشیم. | | تعریف میکنیم {TEX()} {0!=1} {TEX} که اگر در فرمول تبدیل (جایگشت) به فاکتوریل صفر رسیدیم مشکلی نداشته باشیم. |
| !!مثال | | !!مثال |
| تعداد حالتهایی که میتوان نامهای شنبه، یکشنبه، دوشنبه، … ، پنجشنبه و جمعه را به روزهای هفته (7 روز) داد چندتا است. | | تعداد حالتهایی که میتوان نامهای شنبه، یکشنبه، دوشنبه، … ، پنجشنبه و جمعه را به روزهای هفته (7 روز) داد چندتا است. |
| __حل .__ | | __حل .__ |
| با استفاده از فرمول ترتیب داریم: | | با استفاده از فرمول ترتیب داریم: |
| @@{TEX()} {P_7^7=\frac{7!}{(7-7)!}=\frac{7!}{0!}=7!} {TEX}@@ | | @@{TEX()} {P_7^7=\frac{7!}{(7-7)!}=\frac{7!}{0!}=7!} {TEX}@@ |
| !نکته | | !نکته |
| برای یادآوری باید گفت که {TEX()} {P_m^n} {TEX} را به صورت {TEX()} { P (n , m) } {TEX} نیز نمایش میدهند: | | برای یادآوری باید گفت که {TEX()} {P_m^n} {TEX} را به صورت {TEX()} { P (n , m) } {TEX} نیز نمایش میدهند: |
| @@{TEX()} {P(n,m)=P_m^n=\frac{n!}{(n-m)!}} {TEX}@@ | | @@{TEX()} {P(n,m)=P_m^n=\frac{n!}{(n-m)!}} {TEX}@@ |
| !!مثال | | !!مثال |
| ثابت کنید | | ثابت کنید |
| __الف.__ {TEX()} { P(n , n) = P (n , n – 1) } {TEX} | | __الف.__ {TEX()} { P(n , n) = P (n , n – 1) } {TEX} |
| __ب.__ {TEX()} { P(n , 1) + P(m , 1) = P(n +m , 1) } {TEX} | | __ب.__ {TEX()} { P(n , 1) + P(m , 1) = P(n +m , 1) } {TEX} |
| __حل .__ | | __حل .__ |
| __ الف.__ | | __ الف.__ |
| @@{TEX()} {P(n,n)=\frac{n!}{(n-n)!}=\frac{n!}{0!}=n!} {TEX}@@ | | @@{TEX()} {P(n,n)=\frac{n!}{(n-n)!}=\frac{n!}{0!}=n!} {TEX}@@ |
| @@{TEX()} {P(n,n-1)=\frac{n!}{(n-(n-1))!}=\frac{n!}{1!}=n!} {TEX}@@ | | @@{TEX()} {P(n,n-1)=\frac{n!}{(n-(n-1))!}=\frac{n!}{1!}=n!} {TEX}@@ |
| @@{TEX()} {\Rightarrow \ P(n,n)=P(n,n-1)} {TEX}@@ | | @@{TEX()} {\Rightarrow \ P(n,n)=P(n,n-1)} {TEX}@@ |
| یا | | یا |
| @@{TEX()} {P_n^n=P_{n-1}^n} {TEX}@@ | | @@{TEX()} {P_n^n=P_{n-1}^n} {TEX}@@ |
| شهود این مطلب نیز به این صورت است که {TEX()} {P_{n-1}^n} {TEX} یعنی{TEX()} { n – 1} {TEX} نفر با لحاظ ترتیب از {TEX()} { n } {TEX} نفر انتخاب شوند، که تنها فرد باقیمانده تنها حالت برای انتخاب نفر بعد یعنی نفر{TEX()} { n } {TEX}ام است. پس به ازای هر حالت انتخاب با ترتیب {TEX()} { n – 1 } {TEX} نفر تنها یک حالت از انتخاب{TEX()} { n } {TEX} نفر داریم و بالعکس پس{TEX()} {P_{n-1}^n=P_n^n} {TEX} | | شهود این مطلب نیز به این صورت است که {TEX()} {P_{n-1}^n} {TEX} یعنی{TEX()} { n – 1} {TEX} نفر با لحاظ ترتیب از {TEX()} { n } {TEX} نفر انتخاب شوند، که تنها فرد باقیمانده تنها حالت برای انتخاب نفر بعد یعنی نفر{TEX()} { n } {TEX}ام است. پس به ازای هر حالت انتخاب با ترتیب {TEX()} { n – 1 } {TEX} نفر تنها یک حالت از انتخاب{TEX()} { n } {TEX} نفر داریم و بالعکس پس{TEX()} {P_{n-1}^n=P_n^n} {TEX} |
| __ ب.__ | | __ ب.__ |
| @@{TEX()} {P(n,1)=\frac{n!}{(n-1)!}=n \qquad , \qquad P(m,1)=\frac{m!}{(m-1)!}=m} {TEX}@@ | | @@{TEX()} {P(n,1)=\frac{n!}{(n-1)!}=n \qquad , \qquad P(m,1)=\frac{m!}{(m-1)!}=m} {TEX}@@ |
| @@{TEX()} {P(n+m,1)=\frac{(n+m)!}{(n+m-1)!}=n+m \Rightarrow \ P_1^n+P_1^m=P_1^{m+n}} {TEX}@@ | | @@{TEX()} {P(n+m,1)=\frac{(n+m)!}{(n+m-1)!}=n+m \Rightarrow \ P_1^n+P_1^m=P_1^{m+n}} {TEX}@@ |
- | و اما اکنون میخواهیم به مسالة جالب دیگری بپردازیم. |
+ | و اما اکنون میخواهیم به مساله جالب دیگری بپردازیم. |
| --- | | --- |
| !!مثال | | !!مثال |
| چند نوع تاسی داریم؟ (تاسی به مکعبی میگویند که وجههای آن از 1 تا 6 به گونهای شمارهگذاری شدهاند که مجموع اعداد وجوه مقابل عدد 7 بشود) | | چند نوع تاسی داریم؟ (تاسی به مکعبی میگویند که وجههای آن از 1 تا 6 به گونهای شمارهگذاری شدهاند که مجموع اعداد وجوه مقابل عدد 7 بشود) |
- | (دقت کنید تاسیهایی که از دوران یکدیگر در فضا بدست بیایند یکسان میباشند) |
+ | (دقت کنید تاسیهایی که از ((دوران)) یکدیگر در فضا بدست بیایند یکسان میباشند) |
| __راه حل 1 . __ | | __راه حل 1 . __ |
| تاسی را روی صفحه به صورت روبرو باز میکنیم واضح است که وجوه {TEX()} {A} {TEX}با {TEX()} {A^1} {TEX}و {TEX()} {B} {TEX}با {TEX()} {B^1} {TEX}و {TEX()} {C} {TEX}با {TEX()} {C^1} {TEX}مقابل میباشند. | | تاسی را روی صفحه به صورت روبرو باز میکنیم واضح است که وجوه {TEX()} {A} {TEX}با {TEX()} {A^1} {TEX}و {TEX()} {B} {TEX}با {TEX()} {B^1} {TEX}و {TEX()} {C} {TEX}با {TEX()} {C^1} {TEX}مقابل میباشند. |
| نخست بدون در نظر گرفتن دوران تاس تعداد کل حالات عدد دهی به این وجوه را میشماریم. | | نخست بدون در نظر گرفتن دوران تاس تعداد کل حالات عدد دهی به این وجوه را میشماریم. |
| چون سه جفت {TEX()} {(6,1)} {TEX} و {TEX()} {(4,3)} {TEX} و {TEX()} {(5,2)} {TEX} وجود دارند که مجموع 7 داشته باشند. پس برای اختصاص این اعداد به وجوه {TEX()} {C^1,\cdots ,A^1,A} {TEX} به تعداد {TEX()} {3!} {TEX} حالت انتخاب برای نسبت دادن جفتها به وجوه مقابل و برای هر دو وجه مقابل دو حالت داریم زیرا اگر به {TEX()} {A} {TEX}و {TEX()} {A^1} {TEX}،{TEX()} {(1,6)} {TEX}را نسبت دهیم دو حالت داریم: {TEX()} { A = 1 , A^1 =6 } {TEX}یا{TEX()} { A = 6 , A^1 = 1 } {TEX}پس در کل{TEX()} {3!\times 2^3} {TEX} حالت داریم. | | چون سه جفت {TEX()} {(6,1)} {TEX} و {TEX()} {(4,3)} {TEX} و {TEX()} {(5,2)} {TEX} وجود دارند که مجموع 7 داشته باشند. پس برای اختصاص این اعداد به وجوه {TEX()} {C^1,\cdots ,A^1,A} {TEX} به تعداد {TEX()} {3!} {TEX} حالت انتخاب برای نسبت دادن جفتها به وجوه مقابل و برای هر دو وجه مقابل دو حالت داریم زیرا اگر به {TEX()} {A} {TEX}و {TEX()} {A^1} {TEX}،{TEX()} {(1,6)} {TEX}را نسبت دهیم دو حالت داریم: {TEX()} { A = 1 , A^1 =6 } {TEX}یا{TEX()} { A = 6 , A^1 = 1 } {TEX}پس در کل{TEX()} {3!\times 2^3} {TEX} حالت داریم. |
- | حال تعداد حالات تکراریای که به ازای هر حالت شمردهایم را بدست میآوریم. اولاً به ازای هر آرایش بازکردن تاسی بر روی صفحة 6 انتخاب برای وجهی که مرکز بازکردن میباشد (در این مثال وجه {TEX()} {B} {TEX}) داریم، |
+ | حال تعداد حالات تکراریای که به ازای هر حالت شمردهایم را بدست میآوریم. اولاً به ازای هر آرایش بازکردن تاسی بر روی صفحه 6 انتخاب برای وجهی که مرکز بازکردن میباشد (در این مثال وجه {TEX()} {B} {TEX}) داریم، |
| و برای آنکه در کدام جهت آن وجه، دو وجه به هم متصل شده باشند ( در این مثال جهت بالا که وجوه {TEX()} {C^1} {TEX}و {TEX()} {B^1} {TEX}به هم وصلند) نیز چهار حالت داریم. | | و برای آنکه در کدام جهت آن وجه، دو وجه به هم متصل شده باشند ( در این مثال جهت بالا که وجوه {TEX()} {C^1} {TEX}و {TEX()} {B^1} {TEX}به هم وصلند) نیز چهار حالت داریم. |
| پس به ازای هر تاسی ما{TEX()} {6\times 4} {TEX} حالت یکسان را شمردهایم پس تعداد کل بدست آمده را تقسیم بر این تعداد کرده و داریم: | | پس به ازای هر تاسی ما{TEX()} {6\times 4} {TEX} حالت یکسان را شمردهایم پس تعداد کل بدست آمده را تقسیم بر این تعداد کرده و داریم: |
| @@{TEX()} {\frac{3!\times 2^3}{6\times 4}=2} {TEX}@@ | | @@{TEX()} {\frac{3!\times 2^3}{6\times 4}=2} {TEX}@@ |
| یعنی کلاً 2 نوع تاسی داریم. | | یعنی کلاً 2 نوع تاسی داریم. |
| __راه حل 2.__ | | __راه حل 2.__ |
| این راه که نیاز به درک فضاییِ خوبی دارد ، کوتاهتر و زیباتر است . اولاً میدانیم یکی از وجوه حتماً 1 است.پس تاسی را به قسمی روی میز میگذاریم که وجه 1 به زمین چسبیده و وجه 6 رو به بالا باشد: | | این راه که نیاز به درک فضاییِ خوبی دارد ، کوتاهتر و زیباتر است . اولاً میدانیم یکی از وجوه حتماً 1 است.پس تاسی را به قسمی روی میز میگذاریم که وجه 1 به زمین چسبیده و وجه 6 رو به بالا باشد: |
| حال میدانیم یکی از چهار وجه کناری حتماً 2 و مقابل آن 5 است. پس در همین وضعیت تاسی را در جهت حرکت ساعت آنقدر میچرخانیم تا وجه 2 روبروی ما قرار گیرد . | | حال میدانیم یکی از چهار وجه کناری حتماً 2 و مقابل آن 5 است. پس در همین وضعیت تاسی را در جهت حرکت ساعت آنقدر میچرخانیم تا وجه 2 روبروی ما قرار گیرد . |
| اکنون برای وجههای چپ و راست دو حالت داریم یا سمت راست 3 و چپ 4 باشد و یا بالعکس پس کل تعداد تاسهای ممکن به صورت زیر میباشد | | اکنون برای وجههای چپ و راست دو حالت داریم یا سمت راست 3 و چپ 4 باشد و یا بالعکس پس کل تعداد تاسهای ممکن به صورت زیر میباشد |
| --- | | --- |
| !!مثال | | !!مثال |
| به چند طریق میتوان چهار مرد و چهار زن را دور یک میز نشاند به قسمی که هیچ دومردی در دوصندلی مجاور قرار نگیرند؟! | | به چند طریق میتوان چهار مرد و چهار زن را دور یک میز نشاند به قسمی که هیچ دومردی در دوصندلی مجاور قرار نگیرند؟! |
| __راه حل 1.__ | | __راه حل 1.__ |
| فرض کنیم میزیک خط راست باشد، برای شروع از سمت چپ نخست دو حالت داریم که با مرد یا زن شروع شود و فرض کنیم سمت چپترین فرد مرد باشد | | فرض کنیم میزیک خط راست باشد، برای شروع از سمت چپ نخست دو حالت داریم که با مرد یا زن شروع شود و فرض کنیم سمت چپترین فرد مرد باشد |
- | اگر مربع نشاندهندة مرد و خط نشاندهندة زن باشد واضح است {TEX()} {4!} {TEX} برای مردها و{TEX()} {4!} {TEX} حالت برای زنها داریم. پس کلاً به{TEX()} {4!\times 4!\times 2} {TEX} حالت میتوانند در یک خط راست بنشینند. حال اگر ما این خط راست را به دایره تبدیل کنیم به ازای هر حالت 8 حالت تکراری داریم (چرا؟) پس کلاً {TEX()} {\frac{4!\times 4!\times 2}{8}=4!\times 3!} {TEX} حالت داریم. |
+ | اگر مربع نشاندهنده مرد و خط نشاندهنده زن باشد واضح است {TEX()} {4!} {TEX} برای مردها و{TEX()} {4!} {TEX} حالت برای زنها داریم. پس کلاً به{TEX()} {4!\times 4!\times 2} {TEX} حالت میتوانند در یک خط راست بنشینند. حال اگر ما این خط راست را به دایره تبدیل کنیم به ازای هر حالت 8 حالت تکراری داریم (چرا؟) پس کلاً {TEX()} {\frac{4!\times 4!\times 2}{8}=4!\times 3!} {TEX} حالت داریم. |
| __راه حل 2.__ | | __راه حل 2.__ |
- | اگر مرد شمارة 1 را در نظر بگیریم، میدانیم حتماً در یک جای دایره نشسته، دایره را آنقدر میچرخانیم تا مرد 1 به سمت چپ بیاید. |
+ | اگر مرد شماره 1 را در نظر بگیریم، میدانیم حتماً در یک جای دایره نشسته، دایره را آنقدر میچرخانیم تا مرد 1 به سمت چپ بیاید. |
| واضح است برای انتخاب 3 مرد دیگر{TEX()} {3!} {TEX} حالت و برای انتخاب محل نشستن چهار زن{TEX()} {4!} {TEX} حالت داریم پس کلاً {TEX()} {4!\times 3!} {TEX} حالت داریم. | | واضح است برای انتخاب 3 مرد دیگر{TEX()} {3!} {TEX} حالت و برای انتخاب محل نشستن چهار زن{TEX()} {4!} {TEX} حالت داریم پس کلاً {TEX()} {4!\times 3!} {TEX} حالت داریم. |
| --- | | --- |
| !!مثال | | !!مثال |
| 10 همکلاسی را در نظر بگیرید که دوتا از آنها به تازگی باهم قهر کردهاند! به چند طریق این 10 نفر می توانند دور یک میز دایرهای بنشینند به قسمی که دونفری که با هم قهر کردهاند کنار هم نباشند. | | 10 همکلاسی را در نظر بگیرید که دوتا از آنها به تازگی باهم قهر کردهاند! به چند طریق این 10 نفر می توانند دور یک میز دایرهای بنشینند به قسمی که دونفری که با هم قهر کردهاند کنار هم نباشند. |
| __حل.__ | | __حل.__ |
| تعداد حالاتی که این دو نفر کنار هم باشند را شمرده و از کل حالات کم میکنیم. | | تعداد حالاتی که این دو نفر کنار هم باشند را شمرده و از کل حالات کم میکنیم. |
| در حالاتی که این دو نفر کنار هم باشند، آن دو را یک بسته مینامیم و میدانیم این بسته و 8 نفر دیگر به{TEX()} {8!} {TEX} طریق میتوانند دور میز قرار گیرند حال در این بسته نیز 2 حالت داریم، یا نفر اول در سمت راست بنشیند یا نفر دوم آن بسته. پس کلاً به{TEX()} {2\times 8!} {TEX}حالت این دو نفر میتوانند کنار هم بنشینند پس تعداد طرقی که این 10 همکلاسی دورمیز میتوانند بنشینند که این دو کنار هم بناشند برابر است با: {TEX()} {10!-2\times 8!} {TEX} | | در حالاتی که این دو نفر کنار هم باشند، آن دو را یک بسته مینامیم و میدانیم این بسته و 8 نفر دیگر به{TEX()} {8!} {TEX} طریق میتوانند دور میز قرار گیرند حال در این بسته نیز 2 حالت داریم، یا نفر اول در سمت راست بنشیند یا نفر دوم آن بسته. پس کلاً به{TEX()} {2\times 8!} {TEX}حالت این دو نفر میتوانند کنار هم بنشینند پس تعداد طرقی که این 10 همکلاسی دورمیز میتوانند بنشینند که این دو کنار هم بناشند برابر است با: {TEX()} {10!-2\times 8!} {TEX} |
| --- | | --- |
| ! پیوند های خارجی | | ! پیوند های خارجی |
| [http://Olympiad.roshd.ir/computer/content/pdf/0022.pdf] | | [http://Olympiad.roshd.ir/computer/content/pdf/0022.pdf] |
- | |
+ | --- !همچنین ببینید *((جایگشت های دوری )) *((جایگشت ها و جایگشت های با تکرار )) |
| #@^ | | #@^ |