المپدیا

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

ابزار کاربر

ابزار سایت


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

سؤال ۳۴

یک مکعب بزرگ $n× n× n$ را در نظر بگیرید. این مکعب را به $n^3$ مکعب واحد تقسیم کرده‌ایم. دو نفر این بازی را روی مکعب بزرگ انجام می‌دهند: هر نفر در نوبت خود یک مکعب مستطیل $ n× 1× 1 $ و $ 1 \times n \times 1$ یا $ 1× 1× n $از مکعب بزرگ ، که هیچ‌یک از مکعب‌های واحد آن رنگ نشده‌اند، را انتخاب کرده و مکعب‌های واحد آن را رنگ می‌کند. در ابتدا هیچ‌یک از مکعب‌های واحد رنگ نشده‌اند. هر کس نتواند در نوبت خود مکعب مستطیلی به شرح فوق انتخاب و رنگ کند بازنده خواهد بود. برای کدام‌یک از حالت‌های $n = ۱۰$, $n= ۱۱$, $n = ۱۲$ و $n = ۱۳$٬ نفر اول می‌تواند طوری بازی کند که حتماً برنده شود؟

  1. همه‌ی حالات
  2. هیچ‌یک از حالات
  3. حالاتِ $۱۱ = n $ و $۱۳ = n$
  4. حالتِ $۱۱ = n$
  5. حالاتِ $۱۰ = n $ و $۱۲ = n$

پاسخ

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

اگر $n$ فرد باشد٬ آن‌گاه سه مکعب با ابعاد ۱٬۱ و $n$ به صورت عمودی٬ طولی و عرضی در وسط مکعب وجود دارد که قرینه آن مکعب‌ها نسبت مرکز اصلی مکعب خود آن مکعب‌ها می‌شود. در بقیه حالت‌ها قرینه هر مکعب با ابعاد ۱٬۱ و $n$مکعب دیگری باهمین ابعاد می‌شود.بنابراین اگر $n$ زوج باشد٬ بازیکن دوم برنده می‌شود به این صورت که بازیکن اول هر حرکتی را انجام دهد او قرینه همان حرکت نسبت به مرکز اصلی مکعب را انجام می‌دهد و اگر $n$ فرد باشد٬ بازکن اول برنده می‌شود به این صورت که در ابتدا یکی از سه مکعب با ابعاد ۱٬۱ و $n$ که از مرکز مکعب می‌گذرد را بر‌می‌دارد و سپس بازیکن دوم هر حرکتی را انجام دهد بازیکن اول قرینه حرکت او نسبت به مرکز مکعب را انجام می‌دهد. بنابراین به ازای $n$ های فرد بازیکن اول و به ازای $n$ های زوج بازیکن دوم برنده می‌شود.


ابزار صفحه