منو
 صفحه های تصادفی
تکنسین بررسی آفات و بیماری های گیاهی
چگونه امام علی را بشناسیم؟
پرکاری‌ تیرویید
ریک
حدیث ثقلین و عصمت
بافت نرده ای
نائینی
امام علی علیه السلام، برتر از پیامبران اولوالعزم
استخراج نفت
روابط ایران و عثمانی در دوره فتحعلیشاه
 کاربر Online
226 کاربر online

جایگشت های دوری

تازه کردن چاپ
علوم ریاضی > علو م رایانه
(cached)



این مطلب از بخش آموزش وب‌سایت المپیاد کامپیوتر رشد،انتخاب شده که با فرمت pdf نیز در وب‌سایت المپیاد رشدموجود می‌باشد. برای مشاهده این موضوعات در وب‌سایت المپیاد، به آدرس فهرست مطالب کامپیوتر مراجعه کنید. همچنین می‌توانید با کلیک اینجا‌ ، با ویژگی‌های بخش آموزش این وب‌سایت آشنا شوید.


جایگشت‌های دوری

مثال

به چند طریق 6 نفر می‌توانند دور یک میز دایره‌ای بنشینند؟ (دقت کنید که در آرایشی که با دوران هم دیگر به دست آیند را یکسان حساب می‌کنیم، به عنوان مثال اگر 6 نفر را، با نشان دهیم؛ آرایش شکل الف با آرایش شکل ب یکسان است ولی با آرایش شکل ج یکسان نیست)
img/daneshnameh_up/9/95/com0014a.jpg

حل
روش اول. در حال مسائلی که شرایطی را گذاشته‌اند سعی می‌کنیم، این شرایط را به نحوی برطرف کنیم تا به مسائل ساده‌ای که می‌توانیم حل کنیم، تبدیل شوند. به عنوان نمونه در این مثال، شرط مسأله یکسان بودن دوجایگشتی است که با دوران میز به یکدیگر تبدیل می‌شوند. چون میز را می‌توانیم دوران دهیم، پس می‌توان فرض کرد که همواره بالای میز می‌نشیند. با ثابت نگه‌داشتن جای ، شرط دوران از بین می‌رود. حال 5 نفر داریم که می‌خواهیم آنها را در 5 جای خالی بنشانیم و در مثال‌های قبل دیدیم که این کار را به طریق می‌توان انجام داد.
روش دوم. اگر شرط دوران را در نظر نگیریم، به حالت می‌توان این شش نفر را دور میز نشاند. ولی هر 6 جایگشت خطی معادل یک جایگشت دورانی می‌باشند، به عنوان مثال جایگشت‌های خطی ، همگی یک جایگشت دوری را مشخص می‌کنند. پس جواب مسأله برابر است با .
در این مثال، دو روش برای حل مسائل دوراین یادگرفتیم. روش اول از بین بردن شرط دوران با استفاده از ثابت نگه‌داشتن یک نفر و روش دوم تبدیل جایگشت دوری به جایگشت خطی. در ایده‌ی اول فردی که جای آن را ثابت نگه‌داشتیم هر یک از افراد می‌توانست باشد و انتخاب این فرد به عهدة ما می‌باشد.

مثال

به چند طریق می‌توان از بین 5 نفر، 3 نفر را دور یک میز دایره‌ای نشاند؟
حل.
از ایدة دوم استفاده می‌کنیم. اگر دوران را در نظر نگیریم، به طریق می‌توان سه نفر از بین پنج نفر را دور میز نشاند. ولی به دلیل دوران، هر حالت سه بار شمرده شده است، پس جواب برابر با می‌باشد.

نکته

به طریق مشابه می‌توان ثابت کرد که از بین نفر، نفر را به طریق می‌توان دور یک میز نشاند.

مثال

به چند طریق 7 نفر را می‌توان دور یک میز دایره‌ای 10 نفره، (میزی که 10 صندلی دارد) نشاند؟
حل.
راه حل اول. اگر این 7 نفر را با و صندلی‌ها را با نشان دهیم، می‌توان فرض کرد که روی صندلی نشسته است. (زیرا در غیر این صورت می‌توانیم با چرخاندن میز صندلی فرد را به صندلی تبدیل کنیم.) حال با نشستن شرط دوران از بین رفته است و حالا 6 نفر دیگر داریم که باید روی 9 صندلی خالی بنشینند. در قسمت‌های قبل یاد گرفتیم که این افراد به طریق می‌توانند این کار را انجام دهند. پس جواب برابر است با .
راه حل دوم. اگر دوران را در نظر نگیریم به طریق می‌توانیم این 7 نفر را دور میز بنشانیم و چون هر حالت را 10 بار شمرده‌ایم (زیرا با دوران می‌توانیم از هر حالت، 10 حالت بسازیم)، بنابراین جواب برابر است با: .

نکته

به طریق مشابه می‌توان ثابت کرد اگر بخواهیم نفر را دور یک میزگرد نفره ، بنشانیم؛ به طریق می‌توانیم این کار را بکنیم.

مثال

به چند طریق می‌توان با پنج‌مهرة به رنگ‌های قرمز، سفید، سبز، آبی و زرد یک گردن‌بند ساخت؟
حل
در ساخت گردن‌بند اگر نمی‌توانستیم آن را برگردانیم، جواب برابر با !4 بود. ولی دو جایگشت یک گردن‌بند را می‌سازند. (از برگرداندن یکدیگر به دست می‌آیند.) به طور مشابه چون هر حالت را دو بار شمرده‌ایم؛ جواب مسأله برابر است با .

