Областная олимпиада по математике, 2019 год, 10 класс

Дано натуральное число $n > 2.$ Пусть $k$ — наименьшее натуральное число такое, что множество $\{1,3,5,\ldots ,2n-1\}$ можно разбить на два подмножества $A$ и $B$ так, что сумма элементов $A$ ровно в $k$ раз больше суммы элементов $B$. Докажите, что числа $n$ и $k$ взаимно просты.

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

Комментарии от администратора Комментарии от администратора №1.    
Решение. Пусть $p$ — наименьший простой делитель числа $n.$ Докажем, что $k=p-1,$ тогда числа $n$ и $k$ будут взаимно просты.
   Заметим, что $1+3+\ldots+(2n-1)=n^2.$ Пусть сумма элементов $B$ равна $s,$ тогда сумма элементов $A$ равна $ks.$ Значит $n^2=(k+1)s,$ отсюда $k+1|n^2$ и $k+1 > 1,$ следовательно $k+1 \ge p.$ Теперь докажем, что $k=p-1$ подходит.
   Если число $n$ четно, то $p=2.$ В этом случае нужно доказать, что множество $\{1,3,\ldots ,2n-1\}$ можно разбить на 2 части с одинаковой суммой. Докажем это индукцией по $n \ge 4.$
   База: для $n=4$ и $n=6$ подходят разбиения $\{1,7\},$ $\{3,5\}$ и $\{1,3,5,9\},$ $\{7,11\}$ соответственно.
   Предположим, что утверждение верно для $n$ и $n+2.$ Тогда для $\{1,3,\ldots ,2(n+4)-1\}$ рассмотрим разбиение $\{1,3,\ldots ,2n-1\}$ на 2 части с одинаковой суммой, и к первому множеству добавим элементы $2n+1,$ $2n+7,$ а ко второму множеству — элементы $2n+3,$ $2n+5.$ Переход доказан.
   Пусть теперь $n$ нечетно. Запишем $n=pm.$ Рассмотрим подмножество $B=\{p,3p,\ldots ,(2m-1)p\}$ множества $\{1,3,\ldots ,2n-1\}.$ Сумма элементов $B$ равна $$p+3p+\ldots+(2m-1)p=p(1+3+\ldots+(2m-1))=pm^2,$$ следовательно сумма элементов $A=\{1,3,\ldots ,2n-1\}/B$ равна $$n^2-pm^2=(pm)^2-pm^2=(p-1)pm^2.$$