2014 dxdy logo

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

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




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

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

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

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

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

 
 
 
 Re: Два игрока по очереди ставят точки в клетки таблицы
Сообщение12.12.2017, 13:20 
При числе точек меньше 28 всегда найдется строка, куда можно поставить точку, ... и столбец, конечно, тоже. Можно разрешить первому поставить сразу 14 точек, затем перестановкой строк и столбцов разместить их как угодно. От этого результат не изменится.
Этот же текст я привел в комментарии к этой задаче на форуме hashcode.

 
 
 
 Re: Два игрока по очереди ставят точки в клетки таблицы
Сообщение12.12.2017, 13:26 
Аватара пользователя
Iam в сообщении #1274335 писал(а):
При числе точек меньше 28 всегда найдется строка, куда можно поставить точку, ... и столбец, конечно, тоже
Это так, но клетка на пересечении этого столбца и этой строки может быть уже занятой.
Пример проигрышной ситуации из 25 точек: два заполненных противолежащих квадрата 4x4 и 3x3 и свободные прямоугольники 3x4 и 4x3 между ними.

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

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

 
 
 
 Re: Два игрока по очереди ставят точки в клетки таблицы
Сообщение12.12.2017, 13:37 
worm2 в сообщении #1274337 писал(а):
.
Пример проигрышной ситуации из 25 точек: два заполненных противолежащих квадрата 4x4 и 3x3 и свободные прямоугольники 3x4 и 4x3 между ними.

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

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

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

 
 
 [ Сообщений: 4 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group