Игра, в которой требуется вытаскивать шарики из кувшина. Забравший последний шарик — победитель. Нужно определить лучшую стратегию

У вас есть стеклянный кувшин, в котором лежат небольшие шарики, и вы в любое время можете определить их количество. Вы со своим другом играете в следующую игру: каждый из вас по очереди забирает из кувшина 1 или 2 шарика. Игрок, который забирает последний шарик, выигрывает. Какая самая лучшая стратегия в этой игре? Можете ли вы в самом начале предсказать, кто выиграет?

Число шариков становится все меньше и меньше с каждым ходом, и, в конце концов, их станет как-то совсем мало. Вот тут-то стратегия становится совершенно понятной.
Давайте исходить из того, что в кувшине остался всего один шарик и теперь моя очередь брать. Взяв последний шарик, я выиграю.

Я выиграю и при двух оставшихся шариках, потому что могу взять оба.
Но три оставшихся шарика для меня плохой вариант. Мне придется оставить либо один, либо два шарика, и тут-то мой соперник немедленно воспользуется таким подарком.

Четыре и пять шариков — хороший вариант. Я могу оставить моего соперника с неудачным (уже для него) числом три.
Ну что ж, все понятно. Число, которое делится на три, означает для меня проигрыш: 3, 6, 9, 12… — плохие варианты, когда моя очередь ходить. Все другое (1, 2, 4, 5, 7, 8…) — прекрасно.

Так как теперь этим воспользоваться в игре? Мы начинаем с большого, но неизвестного числа шариков. Разделим его на 3. Если число делится без остатка, это неудачный для нас вариант. Тогда постарайтесь не ходить первым. Если соперник предложит вам бросить монетку, чтобы решить, кто должен ходить первым, проявите «великодушие» и позвольте ему сделать первый ход. Если же вам улыбнулась удача и число шариков не делится на три, и вы ходите первым, то стратегия выигрыша проста: с каждым ходом берите столько шариков, чтобы в кувшине оставалось проигрышное число. Скажем, если вы начнете с 304 шариков (прекрасно для вас), вы забираете один, оставляя сопернику неудачные для него 303. Поступайте так при каждом ходе, и, в конце концов, он останется с тремя шариками. Такая стратегия обеспечит вам победу.

Более того, такая стратегия совершенно надежно приведет вас к выигрышу, независимо от того, как будет действовать другой игрок (если только в порыве гнева он не размахнется кувшином об пол). Ему приходится забирать один или два шарика из оставшегося числа, неудачного для него. Это всегда позволяет вам при следующем ходе оставлять в кувшине «удачное» число шариков.

Но что делать, если вы начинаете с неудачного расклада? Вы обречены на поражение, если другой игрок сам применит описанную выше стратегию. Однако пока никакой трагедии нет. Ваш соперник может и не знать о такой стратегии, а может просто просчитаться. Любой, кто играет без стратегии, почти обязательно рано или поздно предоставит вам возможность перейти к счастливому (для вас) числу, поскольку две трети всех чисел для вас выигрышны. Человек, который знает оптимальную стратегию, но в ходе игры ошибется хотя бы раз, обречен: он больше не командует парадом (конечно, при условии, что вы такой ошибки не совершите).

Но, собственно, вас-то спрашивают, можно ли предсказать, кто выиграет. Да, если оба игрока идеально знают теорию этой игры. Определите, является ли первоначальное число шариков «счастливым». Если да, то первый игрок всегда выиграет. И наоборот.

Но живем мы с вами в реальном мире. Кто возьмется предсказать конечный результат?! Даже если оба игрока знают правильную стратегию, чем больше шариков в игре, тем выше вероятность ошибки. Шансы выше у того, кто не ошибется, следуя выигрышной стратегии.

Встречаются и варианты этого вопроса, например такой: проигрывает тот, кто забирает последний шарик. Как поступить в этом случае? «Неудачное» число шариков запишем в виде 3N+1, а затем будем применять ту же самую стратегию.

Разбор по книге «Действительно ли Вы достаточно умны, чтобы работать в Google?»