|
|
 |
Условие
В клетках таблицы 10×10 расставлены числа 1, 2, 3, ..., 100 так, что сумма любых двух соседних чисел не превосходит S.
Найдите наименьшее возможное значение S. (Числа называются соседними, если они стоят в клетках, имеющих общую сторону.)
Решение
Пример расстановки, для которой S = 106:
Оценка. Лемма. Если в прямоугольнике 2×10 отмечено n ≤ 9 попарно несоседних клеток, то число (неотмеченных) клеток прямоугольника, соседних с отмеченными, больше n.
Доказательство. В каждой из 10 вертикальных доминошек 1×2, покрывающих прямоугольник 2×10, отмечено не более одной клетки. Если одна клетка в таком прямоугольничке отмечена, то другая – неотмеченная, соседняя с отмеченной. Тем самым уже имеем n таких клеток, а поскольку n ≤ 9, то (при
n ≥ 1) найдётся, очевидно, и клетка, принадлежащая доминошке без отмеченных клеток, граничащая с отмеченной клеткой соседней доминошки.
Допустим, что S ≤ 105 для некоторой расстановки чисел. Стерев все числа в таблице, будем вписывать их на прежние места, начиная с числа 100 в порядке убывания. Выделим в таблице пять неперекрывающихся горизонтальных полос 10×2 и пять неперекрывающихся вертикальных полос 2×10. Зафиксируем число n0, после вписывания которого впервые либо в каждой горизонтальной, либо в каждой вертикальной полосе окажется не меньше одного вписанного числа; соответствующий момент назовём критическим.
Пусть уже вписаны 33 числа от 100 до 68, но есть пустые горизонтальная и вертикальная полосы. Те 64 клетки таблицы, которые не входят в эти полосы, можно разбить на 32 доминошки; хотя бы в одной из них окажутся два вписанных числа с суммой, не меньшей чем 68 + 69 > 105. Отсюда следует, что
n0 ≥ 68, и все вписанные числа – несоседние.
Заметим, что в критический момент в каждую из полос вписано меньше десяти чисел (если бы нашлась, например, горизонтальная полоса, в которую вписано ровно десять чисел, то перед вписыванием числа n0 в ней было бы не меньше девяти чисел, в силу чего в каждой из вертикальных полос было бы минимум по одному числу, что противоречит определению числа n0). Поэтому к полосам того направления, в которых в критический момент оказалось хотя бы по одному числу, можно применить лемму.
Поскольку в критический момент в таблицу вписано 101 – n0 чисел, из леммы следует, что у клеток, куда они вписаны, есть не менее
(101 – n0) + 5 = 106 – n0 пустых соседних. Нам предстоит, таким образом, вписать в таблицу число, которое не меньше чем 106 – n0, причём рядом с числом, которое не меньше чем n0. Сумма этих двух чисел будет не меньше чем 106 – n0 + n0 = 106, что противоречит нашему предположению о том, что S ≤ 105.
Ответ
106.
