Задание №175388: Задание 3

3. При каких n, больших 2, можно расставить в клетках таблицы размером nn крестики и нолики (в
каждой клетке — один знак) так, чтобы в каждом столбце таблицы, кроме одного, крестиков было
больше, чем ноликов, а в каждой строке таблицы, кроме одной, ноликов было больше, чем крестиков?
(И. Рубанов)
Ответ. При всех нечетных n. Решение. Пример. Пусть n = 2k+1 нечетно. Выделим в таблице квадрат 2k×2k,
находящийся в левом верхнем углу. Разобьем его на четыре квадрата k×k. Левый верхний и правый нижний
из этих квадратов целиком заполним крестиками, а остальные два — ноликами. Затем крайний правый
столбец таблицы целиком заполним ноликами, а во всех клетках нижней строки, кроме самой правой,
поставим крестики. Теперь в каждом столбце таблицы, кроме самого правого, стоит k+1 крестиков и k
ноликов, а в каждой строке, кроме самой нижней — k+1 ноликов и k крестиков. Оценка. Пусть n = 2k четно.
Тогда в каждом из
2k–1 столбцов таблицы, где крестиков больше, чем ноликов, крестиков должно быть по крайней мере k+1.
Значит, всего в таблице должно быть по крайней мере (2k–1)(k+1) = 2k2+k–1 > 2k2 крестиков (так как по
условию n > 2, то k > 1), то есть больше половины общего числа 4k2 клеточек таблицы. Но из рассмотрения
строк таким же образом получается, что больше половины общего числа клеточек таблицы должно быть
заполнено ноликами. Полученное противоречие показывает, что при четном n таблицу нужным образом
заполнить нельзя.