Олимпиада Туймаада по математике. Младшая лига. 2021 год

На доске $100 \times 100$ отмечено 110 клеток. Верно ли, что можно так переставить строки и столбцы, чтобы все клетки отмеченные оказались не ниже главной диагонали? ( М. Антипов )

Комментарий/решение

Покажем на деле, что это невозможно для 102 квадратов. Конфигурация представляет собой квадрат $2\times 2$ в верхнем левом углу, а остальные квадраты — в верхнем левом и правом нижнем углу главной диагонали. Мы покажем это индукцией по таблице $n\times n$.

Базовый случай $n=2$ очевиден (все квадраты закрашены).

Что касается индуктивного шага, предположим, что он возможен для некоторого $n>2$. Выберите строку, содержащую один отмеченный квадрат. Тогда столбец, содержащий квадрат, не содержит других отмеченных квадратов. Если этот квадрат не находится на главной диагонали (т.е. квадрат находится справа от диагонали), то мы можем переместить столбец влево так, чтобы квадрат оказался на главной диагонали. Все остальные столбцы перемещаются вправо, и на достоверность этой конфигурации это не влияет. Тогда мы можем убрать эту строку и столбец с доски и применить индуктивную гипотезу, чтобы получить противоречие.