|
|
 |
Условие
Все клетки квадратной таблицы 100×100 пронумерованы в некотором порядке числами от 1 до 10000. Петя закрашивает клетки по следующим правилам. Вначале он закрашивает k клеток по своему усмотрению. Далее каждым ходом Петя может закрасить одну еще не закрашенную клетку с номером a, если для неё выполнено хотя бы одно из двух условий: либо в одной строке с ней есть уже закрашенная клетка с номером меньшим, чем a; либо в одном столбце с ней есть уже закрашенная клетка с номером большим, чем a. При каком наименьшем k независимо от исходной нумерации Петя за несколько ходов сможет закрасить все клетки таблицы?
Решение
Лемма. Для любых двух клеток A и B существует такая клетка C, закрасив которую, можно затем закрасить и A и B (возможно, C совпадает с A или с B).
Доказательство. Можно считать, что номер a клетки A меньше, чем номер b клетки B. Пусть D – клетка в одном столбце с A и в одной строке с B, и пусть d – её номер (возможно, D = A или D = B). Тогда, если d < a, то после закрашивания A можно последовательно закрасить D и B; если a ≤ d ≤ b, то после закрашивания D можно закрасить как A, так и B; наконец, если d > b, то после закрашивания B можно последовательно закрасить D и A. Итак, в качестве C можно выбрать одну из клеток A, B и D.
Перейдём к решению задачи. Достаточно доказать, что при k = 1 закраска всегда возможна.
Зафиксируем произвольную нумерацию клеток. Рассмотрим все способы закрашивания клеток согласно условию (при k = 1) и выберем из них тот, в котором количество закрашенных клеток максимально. Пусть в этом способе первая закрашенная клетка – A. Предположим, что при этом способе какая-то клетка B осталась незакрашенной. Тогда, выбрав по лемме соответствующую клетку C и начав закрашивание с неё, мы потом сможем закрасить B, A и, как следствие, все клетки, закрашенные в выбранном способе. Значит, всего мы закрасим хотя бы на одну клетку больше, что противоречит выбору способа.
Ответ
k = 1.
