petr_mankin писал(а):
Дана последовательность из n различных натуральных чисел и из сумм ровно двух этих чисел составлена новая последовательность из различных натуральных чисел. Например первая строка: 1,2,3,4 вторая строка: 3,4,5,6,7
Какое минимальное должно быть n, если вторая строка состоит из двузначных чисел оканчивающихся на 6?
Посчитаем наибольшее количество чисел во второй строке, когда в первой строке `n` чисел. Расположим все числа в первой строке по возрастанию. Первое число из первой строки со всеми остальными даёт `n-1` сумму. Следующее число даст максимум `n-2` новых сумм. Следующее число даст максимум `n-3` новых сумм. И так далее. Получается, что максимальное значение количество чисел во второй строке равно `( (2), (n) :} )`. Так как `( (2), (n) :} ) \ge 9 \Leftrightarrow n \ge 5` . Тогда чтобы получить как минимум `9` чисел во второй строке, необходимо минимум `5` чисел.
Пусть `a<b<c<d<e` - числа в первой строке. Решим систему:
`{(a+b=16), (a+c=26), (b+c=36):} \Leftrightarrow {(a=3), (b=13), (c=23):}`.
Итак, мы нашли первые три числа первой строки: `3,quad13,quad23`. Теперь уже несложно найти остальные два числа. Итак, оптимальный ряд чисел для первой строки:
`3,quad13,quad23,quad43,quad73`.
