Разделы 
Дополнительно
Задача по математике - 1865
2019-01-21 
В клетках таблицы $10 \times 10$ расставлены числа $1, 2, 3, \cdots, 100$ так, что сумма любых двух соседних чисел не превосходит $S$. Найдите наименьшее возможное значение $S$. (Числа называются соседними, если они стоят в клетках, имеющих общую сторону).
Решение:
Пример расстановки, для которой $S = 106$, приведен на рис.
Докажем теперь, что $S \geq 106$ для любой расстановки чисел в таблице. Нам понадобится следующая лемма.
Лемма. Если в прямоугольнике $2 \times 10$ отмечено $n < 9$ попарно не соседних клеток, то число (неотмеченных) клеток прямоугольника, соседних с отмеченными, больше $n$.
Доказательство. В каждом из 10 прямоугольничков $1 \times 2$, длинные стороны которых параллельны коротким сторонам прямоугольника $2 \times 10$, отмечено не более одной клетки. Если одна клетка в таком прямоугольничке отмечена, то другая - неотмеченная, соседняя с отмеченной. Тем самым уже имеем $n$ таких клеток, а поскольку $n \leq 9,$ то (при $n \geq 1$) найдется, очевидно, и клетка, принадлежащая прямоугольничку $1 \times 2$ без отмеченных клеток, граничащая с отмеченной клеткой соседнего прямоугольничка $1 \times 2$. Следовательно, общее число неотмеченных клеток, соседних с отмеченными, больше $n$. Лемма доказана.
Допустим, что $S \leq 105$ для некоторой расстановки чисел. Стерев все числа в таблице, будем вписывать их на прежние места, начиная с числа 100 в порядке убывания.
Выделим в таблице пять неперекрывающихся горизонтальных полос $10 \times 2$ клетки и пять неперекрывающихся вертикальных полос $2 \times 10$ клеток. Зафиксируем число $n_0$, после вписывания которого впервые либо в каждой горизонтальной, либо в каждой вертикальной полосе окажется не меньше одного вписанного числа; соответствующий момент назовем критическим. Пусть уже вписаны 33 числа от 100 до 68, но есть пустые горизонтальная и вертикальная полосы. Те 64 клетки таблицы, которые не входят в эти полосы, можно разбить на 32 прямоугольничка $1 \times 2$; хотя бы в одном из них окажутся два вписанных числа с суммой, не меньшей, чем $68 + 69 > 105$. Отсюда следует, что $n_0 \geq 68$, и все числа - несоседние.
Заметим, что в критический момент в каждую из полос вписано меньше 10 чисел (если бы нашлась, например, горизонтальная полоса, в которую вписано ровно 10 чисел, то перед вписыванием числа $n_0$ в ней было бы не меньше 9 чисел, в силу чего в каждой из вертикальных полос было бы минимум по одному числу, что противоречит определению числа $n_0$). Поэтому к полосам того направления, в которых в критический момент оказалось хотя бы по одному числу, можно применить лемму.
Поскольку в критический момент в таблицу вписано $101 - n_0$ чисел, из леммы следует, что у клеток, куда они вписаны, есть не менее $(101 - n_0) + 5 = 106 - n_0$ пустых соседних. Нам предстоит, таким образом, вписать в таблицу число, которое не меньше, чем $106 - n_0$, причем рядом с числом, которое не меньше, чем $n_0$. Сумма этих двух чисел будет не меньше, чем $106 - n_0 + n_0 = 106$, что противоречит нашему предположению о том, что $S \leq 105$.
Ответ. 106.
В клетках таблицы $10 \times 10$ расставлены числа $1, 2, 3, \cdots, 100$ так, что сумма любых двух соседних чисел не превосходит $S$. Найдите наименьшее возможное значение $S$. (Числа называются соседними, если они стоят в клетках, имеющих общую сторону).
Решение:
Пример расстановки, для которой $S = 106$, приведен на рис.
Докажем теперь, что $S \geq 106$ для любой расстановки чисел в таблице. Нам понадобится следующая лемма.
Лемма. Если в прямоугольнике $2 \times 10$ отмечено $n < 9$ попарно не соседних клеток, то число (неотмеченных) клеток прямоугольника, соседних с отмеченными, больше $n$.
Доказательство. В каждом из 10 прямоугольничков $1 \times 2$, длинные стороны которых параллельны коротким сторонам прямоугольника $2 \times 10$, отмечено не более одной клетки. Если одна клетка в таком прямоугольничке отмечена, то другая - неотмеченная, соседняя с отмеченной. Тем самым уже имеем $n$ таких клеток, а поскольку $n \leq 9,$ то (при $n \geq 1$) найдется, очевидно, и клетка, принадлежащая прямоугольничку $1 \times 2$ без отмеченных клеток, граничащая с отмеченной клеткой соседнего прямоугольничка $1 \times 2$. Следовательно, общее число неотмеченных клеток, соседних с отмеченными, больше $n$. Лемма доказана.
Допустим, что $S \leq 105$ для некоторой расстановки чисел. Стерев все числа в таблице, будем вписывать их на прежние места, начиная с числа 100 в порядке убывания.
Выделим в таблице пять неперекрывающихся горизонтальных полос $10 \times 2$ клетки и пять неперекрывающихся вертикальных полос $2 \times 10$ клеток. Зафиксируем число $n_0$, после вписывания которого впервые либо в каждой горизонтальной, либо в каждой вертикальной полосе окажется не меньше одного вписанного числа; соответствующий момент назовем критическим. Пусть уже вписаны 33 числа от 100 до 68, но есть пустые горизонтальная и вертикальная полосы. Те 64 клетки таблицы, которые не входят в эти полосы, можно разбить на 32 прямоугольничка $1 \times 2$; хотя бы в одном из них окажутся два вписанных числа с суммой, не меньшей, чем $68 + 69 > 105$. Отсюда следует, что $n_0 \geq 68$, и все числа - несоседние.
Заметим, что в критический момент в каждую из полос вписано меньше 10 чисел (если бы нашлась, например, горизонтальная полоса, в которую вписано ровно 10 чисел, то перед вписыванием числа $n_0$ в ней было бы не меньше 9 чисел, в силу чего в каждой из вертикальных полос было бы минимум по одному числу, что противоречит определению числа $n_0$). Поэтому к полосам того направления, в которых в критический момент оказалось хотя бы по одному числу, можно применить лемму.
Поскольку в критический момент в таблицу вписано $101 - n_0$ чисел, из леммы следует, что у клеток, куда они вписаны, есть не менее $(101 - n_0) + 5 = 106 - n_0$ пустых соседних. Нам предстоит, таким образом, вписать в таблицу число, которое не меньше, чем $106 - n_0$, причем рядом с числом, которое не меньше, чем $n_0$. Сумма этих двух чисел будет не меньше, чем $106 - n_0 + n_0 = 106$, что противоречит нашему предположению о том, что $S \leq 105$.
Ответ. 106.
