سوال ۷

هفت دیو با قدرت‌های $\langle 1, 5, 6, 8, 10, 12, 13 \rangle$ و هفت انسان با قدرت‌های $\langle 2, 3, 4, 7, 9, 11, 14 \rangle$ داریم. می‌دانیم در هر جنگ، هفت جفت انسان و دیو نبرد تن به تن می‌کنند و از هر جفت، فرد قدرتمندتر زنده می‌ماند. دو چینش در صورتی متمایزند که فردی وجود داشته باشد که رقیب او در این دو چینش متفاوت باشد. به ازای چند چینش اولیه، تعداد انسان‌هایی که زنده می‌مانند بیشترین مقدار ممکن است؟

  1. ۴۲۰
  2. ۱۴۴
  3. ۷۲
  4. ۱۰۸
  5. ۲۴

پاسخ

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

ابتدا ثابت می‌کنیم که در هر چینش، انسان‌ها حداقل ۲ کشته می‌دهند. افراد $\langle 2, 3, 4 \rangle$ تنها از یک دیو قدرت بیشتری دارند. پس در هر چینش حداقل دو نفر از آنها با افراد قوی‌تر از خود نبرد کرده و می‌میرند. حال به ۳ طریق فردی که از میان آن سه نفر زنده می‌ماند را انتخاب می‌کنیم و رقیب او را دیو اول (با قدرت ۱) قرار می‌دهیم. سپس به ۲ طریق رقیب انسان به قدرت ۷ را از میان $\langle 5, 6 \rangle$ انتخاب می کنیم و به طریق مشابه، به ۲ طریق از میان مجموعه‌ی $\langle 5, 6, 8 \rangle$ که یکی از اعضای آن به عنوان رقیب انسان قبلی انتخاب شده است رقیب انسان به قدرت ۹ را انتخاب می‌کنیم. این روند را ادامه می‌دهیم تا رقیب قوی‌‌ترین انسان نیز انتخاب شود. با این کار تنها تعیین رقیب‌های دو انسان کشته شده باقی می‌ماند که به ۲ طریق می‌توان دو دیو باقی مانده را برای رقیب‌های آن دو انتخاب کرد. در انتها تعداد حالات برابر $3 \times 2^3 \times 3 \times 2 = 144$ می‌شود.