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

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

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

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

[Nadir Zaitov]

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

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

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

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

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

[Nadir Zaitov]

Я только так и доказывал.Именно так? :)
http://upload.wikimedia.org/wikipedia/commons/thumb/6/68/Gay_flag.svg/125px-Gay_flag.svg.png

[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]

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

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

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

[DarkUser]

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


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

[Nadir Zaitov]

Или я не понимаю условия... или... По диагонали - это типа можно, только общими сторонами нельзя.

[Nadir Zaitov]

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

Кстати, Можно было нарисовать только эти 2 картинки и сказать, что все доказано:)

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

Можно было нарисовать только эти 2 картинки и сказать, что все доказано Браво Nadir! Осталось только обосновать немного более строго это решение. Ведь указанные две позиции в принципе не могут совпадать, и значки очевидно стоят на разных местах. Предлагаю, например, так:
у нас 5 "X". Они не могут все являться диагональными. :) Также и "0"-4 "0" не могут являться диагональными. Ъ.

[Nadir Zaitov]

Осталось только обосновать немного более строго это решение.Так нарисуйте другие картинки удовлетворяющие требованию задачи - не получится.

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

нарисуйте другие картинки удовлетворяющие требованию задачи - не получится. Нет, это решение! Просто в нём другая идея. Если бы (по второму решению) одинаковые значки не стояли бы на диагоналях поля и одновременно ни один не был бы соседним с другим, получилось бы противоречие (так как поле у нас - 3X3, то это невозможно: по тому же принципу Дирихле на одну из сторон приходится два "X";так как в центре может стоять только один "X", то и в случае этого значка в центре получим утверждение ). C "0" ситуация аналогичная. Если же по углам будут нолики, мы, как уже отмечалось, получим две выигрышных диагонали. Поняли мысль?

[Nadir Zaitov]

Поняли мысль?Так я ее понял. Тут логика несколько другая: вы строите решение, удовлетворяющее условию задачи и получаете только 2 картинки, которые не соответствуют ничье.