نکته

به طور مشابه با مهرة مختلف، گردن‌بند متفاوت می‌توان ساخت.

مثال



به چند طریق 9 ریاضی‌دان و 7 فیزیک‌دان می‌توانند دوریک میز گرد بنشینند، به طوری که
الف.هیچ شرطی وجود نداشته باشد.
‌ب.فیزیک‌دان کنار ریاضی‌دان ننشسته باشد.
‌ج.‌هیچ دو فیزیک‌دانی کنار یکدیگر ننشینند.
‌د.همة فیزیک‌دان‌ها کنار یکدیگر نشسته باشند.

حل.
الف.-چون نفر داریم؛ جواب برابر است با.
ب. راه حل اول. ابتدا با نگه‌داشتن جای ریاضی‌دان شرط دوران را از بین می‌بریم. حال برای از بین بردن شرط کنار هم ننشستن و ، فیزیک‌دان را می‌نشانیم. فیزیک‌دان نمی‌تواند روی صندلی که ریاضی‌دان نشسته و دو صندلی مجاور آن بنشیند، بنابراین فیزیک‌دان بهطریق می‌تواند بنشیند. حال 14 نفر دیگر بهطریق می‌توانند روی صندلی‌های باقی مانده بنشینند. پس طبق اصل ضرب جواب برابر است با
دقت کنید در حل مسائلی که برای افراد یا اشیاء تعیین کرده‌اند، اول سعی کنید تا وضعیت آن افراد یا اشیاء را مشخص کنید تا شرط مسأله از بین برود تا بتوانید باقی مسأله را به راحتی حل کنید. به عنوان مثال، در این مثال ابتدا ریاضی‌دان و فیزیک‌دان را نشاندیم تا شرط کنار هم ننشستن و برطرف شود.
راه حل دوم (استفاده از اصل متمم). در این روش تعداد حالات مطلوب را از تفریق تعداد حالات نامطلوب از تعداد کل حالات به دست می‌آوریم. این روش حالت خاصی از اصل شمول و عدم شمول است که در فصل‌های آتی بررسی خواهد شد.
اگر شرط کنار هم ننشستن، و وجود نداشت به طریق این 16 نفر می‌توانستند دور میز بنشینند. اما ببینیم تعداد حالات نامطلوب چند تاست؟ حالاتی که و کنار هم نشسته باشند، نامطلوب است. برای شمردن تعداد این حالات و را یک فرد واحد مثل در نظر بگیرید؛
حال 15 نفر داریم که آنها را به طریق می‌توان دور میز نشاند ولی خود دو حالت دارد (سمت راست یا سمت چپ باشد.) بنابراین طبق اصل ضرب درحالت، و مجاور یکدیگرند. بنابراین تعداد حالات مطلوب برابر است با:
ج. ابتدا ریاضی‌دان‌ها را دور میز می‌نشانیم، به طریق می‌توان این کار را انجام داد. حال بین ریاضی‌دان‌ها 9 جا وجود دارد که باید فیزیک‌دان‌ها در 7 جا از آنها بنشینند. پس فیزیک‌دان‌ها هم به طریق می‌توانند بنشینند. پس طبق اصل ضرب جواب مسأله برابر است با .
د. تمام فیزیک‌دان‌ها را یک نفر مثلاً ، در نظر می‌گیریم. حالا 9 ریاضی‌دان و ، مثل 10 نفر هستند و آنها را به حالت می‌توانیم دور میز بنشانیم ولی خود فیزیک‌دان‌ها می‌توانند بهحالت کنار یکدیگر بنشینند. بنابراین جواب برابر است با: .

مثال

به چند طریق می‌توان زوج را دور یک میز گرد نشاند به طوری که:
الف.مردها و زن‌ها یک در میان بنشینند.
‌ب.مردها و زن‌ها یک در میان بنشینند و هر زنی نیز کنار همسر خود نشسته باشد.
حل.
الف. ابتدا مردها را به طریق دور میز می‌نشانیم. سپس بین هر دو مرد، یک زن می‌نشانیم که این کار بهطریق امکان دارد. پس طبق اصل ضرب، جواب مسأله برابر است با.
‌ب.ابتدا مردها را به طریق دور میز می‌نشانیم. حال برای نشستن همسر هر مرد، دو طریق وجود دارد. (سمت چپ یا سمت راست شوهر خود بنشینند). پس به طریق هم می‌توان زن‌ها را دور میز نشاند. در نتیجه جواب نهایی برابر است با .

پیوند های خارجی

http://Olympiad.roshd.ir/computer/content/pdf/0021.pdf




تعداد بازدید ها: 33280


ارسال توضیح جدید
الزامی
big grin confused جالب cry eek evil فریاد اخم خبر lol عصبانی mr green خنثی سوال razz redface rolleyes غمگین smile surprised twisted چشمک arrow



از پیوند [http://www.foo.com] یا [http://www.foo.com|شرح] برای پیوندها.
برچسب های HTML در داخل توضیحات مجاز نیستند و تمام نوشته ها ی بین علامت های > و < حذف خواهند شد..