Стоящие рядом

[николай москвитин]

Предлагаю собственную задачу по другому разделу логики.

Пусть при игре в "X-0" получилась ничья (при этом считается, что, по традиции, независимо от числа ходов до достижения ничьи, заполняются все 9 клеток). Доказать, что обязательно будет пара рядом стоящих "X" и пара рядом рядом стоящих "0" (на соседних клетках по вертикали или горизонтали).

[Nadir Zaitov]

Сообщение от николай москвитин

Доказать, что обязательно будет пара рядом стоящих "X" и пара рядом рядом стоящих "0" (на соседних клетках по вертикали или горизонтали).

Доказать "влоб" ничего сложного не представляет. Но как доказать "красиво"

[николай москвитин]

Сообщение от Nadir Zaitov

как доказать "красиво"

Я только так и доказывал. Стратегия + один очень-очень знаменитый принцип.

[Nadir Zaitov]

Сообщение от николай москвитин

Я только так и доказывал.

Именно так?

[Nadir Zaitov]

николай москвитин, может дадите свое решение?

[николай москвитин]

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

[Nadir Zaitov]

Сообщение от николай москвитин

Хорошо! Доказательство относительно несложное.

Но это и есть влом "в лоб" и поэтому я и назвал его некрасивым...

[JH]

Или я не понимаю условия... или... Очевидно же, что если в одном углу стоит крестик, то в трех клетках вокруг него должны быть нули, соответственно, они будут соседними друг для друга...

[николай москвитин]

Сообщение от JH

Очевидно же, что если в одном углу стоит крестик, то в трех клетках вокруг него должны быть нули, соответственно, они будут соседними друг для друга...

Практика ведь не подтверждает это. Фактически Вы утверждаете, что не может быть позиции, в которой вокруг "X" в углу есть "X". Вернее, что обязательно будет указанная Вами позиция. По крайней мере попробуйте доказать Вашу гипотезу.

[DarkUser]

Сообщение от JH

Очевидно же, что если в одном углу стоит крестик, то в трех клетках вокруг него должны быть нули

AFAIU, только в двух, т.к.

Сообщение от николай москвитин

на соседних клетках по вертикали или горизонтали

т.е. что-то вроде

PHP код:

X | 0 | X         0 | X | 0
---------         ---------
0 | X | 0   либо  X | 0 | X
---------         ---------
X | 0 | X         0 | X | 0