| николай москвитин |
19.07.2011 18:03 |
Хорошо! Доказательство относительно несложное. Начинать лучше именно с "X". Итак: покажем сначала, что обязательно будет пара рядом стоящих "X". Абстрагируемся от порядка ходов, остановим внимание лишь на позиции. Если бы "X" только чередовался с "0" (т.е. не было бы соседних "X"), то получились бы аж две выигрышные диагонали в одном случае и перебор нулей в другом (то есть их было бы 5). Далее я делаю следующий ход: принцип Дирихле пока откладываем. Рассмотрим клетки, соседние с двумя соседними "X" (ясно, что их можно рассматривать, и сверху, и снизу, но я решил рассматривать именно справа или слева-можно просто перевернуть поле). Если там нет "X", имеем два соседних "0" (а значит, этот случай доказан). Значит, можно считать, что там будет 1 "X". Тогда у нас остаётся 6 клеток, 2 "X" и 4 "0". Разобьём их на пары (неважно, что одна из них будет "несвязной"): теперь, уже используя принцип Дирихле, получаем, что в каждой из пар обязательно должно быть по "0", и, кроме того, остаётся ещё один лишний "0". Следовательно, будет пара рядом стоящих нулей. Теперь (только сегодня подумал): что же делать в случае "несвязной пары ( то есть с парой несоседних нулей)?-Если предположить, что ни одна пара нулей не является связной, получим выигрышный ряд нулей. Это если уголок из "X" с краю. Если же один из "X" уголка вылезает в центр, все пары связны. Доказано!:) Комментарий: связность здесь используется не совсем в обычном смысле: считается, что диагональные клетки не соприкасаются друг с другом по прямой линии. Да, и ещё один случай: если вершина уголка "X" в центре. Решается аналогично: если предположить, что нет рядом стоящих нулей, получаем две выигрышных диагонали.
|
