Задача на множество чисел 3k+1 Какое наибольшее количество чисел можно выбрать из множества {1, 2, …, 2023} так, чтобы сумма
никаких двух чисел из выбранных не делилась на их разность?

Предыдущий
вопрос Следующий
вопрос

Question

Задача на множество чисел 3k+1 Какое наибольшее количество чисел можно выбрать из множества {1, 2, …, 2023} так, чтобы сумма
никаких двух чисел из выбранных не делилась на их разность?

Предыдущий
вопрос Следующий
вопрос

13 Янв 2023 в 19:41

78 +1

0

Helper · Answer 1

Давайте введем обозначения: пусть a и b - два числа из множества {1, 2, …, 2023}.
Если a и b удовлетворяют условию задачи, то мы не можем иметь сумму а + b, делящуюся на их разность a - b.
То есть a + b не должно делиться на a - b, что означает, что a + b не должно делиться на (a - b) и a - b не должно делиться на (a + b).

Правило арифметики:

(a+b) % (a-b) = 0 => a+b = k*(a-b), где k - целое число(a+b) % (a-b) = 0 => a-b = s*(a+b), где s - целое число

Исключим случаи, где (a + b) = 0, так как это невозможно (a и b не могут быть равны нулю).

Посмотрим на первое уравнение:

a+b = k(a-b),
a = ka - kb,
b = (k-1)a.

Теперь второе уравнение:

a-b = s(a+b),
a = sa + sb,
b = -sa + (s+1)*b.

Мы видим, что в обоих случаях a = b или b = -a, но такие комбинации нам не подходят.

Таким образом, все числа из множества {1, 2, …, 2023} при выборе следует рассматривать по модулю 4046 (минимальное общее кратное 2023 и 2023). Так как числа увеличились в 2 раза, достаточное условие будет выполнено. Таким образом, в нашем случае можно выбрать наибольшее количество чисел - все числа из данного множества.