2014 dxdy logo

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

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


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему
 
 Два игрока по очереди ставят точки в клетки таблицы
Сообщение12.12.2017, 01:53 
Аватара пользователя


01/12/11

8634
Два игрока по очереди ставят точки в клетки таблицы $7\times 7$. За один ход
ставится ровно одна точка. В одну клетку может быть поставлено несколько
точек (ставить точки на границы клеток нельзя). Проигрывает тот, после
чьего хода в клетках какой-то строки или столбца суммарно будут стоять 5
точек. Кто из игроков может обеспечить себе победу независимо от игры
соперника?

(Минская городская олимпиада)

............................................................

Меня смущает, что в одну клетку может быть поставлено несколько точек, ведь добавление данной детали в условие задачи лишь облегчает её решение!
Действительно, вторму игроку для победы достаточно в ответ на ход первого игрока ставить точку в той же самой клетке, что и первый. Изначально таблица пуста (во всяком случае, в условии не указано, что это не так), следовательно, в каждом строке и в каждой столбце чётное число точек. Ход первого игрока нарушает условие чётности (ровно в одной строке и ровно в одном столбце теперь нечётное число точек), а ответный ход второго возвращает всё на круги своя - и снова в каждой строке и в каждом столбце чётное число. Следовательно, первый игрок рано или поздно проиграет.
Разве не так?

А если изменить условие и запретить ставить в одну клетку более одной точки, что тогда?
Пожалуйста, помогите решить.
Заранее благодарю!

 Профиль  
                  
 
 Re: Два игрока по очереди ставят точки в клетки таблицы
Сообщение12.12.2017, 13:20 


01/11/14
195
При числе точек меньше 28 всегда найдется строка, куда можно поставить точку, ... и столбец, конечно, тоже. Можно разрешить первому поставить сразу 14 точек, затем перестановкой строк и столбцов разместить их как угодно. От этого результат не изменится.
Этот же текст я привел в комментарии к этой задаче на форуме hashcode.

 Профиль  
                  
 
 Re: Два игрока по очереди ставят точки в клетки таблицы
Сообщение12.12.2017, 13:26 
Заслуженный участник
Аватара пользователя


01/08/06
3053
Уфа
Iam в сообщении #1274335 писал(а):
При числе точек меньше 28 всегда найдется строка, куда можно поставить точку, ... и столбец, конечно, тоже
Это так, но клетка на пересечении этого столбца и этой строки может быть уже занятой.
Пример проигрышной ситуации из 25 точек: два заполненных противолежащих квадрата 4x4 и 3x3 и свободные прямоугольники 3x4 и 4x3 между ними.

-- Вт дек 12, 2017 15:28:03 --

Случай 3x3 (проигрывает тот, кто заполняет ряд или строку, т.е. критическое число точек тоже 3) уже не могу назвать тривиальным. Но при правильной игре выигрывает второй.

 Профиль  
                  
 
 Re: Два игрока по очереди ставят точки в клетки таблицы
Сообщение12.12.2017, 13:37 


01/11/14
195
worm2 в сообщении #1274337 писал(а):
.
Пример проигрышной ситуации из 25 точек: два заполненных противолежащих квадрата 4x4 и 3x3 и свободные прямоугольники 3x4 и 4x3 между ними.

-- Вт дек 12, 2017 15:28:03 --

Случай 3x3 (проигрывает тот, кто заполняет ряд или строку, т.е. критическое число точек тоже 3) уже не могу назвать тривиальным. Но при правильной игре выигрывает второй.

Контрпример для меня неожиданный. Суждения были поверхностными, задача оказалась интересной.

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

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



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

Сейчас этот форум просматривают: нет зарегистрированных пользователей


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

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