Наименьшее значение суммы соседних чисел 10x10 — олимпиадная задача Храмцова

  Пример расстановки, для которой  S = 106:

  Оценка. Лемма. Если в прямоугольнике 2×10 отмечено  n ≤ 9  попарно несоседних клеток, то число (неотмеченных) клеток прямоугольника, соседних с отмеченными, больше n.

  Доказательство. В каждой из 10 вертикальных доминошек 1×2, покрывающих прямоугольник 2×10, отмечено не более одной клетки. Если одна клетка в таком прямоугольничке отмечена, то другая – неотмеченная, соседняя с отмеченной. Тем самым уже имеем n таких клеток, а поскольку  n ≤ 9,  то (при

n ≥ 1)  найдётся, очевидно, и клетка, принадлежащая доминошке без отмеченных клеток, граничащая с отмеченной клеткой соседней доминошки.   Допустим, что  S ≤ 105  для некоторой расстановки чисел. Стерев все числа в таблице, будем вписывать их на прежние места, начиная с числа 100 в порядке убывания. Выделим в таблице пять неперекрывающихся горизонтальных полос 10×2 и пять неперекрывающихся вертикальных полос 2×10. Зафиксируем число n₀, после вписывания которого впервые либо в каждой горизонтальной, либо в каждой вертикальной полосе окажется не меньше одного вписанного числа; соответствующий момент назовём критическим.

  Пусть уже вписаны 33 числа от 100 до 68, но есть пустые горизонтальная и вертикальная полосы. Те 64 клетки таблицы, которые не входят в эти полосы, можно разбить на 32 доминошки; хотя бы в одной из них окажутся два вписанных числа с суммой, не меньшей чем  68 + 69 > 105.  Отсюда следует, что

n₀ ≥ 68,  и все вписанные числа – несоседние.

  Заметим, что в критический момент в каждую из полос вписано меньше десяти чисел (если бы нашлась, например, горизонтальная полоса, в которую вписано ровно десять чисел, то перед вписыванием числа n₀ в ней было бы не меньше девяти чисел, в силу чего в каждой из вертикальных полос было бы минимум по одному числу, что противоречит определению числа n₀). Поэтому к полосам того направления, в которых в критический момент оказалось хотя бы по одному числу, можно применить лемму.

  Поскольку в критический момент в таблицу вписано  101 – n₀  чисел, из леммы следует, что у клеток, куда они вписаны, есть не менее

(101 – n₀) + 5 = 106 – n₀  пустых соседних. Нам предстоит, таким образом, вписать в таблицу число, которое не меньше чем  106 – n₀,  причём рядом с числом, которое не меньше чем n₀. Сумма этих двух чисел будет не меньше чем  106 – n₀ + n₀ = 106,  что противоречит нашему предположению о том, что  S ≤ 105.