|
|
 |
Условие
В некоторых клетках таблицы 10x10 расставлены несколько крести-
ков и несколько ноликов. Известно, что нет линии (строки или столб-
ца), полностью заполненной одинаковыми значками (крестиками или
ноликами). Однако, если в любую пустую клетку поставить любой
значок, то это условие нарушится. Какое минимальное число значков
может стоять в таблице?
Решение
Пусть мы заполнили таблицу согласно условию, а клетка A
свободна. Так как при постановке в нее любого значка должна
получаться линия из одинаковых значков, то существует линия, содержащая
ее, в которой все остальные клетки заполнены крестиками, и то же
самое верно для ноликов (эти линии должны быть, естественно,
строкой и столбцом). В частности, все свободные клетки стоят в разных
строках и столбцах.
Предположим, что пустых клеток больше двух. Тогда для двух
из них (скажем, для A и B) направления линии крестиков
совпадают (то есть либо для обеих крестики стоят в их горизонталях, либо
для обеих — в вертикалях) (см. рис.). Пусть крестики стоят в их
столбцах, а нолики — в их строках; тогда в пересечении строки,
содержащей A , со столбцом, содержащим B, должен стоять и крестик,
и нолик (ибо это пересечение непусто); противоречие. Значит, пустых
клеток не больше двух. Пример с двумя пустыми клетками приведен
на рис. (вместо звездочек могут стоять любые значки).
Ответ
98.
