26-я Балканская математическая олимпиада среди юниоров. Босния и Герцеговины, 2022 год

Назовём четное положительное число $n$ хорошим, если множество $\{1, 2, \ldots, n\}$ можно разделить на $n/2$ двухэлементные подмножества такие, что сумма элементов в каждом подмножестве является степенью числа 3. Например, число 6 является хорошим, так как множество $\{1, 2, 3, 4, 5, 6\}$ можно разделить на подмножества $\{1, 2\}$ ,$\{3, 6\}$ ,$\{4, 5\}$. Найдите количество хороших чисел, меньших $3^{2022}$.

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

Ответ: $2^{2022}-1$

Положим $k$ таким, что $3^k<n<3^{k+1}-1$ для данного хорошего $n$. Пусть при разбиении на двухэлементные подмножества, $n$ в паре с $a$, тогда их сумма больше $3^k$, но не больше $2n-1<3^{k+2}$. Значит $n+a=3^{k+1}\le 2n-1\Rightarrow n\ge\frac12(3^{k+1}+1)$

Если $x\ge 3^k$ в паре $y$, то

$$3^k<x+y<3^{k+2}\Rightarrow y=3^{k+1}-x\le 3^{k+1}-n$$ , из чего следует, что числа на отрезке $[3^{k+1}-n,n]$ сгруппированы между собой, следовательно числа $[1,3^{k+1}-n-1]$ также сгруппированы между собой, т.е. $3^{k+1}-n-1$ тоже хорошее число. Легко понять, что если $3^{k+1}-n-1$ хорошее, то $n$ хорошее.

Пусть $a_k$ - количество хороших чисел, меньших $3^k$. Из вышевыведенного факта следует, что $a_{k+1}=2a_{k}+1$(1 добавляется, поскольку требуется учесть $3^{k+1}-1$). Очевидно $a_1=1$, откуда $a_k=2^k-1$.