26th Junior Balkan Mathematical Olympiad | JBMO 2022 - Problem 4

Problem 4

We call an even positive integer $n$ nice if the set $\{1, 2, \dots, n\}$ can be partitioned into $\frac{n}{2}$ two-element subsets, such that the sum of the elements in each subset is a power of $3$ . For example, $6$ is nice, because the set $\{1, 2, 3, 4, 5, 6\}$ can be partitioned into subsets $\{1, 2\}$ , $\{3, 6\}$ , $\{4, 5\}$ . Find the number of nice positive integers which are smaller than $3^{2022}$ .

Solution

Let $P(k)$ be the number of nice $n$ smaller than $3^k$ and $T(k)$ be the set including the nice $n$ smaller than $3^k$ .

Easily we get $P(1)=1, P(2)=3, P(3)=7$ .

Lemma 1: $n=3^k - 1$ is always nice.
Proof: Pair the numbers as following: $(3^k - 1,1), (3^k - 2, 2) ....$ , done.

Lemma 2: $n=3^{k+1} - m - 1, m \in T(k)$ is always nice.
Proof: Pair the numbers ${m+1, m+2 .... , 3^{k+1} - m - 1}$ as we did above. Now the numbers left are ${1,2...,m}$ and $m$ is nice, done.

Induction $Q(k)$ : The only nice $n$ for each $k \geq 2$ are $l$ :
1) $l=m, m \in T(k-1)$
2) $l=3^k -1$
3) $l=3^k - m - 1, m \in T(k-1)$

For $k=2$ just do the handwork.
Let $Q(k)$ be true for $k=j$
For $k=j+1$ :
Obviously these numbers work due to the lemmas. If there exists another number $l$ so that $l \in T(j+1)$ , then $l > 2 \cdot 3^j$ (why?), and also $3^{j+1} - l - 1$ is good.
But $3^{j+1} - l - 1 < 3^j$ and therefore due to $Q(j)$ it must be $3^{j+1} - l -1\in T(j)$ , which is clearly absurd. Done.

Now by counting the number of these 3 cases of nice numbers we get that $P(1)=1$ and by straightforward induction $P(n)=2P(n-1) + 1, \forall n \geq 2$ .
Solving the recurrence relation we get that $P(n)=2^n - 1 \implies P(2022) = 2^{2022} - 1$ .