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$.