Районная олимпиада, 2018-2019 учебный год, 8 класс

Множество $A$ состоит из целых чисел, его наименьший элемент равен 1, а наибольший — 100. Каждый элемент $A,$ кроме 1, равен сумме двух (возможно, равных) чисел из $A.$ Укажите среди всех множеств $A,$ удовлетворяющих этим условиям, множество с минимальным числом элементов.

Комментарий/решение

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

1+1=2

2+2=4

4+4=8

8+8=16

16+16=32

32+32=64

64+64 уже будеть больше наибольшего число так что берем два большых чисел которые не равны 64+32=96, а 100-96=4 нам нужно добавить 4 он есть так что можна

1+1=2 так далее до 32+32=64

Мы делаем 64+4=68 а теперь 32+68=100

Ответ:1;2;4;8;16;32;64;68;100

Всего 9 элементов