Задание №177566: Турнир Ломоносова 2010

Question

3. «Борьба за территорию». Двое играют на поле 5 5 клеток, × закрашивая клетки — каждый в свой цвет. Первый игрок своим ходом красит одну клетку, второй — фигуру из нескольких клеток (повёрнутую по своему усмотрению). Повторно клетки красить нельзя. Игрок, не имеющий хода, пропускает его. Игра заканчивается, когда всё поле закрашено. Победителем считается тот, кто в итоге сумел закрасить своим цветом бо´льшую площадь, чем противник. Кто — начинающий или его соперник — победит в этой игре, как бы ни играл его партнёр? Рассмотрите случаи, когда второй игрок закрашивает: а) полоску 1 2 клетки ( ); × б) полоску 1 3 клетки ( ); × в) полоску 1 4 клетки ( ); × г) полоску 1 5 клеток ( ); × д) уголок из трёх клеток ( ). (Поля 5 5 клеток можно использовать для игр и черновиков.) × 20

Официальный разбор · ВсОШ · Accepted Answer

3. «Борьба за территорию». Поначалу кажется, что второй
     игрок имеет существенное преимущество: он одним ходом закраши-
     вает в несколько раз больше клеток, чем противник. Однако фигуры
     второго игрока хоть и большие, но неповоротливые: умелой игрой начи-
     нающий быстро «портит» игровое поле, не давая сопернику ходить,
     после чего заполняет свободную территорию своим цветом. Только
     изогнутая форма фигурки второго игрока в последнем пункте («г»)
     позволяет ему (не без труда) победить «одноклеточного» соперника.

Рис. 1          Рис. 2           Рис. 3       
                                                       
       Для описания стратегии первого игрока в пункте «а» поставим на
     некоторых полях точки (см. рис 1). Очевидно, что каждым своим ходом
     второй игрок закрасит одну и только одну отмеченную клетку. Если
     первый игрок будет красить только клетки с точкой (а именно так мы
     и рекомендуем ему поступать), то после того, как оба сделают по шесть
     ходов, второй игрок больше пойти не сможет, а потому проиграет — он
     закрасил только 12 клеток из 25.                  
                                                       
                           23

Абсолютно аналогично решение и в двух следующих пунктах: соот-
     ветствующие расстановки точек смотрите на рисунках 2 и 3.
       Отметим, что в этих случаях «одноклеточный» игрок победит, даже
     если предоставит право первого хода сопернику.    
       В пункте «г» после первого парного хода определяется, в каком
     направлении (вертикальном или горизонтальном) будет красить клетки
     второй игрок. Если, например, он закрасил столбец, то и дальше сможет
     красить только столбцы. Но свободных столбцов остаётся 3, из которых
     он сможет гарантированно закрасить только 1 — два других «испортит»
     начинающий. Тем самым второй игрок закрасит только 10 клеток из 25.
     В этом варианте игры первый игрок проиграет, если передаст сопернику
     право начать игру.                                
       Приведём теперь стратегию для второго игрока в пункте «д» — это
     задание оказалось самым сложным во всём конкурсе. 
      4 5 7 6 4                                        
      6 3 2 3 5                                        
      7 2 1 2 7                                        
                                                       
      5 3 2 3 6                                        
      4 6 7 5 4                                        
         Рис. 4          Рис. 5           Рис. 6       
                                                       
       Все 25 клеток игрового поля можно разбить на семь типов (рис. 4)6:

Задание №177566: Турнир Ломоносова 2010

Что проверяет это задание

Качество материала

Происхождение задания

Связанные понятия

План самостоятельного решения

Закрепить тему

Решение по шагам

Самопроверка после решения

Типичные ошибки