| Об игре с палочками |
[Апр. 15, 2008; 02:33 pm] |
Есть такая простенькая игра. На стол выкладываются палочки, и два игрока по очереди убирают их со стола. Ходят по очереди, за ход можно убрать одну, две или три палочки. Снявший последнюю — проигрывает.
В такую игру играли в свое время в телеигре «Форт Байяр». На самом деле игра совершенно проста в расчетах, и чтобы определить победителя, достаточно знать, сколько палочек на столе и кто первый ходит. При правильной игре, конечно.
Уточнение. Правильной игрой считается та, которая ведет к победе. Как правило, это некий алгоритм. В шахматах и го, например, такой алгоритм не найден, чего нельзя сказать про шашки. В игре с палочками такой алгоритм существует.
Итак, сначала скажем о некой особенности, которая ляжет в основу нашего алгоритма. Пусть играют игроки А и Б, а на столе К палочек. Ходит А. Тогда Б всегда может сделать так, чтобы в следующий раз при ходе А на столе было К–4 палочки, т. е. в сумме А и Б за два хода снимут 4 палочки. Это действительно так: А тянет 3, Б — 1; А — 2, Б — 2; А — 1, Б — 3.
Теперь начнем разбирать сам алгоритм с конца.
Ходит А. Если на столе одна палочка, то он, очевидно, проиграл. Добавим на стол 4 палочки. Всего стало 5. Как известно Б может сделать так, что после пары ходов А и Б количество палочек уменьшится на 4, а значит останется одна. Итак, при пяти палочках А тоже проигрывает (5=1+3+1=2+2+1=3+1+1).
Добавим еще четыре палочки, теперь их 9. Однако после ходов А и Б их снова станет на 4 меньше (если Б будет следовать обозначенному выше принципу). Имея на своем ходу 5 палочек, А проигрывает, что доказывается в предыдущем абзаце. Значит, имея на своем ходу 9 палочек, он проиграет тоже (9=1+3+5=2+2+5=3+1+5).
Прибавляя снова и снова по четыре палочки, мы получим все те количества, при которых А проиграет. Все они имеют вид: 4+4+...+4+1. Т. е. К имеет вид 4×G+1, где G — любое целое неотрицательное число.
Итак, если при ходе А на столе лежит 4×G+1 палочка, то независимо от того, сколько палочек будет тянуть А, после хода Б их будет на четыре меньше, т. е. 4×(G–1)+1. Потом 4×(G–2)+1, 4×(G–3)+1, и так далее, пока не дойдет до 4×(G–G)+1=1. Проигрыш А при одной палочке на столе очевиден.
Отступление. На столе K=4×G+1 палочка, что можно сказать про К?
К–1=4×G, т. е. К–1 делится на 4 нацело (G-то целое).
Итак, на столе такое количество палочек, что по вычитанию единицы оно делится на четыре. Тогда тот, кто ходит первый — заведомо проиграл.
Если же на столе любое другое количество палочек, то тот, кто ходит первый, должен снять столько, сколько нужно, чтобы противнику достались то самое проигрышное число. Такие числа — каждые четвертые в ряду целых, поэтому всегда можно снять 1, 2 или 3 палочки так, чтобы получить одно из них.
Пример:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19...
Если при ходе А ему досталось одно из жирных чисел — он проиграл, если другое — нужно сыграть таким образом, чтобы жирное число досталось Б, он всегда может это сделать, а значит — победил.
Несмотря на пространные объяснения и математические (хотя и простейшие) выкладки, понять это все очень просто. Оказывается, игра не представляет ровным счетом никакого интереса. По сути, это задача, а не игра. Хотя, конечно, с человеком, не решавшим ее, можно и сыграть. В целом, правильная игра обуславливается двумя правилами:
1) Снимите палочки так, чтобы остаток после отнимания единицы делился на 4.
2) Если вы не можете этого сделать (он уже делится на 4, нужно снять 0 или 4), снимайте сколько угодно и улыбайтесь, вы проиграли. |
|
|
