Числа на доске – 2

Автор темы koh 
ОбъявленияПоследний пост
ОбъявлениеМатематик-алгоритмист (Vehicle Routing Problem) – удаленная работа03.06.2020 17:58
ОбъявлениеПреподаватель мехмата МГУ удостоен международной премии по математике Presburger Award28.07.2020 01:04
ОбъявлениеАктуарий в PPF Life Insurance (Junior)25.03.2021 21:35
19.11.2020 19:30
Числа на доске – 2
Условие

На доске написаны последовательные натуральные числа от 1 до 27.
За один ход разрешается стереть с доски три числа таким образом, чтобы их сумма не превышала 31 и была отлична от сумм ранее стертых троек.
Какое наибольшее количество ходов можно сделать?
Похожая задача была в одном из вариантов ЕГЭ-2016.


Пример последовательности из четырех ходов:
27 + 1 + 3 = 31
24 + 2 + 4 = 30
18 + 5 + 6 = 29
13 + 7 + 8 = 28




Ответ: 6 ходов.
Так как первоначально на доске было 27 чисел, то максимальное количество ходов не больше 9.
Допустим, действительно сделано 9 ходов, то есть использованы все 27 чисел.
Тогда сумма всех стертых чисел равна $S_{27} = 1 + 2 + … + 27 = 378$,
а сумма, полученная за 9 ходов $S_9 \leq 31 + 30 + … + 23 = 243$.
То есть $S_{27} > S_9$ – противоречие.
Аналогично для 8 ходов (24 стертых числа):
$1 + 2 + … + 24 = 275 \geq S_{24} > 31 + 30 + … + 24 = 220 \geq S_8$ – противоречие.
То же самое для 7 ходов (21 стертое число):
$1 + 2 + … + 21 = 231 \geq S_{21} > 31 + 30 + … + 25 = 196 \geq S_7$ – противоречие.
Таким образом, показано, что нельзя сделать 9, 8, 7 ходов.
Пример для 6 ходов:
1 + 12 + 18 = 31
2 + 11 + 17 = 30
3 + 10 + 16 = 29
4 + 9 + 15 = 28
5 + 8 + 14 = 27
6 + 7 + 13 = 26

Извините, только зарегистрированные пользователи могут публиковать сообщения в этом форуме.

Кликните здесь, чтобы войти