Question

Какое наибольшее кол-во чисел можно выбрать из чисел 1, 2, 3, 4,...,100 так, чтобы сумма никаких трёх различных выбранных чисел не была бы равна выбранному числу. Даю 20 б.

Answer 1

Основная проблема выбора чисел - можно взять три числа, которые в сумме дадут одно из [1..100]. Но если брать большие числа, то в сумме они будут давать числа большие 100. Тогда давайте найдем три минимальных последовательных числа дающие сумму большую 100. Это 33, 34, 35. А теперь выберем все числа от 33 до 100. Это и будет ответом, ведь все возможные суммы превышают 100. А возьми мы любое число меньшее 33 и в результате некоторые суммы окажутся меньше 100, например 32 + 33 + 34 = 99.

Ответ: 68 чисел от 33 до 100.

Answer 2

Максимальное количество чисел, которое можно выбрать из чисел 1, 2, 3, 4, ..., 100, так чтобы сумма никаких трех различных выбранных чисел не была равна выбранному числу, составляет 20 чисел.

Для доказательства этого факта рассмотрим следующую конструкцию выбора чисел: выберем все четные числа от 2 до 40 (включительно) и все числа, которые являются степенью двойки (1, 2, 4, 8, 16, 32, 64). Этих чисел в сумме будет 20.

Пусть мы выбрали некоторое число из этого набора. Если это число является четным числом от 2 до 40, то его наибольший простой делитель не превышает 19, и поэтому сумма никаких трех выбранных чисел не может быть равна этому числу.

Если выбранное число является степенью двойки, то оно не может быть суммой трех выбранных чисел, так как сумма трех различных степеней двойки не может быть равна степени двойки (например, 1 + 2 + 4 = 7, но 7 не является степенью двойки).

Таким образом, мы можем выбрать 20 чисел из чисел 1, 2, 3, 4, ..., 100, так чтобы никакая сумма трех различных выбранных чисел не была равна выбранному числу.