Processing math: 100%

المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۱۷

یک تکه کاغذ به شکل مقابل در اختیار داریم:

دو نفر با نام‌های ‎A‎ و ‎B‎ به این صورت بازی می‌کنند: ‎A‎ در نوبت خودش یک تکه کاغذ را انتخاب کرده، با یک برش مستقیم روی یکی از خطوطی که با نقطه چین مشخص شده‌اند، آن را به دو تکه تقسیم می‌کند. سپس ‎B‎ نیز در نوبت خود همین کار را با یکی از تکه‌های کاغذ و خطوطی که به صورت کامل (غیر نقطه چین) کشیده شده‌اند انجام می‌دهد. هر یک از بازیکنان که در نوبت خود نتواند بازی کند، بازنده محسوب می‌شود‎.‎

کدام یک از گزاره‌های زیر درست‌تر است؟

  1. اگر ‎A‎ بازی را شروع کند، می‌تواند برنده شود.
  2. اگر ‎B‎ بازی را شروع کند، می‌تواند برنده شود. ‎
  3. در هر صورت ‎A‎ می‌تواند برنده شود.
  4. در هر صورت ‎B‎ می‌تواند برنده شود. ‎
  5. هر بازیکنی که بازی را شروع کند می‌تواند برنده شود.

پاسخ

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

در هر صورت ‎A‎ می‌تواند برنده شود. خطوط تکه کاغذ را به شکل زیر شماره‌گذاری می‌کنیم. اگر ‎B شروع‌کننده باشد به ناچار از یکی از سطرها ۱ یا ۲ کاغذ را به دو تکه تقسیم می‌کند. فرض می‌کنیم این شخص سطر ۱ را برش داده و تکه کاغذ را به دو تکه a (قسمت بالایی) وb (قسمت پایینی) تقسیم کند. در این صورت شخص‎A از یکی از ستون‌های ۱ و یا ۳ تکه a٬ آن را به دو تکه تقسیم می‌کند. ‎B ناچارا سطر ۲ از تکه‌ی b را برش می‌دهد و بازنده می‌شود زیرا چیزی برای برش دادن برای مرحله‌ی بعد برای او باقی نمی‌ماند.

اگر ‎A شروع‌کننده باشد ابتدا او تکه کاغذ را از ستون ۲ برش می‌دهد. ‎B یکی از دو تکه را از سطر ۱ یا ۲ به دو تکه تقسیم می‌کند. شخص ‎A تکه‌ی کوچک‌تر را انتخاب کرده و آن را به دو قسمت تقسیم می‌کند. شخص ‎B در نوبت خود سه بار دیگر می‌تواند تکه کاغذ‌ها را برش دهد و چیزی برای برش برای او باقی نخواهد ماند در صورتی که در هر مرحله برای شخص ‎A تکه کاغذ برای برش افزایش پیدا می‌کند.


ابزار صفحه