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

Задания

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

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

Какое наименьшее количество натуральных чисел от 1 до 320 нужно покрасить в красный цвет, чтобы 1 и 320 были красными, а также для любого красного числа a, большего 1, нашлись такие красные числа b и c (возможно, одинаковые), что $a = b плюс c?$

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

Решение.

Пусть окрашено n чисел. Упорядочим их по возрастанию:

$1=a_1 меньше a_2 меньше \ldots меньше a_n=320.$

Заметим, что для любого $k принадлежит левая фигурная скобка 2, \ldots, n правая фигурная скобка$ справедливо неравенство $a_k меньше или равно 2 a_k минус 1.$ Действительно, в противном случае при $i, j меньше k,$ имеем

$a_k больше 2 a_k минус 1 больше или равно a_i плюс a_j,$

и мы не сможем представить a_k в виде суммы двух красных чисел. Тогда

$320=a_n меньше или равно 2 a_n минус 1 меньше или равно 4 a_n минус 2 меньше или равно \ldots меньше или равно 2 в степени левая круглая скобка n минус 1 правая круглая скобка a_1=2 в степени левая круглая скобка n минус 1 правая круглая скобка .$

Значит, $n минус 1 больше или равно 9$ и $n больше или равно 10.$ Осталось привести пример покраски 10 чисел: 1, 2, 4, 5, 10, 20, 40, 80, 160, 320.

Ответ: 10.

Аналоги к заданию № 2396: 2403 Все

Олимпиада СПБГУ, 11, 10 класс, 2 тур (заключительный), 2020 год

Классификатор: Разное. Логические задачи, Разное. Оценка плюс пример, Разное. Упорядочение

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