Задача М153‍‍‍

Приведём решение для общего случая, когда в каждой строчке не 4, а $n$‍‍ звёздочек. Докажем, что при наилучшей игре противников разность окажется равной $4\cdot10^{n-1}$‍.‍

а) Стратегия второго игрока.

Если первая цифра, названная первым игроком, 4 или меньше, второй игрок ставит её вместо старшего разряда уменьшаемого. После этого, как только первый игрок назовёт цифру, отличную от 0, второй заполняет ею старший разряд вычитаемого. Разность окажется не большей чем $$ \underbrace{499\ldots9}_n-\underbrace{100\ldots0}_n\lt4\cdot10^{n-1}. $$ Если первый игрок, начиная со второго хода, каждый раз называет 0, то разность также будет меньше, или равна $4\cdot10^{n-1}$‍.‍

Если первый игрок начинает с цифр 5, 6, 7, 8 или 9, второй ставит её на место старшего разряда вычитаемого, а затем занимает старший разряд уменьшаемого первой же названной цифрой, отличной от 9. Даже если все последующие цифры — девятки, то также получится разность, не превосходящая $4\cdot10^{n-1}$‍.‍

б) Стратегия первого игрока.

До тех пор пока остаются свободными старшие разряды уменьшаемого и вычитаемого, первый игрок называет цифры 4 и 5. Начиная с момента, когда второй игрок заполнит один из двух старших разрядов, и до конца игры первый игрок называет 0, если раньше оказался заполненным старший разряд уменьшаемого, и 9 — в противном случае. Остаётся уточнить, в каких случаях первый игрок называет цифру 4, а в каких — цифру 5.

Перед очередным своим ходом первый игрок мысленно проставляет нули во всех незаполненных разрядах. Если после этого разность оказывается неотрицательной, он объявляет цифру 4, если же разность отрицательна — цифру 5.

Докажем, что описанная стратегия первого игрока позволяет ему сделать разность не меньшей $4\cdot10^{n-1}$‍.‍

Если старший разряд вычитаемого займёт цифра 4, то в старшем разряде уменьшаемого окажется цифра 9: $$ \underbrace{900\ldots0}_n-\underbrace{499\ldots9}_n\gt4\cdot10^{n-1}. $$

Если старший разряд уменьшаемого заполнит цифра 5, то старший разряд вычитаемого займёт цифра 0, а $$ \underbrace{500\ldots0}_n-\underbrace{099\ldots9}_n\gt4\cdot10^{n-1}. $$

Предположим, что первый игрок назвал цифру 4, а второй заполнил ею старший разряд уменьшаемого. Перед этим ходом разность была неотрицательной, после хода она увеличилась на $4\cdot10^{n-1}$‍‍ и больше не изменялась, так как при всех следующих ходах первый игрок называл 0.

Осталось рассмотреть случай, когда первый игрок назвал цифру 5, а второй заполнил єю старший разряд вычитаемого. Разобьём цифры, называемые первым игроком, на серии, объединяя в серию одинаковые цифры, идущие подряд. Будем считать, что второй игрок не ставит друг под другом одинаковые цифры, в противном случае их можно было бы перечеркнуть и не рассматривать при дальнейших рассуждениях. Докажем теперь, что каждая серия из четвёрок кончается так: $$ \colsep{2pt}{\begin{array}{cccccccc} *&\ldots&*&*&a_m&a_{m+1}&\ldots&a_n\\ *&\ldots&*&4&b_m&b_{m+1}&\ldots&b_n\\ \end{array}} $$ To, что первая серия кончается так, очевидно. Пусть $s$‍‍-я серия из четвёрок кончается таким образом. Покажем, что и ($s+1$‍)‍-я ceрия закончится так же. После 5-й серии четвёрок пойдёт серия из пятёрок. Рассмотрим самую левую пятёрку из этой серии (напомним, что перечёркнутых цифр мы не рассматриваем!). Ясно, что она попадёт в уменьшаемое в разряд с номером, меньшим $m$‍,‍ а под ней стоит либо звёздочка, либо, если она попала в ($n-1$‍)‍-й разряд, четвёрка. Эта пятёрка — последняя в своей серии. Действительно, после того, как она поставлена, разность становится положительной и первый начнёт объявлять четвёрки. Если рассмотреть теперь самую левую четвёрку из ($s-1$‍)‍-й серии, то, с помощью таких же рассуждений можно убедиться, что она стоит в вычитаемом в разряде, более близком к первому, чем последняя пятёрка из предыдущей серии, над ней стоит звёздочка и что она — последняя в своей серии.

Поэтому после того, как названа последняя четвёрка, возникнет следующая ситуация $$ \colsep{2pt}{\begin{array}{ccccccccc} *&*&*&\ldots&*&*&a_{k+1}'&\ldots&a_n'\\ *&*&*&\ldots&*&4&b_{k+1}'&\ldots&b_n' \end{array}} $$

После этого первый игрок один или несколько раз назвал цифру 0 и, так как после каждого его хода уменьшаемое оставалось меньше вычитаемого (при мысленной замене звёздочек нулями), то перед объявлением девяток возникло следующее положение $$ \colsep{2pt}{\begin{array}{ccccccccc} *&a_2&a_3&\ldots&a_{k-1}&a_k&a_{k+1}'&\ldots&a_n'\\ 5&a_2'&a_3'&\ldots&a_{k-1}'&4&b_{k+1}'&\ldots&b_n' \end{array}} $$ где для каждого $i=2$‍,‍ 3, $\ldots$‍,‍ $k-1$‍‍ либо $a_i=a_i'$‍,‍ либо $a_i'=5$‍‍ и $a_i$‍‍ — звёздочка, причём разность чисел $$ \colsep{2pt}{\begin{array}{ccccc} a_2&a_3&\ldots&a_{k-1}&a_k\\ a_2'&a_3'&\ldots&a_{k-1}'&4 \end{array}} $$ отрицательна. Действительно, если бы она была положительна, то перед объявлением девяток первый игрок объявил бы четвёрку, а нулём она быть не может, поскольку $a_k$‍‍ либо звёздочка, либо пятёрка. С другой стороны, ясно, что если при $i\lt k$‍‍ $a_i$‍‍ и $a_i'$‍‍ — не звёздочки, то $a_i=a_i'$‍;‍ действительно, они совпадали в момент объявления последней четвёрки. Поэтому для некоторого $j\le k$‍‍ $a_j$‍‍ — звёздочка, а под ней стоит четвёрка или пятёрка. Но тогда ясно, что окончательная разность не меньше $4\cdot10^{n-1}+3\cdot10^{n-j}\gt4\cdot10^{n-1}$‍.‍ Задача решена.