Задача 109955
|
|
 |
Условие
На концах клетчатой полоски размером 1×101 клеток стоят две фишки: слева – фишка первого игрока, справа – второго. За ход разрешается сдвинуть свою фишку в направлении противоположного края полоски на 1, 2, 3 или 4 клетки. При этом разрешается перепрыгивать через фишку соперника, но запрещается ставить свою фишку на одну клетку с ней. Выигрывает тот, кто первым достигнет противоположного края полоски. Кто выиграет при правильной игре: тот, кто ходит первым, или его соперник?Решение
Выигрывает первый. Сначала ему надо делать ходы длиной в 4 клетки, пока он не встанет на 45-ю клетку. Теперь очередь хода за вторым. Если он тоже все время делает ходы длины 4, очередной ход приведет его на клетку 57. Тогда первый следующим ходом должен пойти на клетку 48 и после ответа второго сходить так, чтобы между ним и вторым оказалось 3 клетки (легко видеть, что это всегда возможно). После этого второй будет вынужден пойти на 1, 2 или 3 клетки и окажется в итоге правее 49-й клетки. Значит, до финиша ему останется больше 48 клеток, и, чтобы добраться туда, он должен будет сделать не меньше 13 ходов. Первый же находится не левее 49-й клетки, и ему до финиша остается не более 52 клеток, которые он сумеет преодолеть за 13 ходов.Рассмотрим теперь случай, когда среди 11 первых ходов второго был ход менее, чем на 4 клетки.
Тогда он после 11-го хода окажется более, чем в 56 клетках от цели, и для ее достижения ему понадобится минимум 15 ходов, а первому до цели остается 56 клеток, и он сможет добраться до нее за 15 ходов, даже если второй при встрече вынудит его сделать ход длины 3 вместо хода длины 4.
