2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Крестики - нолики
Сообщение06.12.2007, 11:29 
Заслуженный участник


03/12/07
380
Україна
Двое играют в <крестики-нолики> на бесконечном листе бумаги. Выигрывает тот, кто первым поставит 5 крестиков (ноликов) по горизонтали или по вертикали подряд. Доказать, что оба игрока при правильной игре не проигрывают.
Задача имеет простое, но весьма нетривиальное решение.

Источник - <Квант> № 11,1975 год, стр.71 - http://kvant.mccme.ru/1975/11/p71.htm

 Профиль  
                  
 
 Re: Крестики - нолики
Сообщение06.12.2007, 13:55 
Заслуженный участник
Аватара пользователя


01/08/06
3158
Уфа
Нужно заполнить плоскость прямоугольниками 2x1 и 1x2, которые мы назовём базовыми, следующим образом:

1134
2234
3411
3422

Видно, что любой прямоугольник 1x5 и 5x1 покрывает хотя бы один базовый прямоугольник полностью.

Стратегия для ходящего вторым ("ноликами") игрока следующая:

Определяем базовый прямоугольник, в который противник поставил "крестик" и ставим "нолик" в оставшуюся свободной клетку этого же базового прямоугольника.

Стратегия гарантирует, что ни один из базовых прямоугольников (а значит, и ни один из прямоугольников 1x5 и 5x1) не будет заполнен одними "крестиками".

Стратегия для ходящего первым оставляется в качестве упражнения :)

 Профиль  
                  
 
 
Сообщение06.12.2007, 16:42 


02/12/07
15
А если рассматривать не только горизонталь или вертикаль, а также диагональ (т. е. если поставить 5 крестиков по диагонали, то выигрывает первый, если 5 ноликов - второй), то есть ли стратегия непроигрыша? Или хотя бы не явная стратегия, а доказательтво существования такой стратегии?

 Профиль  
                  
 
 
Сообщение06.12.2007, 17:07 
Заслуженный участник
Аватара пользователя


01/08/06
3158
Уфа
Думаю, ответ неизвестен. Я видел одну программу, которая играет в эту игру. У этой программы можно было выиграть.

 Профиль  
                  
 
 
Сообщение06.12.2007, 20:40 
Заслуженный участник
Аватара пользователя


23/07/05
18037
Москва
У японцев есть игра "Рэндзю". Используется стандартная доска для Го 19x19 пунктов. Нужно выстроить сплошной ряд из пяти своих шашек. В Рэндзю имеются различные ограничения на ходы первого игрока из-за того, что первый игрок систематически выигрывает. Я где-то встречал упоминание, что якобы японцы доказали, что при игре без ограничений первый игрок выигрывает.

 Профиль  
                  
 
 
Сообщение06.12.2007, 23:43 
Модератор
Аватара пользователя


11/01/06
5710
На поле 19x19 - это Гомоку, а Рендзю - на поле 15x15. Есть также игра "5 в ряд" - как раз на бесконечном поле.

Добавлено спустя 4 минуты 36 секунд:

Игра на поле $m\times n$, где требуется получить ряд из $k$ своих фишек, называется "m,n,k-игрой". Вот тут представлены результаты по анализу таких игр: http://en.wikipedia.org/wiki/M%2Cn%2Ck-game

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 6 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: drzewo, YandexBot [bot]


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group