Processing math: 100%

المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی اول:دوره ی ۱۳:سوال ۳

سؤال ۳

می‌خواهیم هر نقطه موجود در دسته‌ی i+۱ وصل کنیم (i۳) به‌طوری‌ که هیچ دو نقطه‌ای از دسته‌ی iام به یک نقطه از دسته‌ی i+۱ام وصل نباشند. هم‌چنین می‌خواهیم هر نقطه موجود در دسته‌ی ۴ را با یک پاره‌خط به دقیقاً یک نقطه در دسته‌ی ۱ وصل کنیم به‌طوری‌که هیچ دو نقطه‌ای از دسته ۴ به یک نقطه از دسته‌ی اول وصل نباشند. به چند طریق می‌توان این کار را انجام داد؟

  1. 43×24×34
  2. 44×24×34
  3. 43×23×35
  4. 43×25×33
  5. 44×23×33

پاسخ

گزینه (۲) درست است.

در شکل مقابل مقصد هر یک از پاره‌خط‌های خارج شده از چهار نقطه به ترتیب به ۲٬۳٬۴ و ۱ طریق مشخص می‌شود که طبق اصل ضرب تعداد کل حالات برابر !۴ می‌شود. این موضوع از دسته ۲ به دسته ۳ و از دسته ۳ به دسته ۴ و نیز از دسته ۴ به دسته ۱ نیز به همین صورت است. بنابراین جواب مورد نظر (4!4) یا 44×34×24 می‌باشد.


ابزار صفحه