المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۶

قد ‎۸‎ دانش‌آموز به‌نام‌های ‎$J‎, ‎K‎, ‎L‎, ‎M‎, ‎N‎, ‎O‎, ‎P‎, ‎Q$‎ اندازه‌گیری شده است. می‌دانیم:

  • هیچ دو نفری هم‌قد نیستند.
  • قد ‎$J$‎ از قد ‎$K$‎ بلندتر نیست.
  • قد ‎$O$‎ از قد ‎$P$‎ بلندتر نیست.
  • قد ‎$L$‎ از ‎$M$‎ بلندتر و قد ‎$M$‎ از ‎$N$‎ بلندتر است.
  • قد ‎$N$‎ از ‎$Q$‎ بلندتر و قد ‎$Q$‎ از ‎$J$‎ بلندتر است.
  • $L$‎ تنها از بلندقدترین فرد کلاس کوتاه‌تر است.

چند ترتیب مختلف از نظر قد برای این دانش‌آموزان وجود دارد؟

  1. ۳۴
  2. ۳۵
  3. ۳۶
  4. ۳۸
  5. ۳۹

پاسخ

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

باتوجه به داده‌های مسئله ترتیب $LMNQJ$ به‌دست می‌آید٬ که قبل از $L$‎ باید فقط یک نفر قرار گیرد٬ اگر ‎$K$ قبل از $L$‎ باشد٬ آن‌گاه ترتیب افراد به شکل زیر٬ درمی‌آید:

$$KL\Box M\Box N \Box Q \Box J \Box$$

که اگر دو نفر $P$ و ‎$O$ پیش هم باشند٬ آن‌گاه یک خانه از مربع‌ها را انتخاب کرده و آن دو حرف را در آن‌جا قرار می‌دهیم(ابتدا $P$ و سپس ‎$O$)٬ که این کار به ۵ طریق ممکن است. اما اگر دو نفر $P$ و ‎$O$ پیش هم نباشند آن‌گاه دو خانه از مربع را به $\binom{5}{2}$؛ یعنی ۱۰ طریق انتخاب کرده و در اولی $P$ و در دومی ‎$O$ را قرار می‌دهیم.

اگر $P$ قبل از $L$‎ باشد٬ آن‌گاه ترتیب افراد به شکل زیر در می‌آید:

$$PL\Box M\Box N \Box Q \Box J \Box$$

که اگر دو نفر ‎$O$ و ‎$K$ پیش هم باشند٬ آن‌گاه یک خانه از مربع‌ها را انتخاب کرده و آن دو حرف را به $2!$ طریق در آن مربع قرار می‌دهیم( چون باید ‎$K$ قبل از ‎$J$‎ باشد٬ پس مربع آخر نمی‌تواند انتخاب شود)٬ این کار به $\binom{4}{1}\times2!$؛ یعنی ۸ طریق ممکن است. اما اگر دو نفر ‎$O$ و ‎$K$ پیش هم نباشند٬ آن‌گاه یکی از چهار مربع اول را انتخاب می‌کنیم و ‎$K$ را در آن قرار می‌دهیم و سپس یکی از چهار مربع باقی‌مانده را انتخاب کرده و ‎$O$ را در آن قرار می‌دهیم که این کار نیز به $4\times4$ طریق ممکن است. بنابراین تعداد کل حالات برابر $5+10+8+16$؛ یعنی ۳۹ خواهد شد.


ابزار صفحه