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