فهرست مندرجات
سوالات ۱۹ و ۲۰
یک جدول $5 \times 5$ داریم. به یک قطر از یک مربع واحد این جدول، قطرک می‌گوییم. برای مثال، یک قطرک در شکل زیر نشان داده شده است:
دو نقطه‌ی انتهایی هر قطرک، مرزهای آن قطرک نامیده می‌شوند. اگر یک نقطه مرز چهار قطرک رسم‌شده باشد، اشباع نامیده می‌شود (نقاط محیطی جدول هیچ‌گاه اشباع نمی‌شوند).
در هر یک از سوال‌های این دسته قرار است تعدادی قطرک رسم شود (ممکن است قطرک‌ها هم‌دیگر را قطع کنند).
سوال ۱۹
حداکثر چند قطرک می‌توان در جدول رسم کرد، طوری که هیچ نقطه‌ای اشباع نباشد؟
- ۴۲
- ۳۰
- ۴۰
- ۴۶
- ۳۴
پاسخ
گزینه (۱) درست است.
برای اینکه هیچ مرزی اشباع نشود:
- هر نقطه در وسط شکل و نه روی محیط جدول (16 نقطه) می‌تواند مرز حداکثر 3 قطرک باشد.
- هر نقطه روی محیط جدول به جز 4 گوشه (16 نقطه) می‌تواند مرز حداکثر 2 قطرک باشد.
- هر نقطه از ۴ گوشه می‌تواند مرز حداکثر ۱ قطرک باشد
پس در مجموع نقاط می‌توانند ۸۴ بار مرز باشند. از آنجایی که هر قطرک دقیقا ۲ مرز دارد، تعداد قطرک‌ها حداکثر ۴۲ می‌شود. در مثال زیر ۴۲ قطرک رسم شده و هیچ نقطه‌ای اشباع نشده است:
سوال ۲۰
سلطان و ایلیچ یک جدول $5 \times 5$ خالی دارند و می‌خواهند بازی کنند. سلطان بازی را آغاز می‌کند. هر فرد در نوبتش یک قطرک (که تا به‌حال کشیده نشده) رسم می‌کند. نخستین کسی که پس از حرکتش نقطه‌ی اشباع به~وجود بیاید، می‌بازد. فان‌دی‌پلنر (دوست ایلیچ) سه الگوریتم برای بازی کردن به ایلیچ پیشنهاد داده است.
- الگوریتم (آ): فرض کنید سلطان در نوبتش در خانه‌‌ای مانند $A$ یک قطرک رسم کند. بلافاصله پس از آن، قطرک دیگر خانه‌ی $A$ را رسم کن.
- الگوریتم (ب): هر قطرکی که سلطان کشید، آن را نسبت به «خط عمودی گذرنده از نقطه‌ی وسط جدول» قرینه کرده و قطرک متناظر را رسم کن.
- الگوریتم (پ): اگر سلطان قطرکی در خانه‌ی وسط جدول رسم کرد، قطرک باقی‌مانده در خانه‌ی وسط جدول را رسم کن؛ در غیر این صورت قطرک سلطان را نسبت به «نقطه‌ی وسط جدول» قرینه کرده و قطرک متناظر را رسم کن.
کدام الگوریتم‌ها (مستقل از نحوه‌ی بازی سلطان) باعث برد ایلیچ می‌شوند؟
- ب
- هیچ‌کدام
- هر سه مورد
- آ و ب
- ب و پ
پاسخ
گزینه (۱) درست است.
درون هر مربع قطرک‌ها را به شکل زیر نام گذاری می‌کنیم:
- قطرک اصلی: قطرکی که از بالا چپ به پایین راست کشیده می‌شود.
- قطرک فرعی: قطرکی از بالا راست به پایین چپ کشیده می‌شود.
در تمامی موارد سلطان آبی و ایلیچ قرمز است.
الگوریتم (آ): سلطان می‌تواند طوری بازی کند که ایلیچ ببازد. اگر سلطان در ۴ مرحله قطرک اصلی ۴ مربع گوشه بالا سمت راست را بکشد ایلیچ در ۴ امین حرکتش نقطه میانی را اشباع می‌کند.
الگوریتم (ب): با این الگوریتم ایلیچ همیشه می‌برد. فرض کنید یک نقطه را ایلیچ برای اولین بار اشباع کند. نقطه‌ی قرینه نقطه‌ای که ایلیچ اشباع کرده است نسبت به خط عمودی پیش از حرکت ایلیچ اشباع شده است که تناقض است.
الگوریتم (پ): سلطان می‌تواند طوری بازی کند که ایلیچ ببازد. اگر سلطان در ۳ حرکت ابتدایی قطرک‌های زیر را رسم کند و سپس قطرک اصلی خانه وسط جدول را بکشد ایلیچ می‌بازد.
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
