Минимальное число крестиков и ноликов в 10x10: олимпиадная задача Богданова

Пусть мы заполнили таблицу согласно условию, а клетка A свободна. Так как при постановке в нее любого значка должна получаться линия из одинаковых значков, то существует линия, содержащая ее, в которой все остальные клетки заполнены крестиками, и то же самое верно для ноликов (эти линии должны быть, естественно, строкой и столбцом). В частности, все свободные клетки стоят в разных строках и столбцах. Предположим, что пустых клеток больше двух. Тогда для двух из них (скажем, для A и B) направления линии крестиков совпадают (то есть либо для обеих крестики стоят в их горизонталях, либо для обеих — в вертикалях) (см. рис.). Пусть крестики стоят в их столбцах, а нолики — в их строках; тогда в пересечении строки, содержащей A , со столбцом, содержащим B, должен стоять и крестик, и нолик (ибо это пересечение непусто); противоречие. Значит, пустых клеток не больше двух. Пример с двумя пустыми клетками приведен на рис. (вместо звездочек могут стоять любые значки).