РЕШУ ОЛИМП: задания, ответы, решения

Задания

Версия для печати и копирования в MS Word

Тип 0 № 5770 Добавить в вариант

Даны n различных положительных чисел. Из них составляются всевозможные суммы c числом слагаемых от 1 до n.

а)  Какое наименьшее количество различных значений сумм можно получить?

б)  Какое наибольшее количество различных значений сумм можно получить?

Спрятать решение

Решение.

Можно считать, что исходные положительные числа расположены в порядке возрастания: $a_1 меньше a_2 меньше \ldots меньше a_n.$ Рассмотрим числа (см. таблицу).

a₁,	a₂,	$\ldots$	$a_n минус 2,$	$a_n минус 1,$	a_n,
$a_1 плюс a_n,$	$a_1 плюс a_n,$	$\ldots$	$a_n минус 2 плюс a_n,$	$a_n минус 1 плюс a_n,$
$a_1 плюс a_n минус 1 плюс a_n,$	$a_1 плюс a_n минус 1 плюс a_n,$	$\ldots$	$a_n минус 2 плюс a_n минус 1 плюс a_n,$
$\ldots$
$a_1 плюс a_2 плюс \ldots плюс a_n.$

Очевидно, что здесь каждое число больше предыдущего, поэтому все выписанные числа различны. Их количество

$n плюс левая круглая скобка n минус 1 правая круглая скобка плюс \ldots плюс 1= дробь: числитель: 1, знаменатель: 2 конец дроби n левая круглая скобка n плюс 1 правая круглая скобка$

соответствует требованиям задачи.

Осталось привести пример, в котором больше, чем $дробь: числитель: 1, знаменатель: 2 конец дроби n левая круглая скобка n плюс 1 правая круглая скобка$ различных сумм получить не удастся. Для этого подойдет набор из первых n натуральных чисел, из которых нельзя составить больше, чем $дробь: числитель: 1, знаменатель: 2 конец дроби n левая круглая скобка n плюс 1 правая круглая скобка$ различных сумм: эти суммы  — все натуральные числа от 1 до

$1 плюс 2 плюс \ldots плюс плюс n= дробь: числитель: 1, знаменатель: 2 конец дроби n левая круглая скобка n плюс 1 правая круглая скобка .$

6)  Числа $1, 10, 10 в квадрате , \ldots, 10 в степени левая круглая скобка n минус 1 правая круглая скобка$ дают пример n различных чисел, из которых можно образовать наибольшее количество различных сумм. Сумма любых k чисел этого набора это число, в десятичной записи которого используются только 1 и 0. Каждая такая сумма может быть представлена в виде n-элементного упорядоченного набора из 0 и 1. Поскольку на каждом месте набора могут быть только две цифры, их общее количество равно $2 умножить на 2 умножить на \ldots умножить на 2=2 в степени левая круглая скобка n правая круглая скобка .$ Единственный невозможный набор, составленный из n нулей, необходимо исключить, поэтому общее количество допустимых наборов равно $2 в степени левая круглая скобка n правая круглая скобка минус 1.$

Ответ: a) $дробь: числитель: 1, знаменатель: 2 конец дроби n левая круглая скобка n плюс 1 правая круглая скобка ;$ б) $2 в степени левая круглая скобка n правая круглая скобка минус 1.$

Спрятать критерии

Критерии проверки:

Верное решение пункта a) — 10 баллов.

Только ответ — 0 баллов.

Пример с наименьшим числом различных сумм — 5 баллов.

Верное решение пункта б) — 15 баллов.

Только ответ — 0 баллов.

Пример с наибольшим числом различных сумм — 7 баллов.

Олимпиада Казанского федерального университета, 9 класс, 2 тур (заключительный), 2019 год

Классификатор: Разное. Оценка плюс пример, Разное. Числовые таблицы

Спрятать решение · Спрятать критерии · Помощь