Proposed by Jason Prodromidis, Greece In this year's contest 3 problems were authored by Jason (also the author of Balkan MO 2022 Problem 3), which is a feat that to my knowledge has never been attained before!

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

Orestis_Lignos wrote: Proposed by Jason Prodromidis, Greece In this year's contest 3 problems were authored by Jason (also the author of Balkan MO 2022 Problem 3), which is a feat that to my knowledge has never been attained before! Actually Gerhard Woeginger proposed 3 problems for IMO 2014

sarjinius wrote: 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}$. Solved with Knty2006. Call a number oneless if all its digits in ternary representation are either $0$ or $2$. Main claim: $2n$ is nice if and only if it is oneless. Proof. We use induction. This is obviously true for $2n=2,4$. Suppose it is true for all even numbers $<2n$. Let the largest power of 3 in the ternary representation of $2n$ be $3^k$. Since $3^k$ must pair with a number that sums to a power of $3$, it must be paired with $2\times 3^{k}$. This implies that $2n\ge 2\times 3^k$. Let $n=2\times 3^k+t$. Due to size issues, all numbers $a$ between $2\times 3^k+t$ and $3^k$ must be paired with $3^{k+1}-a$. This essentially fixes the pairs that all numbers $\ge 3^k-t$ can be in. Hence, $2n$ is nice if and only if $3^k-t-1$ is. Note that if $2n$ is oneless, then $t$ is also oneless. Notice that $3^k-1$ only has $2$s in its ternary representation. Hence, $(3^k-1)-t$ is also oneless. The same logic applies the other way. Hence, the claim is proven by induction. To finish, note that numbers $<3^{2022}$ have at most $2022$ digits in base 3. Since each of the digits are either $0$ or $2$ (and not all are $0$), there are $2^{2022}-1$ numbers in this range.

I think this problem is too easy for JBMO p4. I think it is suitable for p1 or p2 max.

the_game_master wrote: I think this problem is too easy for JBMO p4. I think it is suitable for p1 or p2 max. It might not be difficult in terms of catching the idea to solve it. However, it involves some technical difficulty. Compared to all other problems it is clearly the most difficult one.

I think, it's just what is proper for JBMO p4. And, I don't think that catching the idea is pretty easy. They are juniors after all. Suppose, one have partitioned the integers $\{1,2,\dots,n\}$ as required. For any pair $\{a_i,b_i\}$ mark the midpoint of the interval $[a_i,b_i]$, that is, the point $m=(a_i+b_i)/2$. Since $a_i+b_i=2m$ is a power of $3$, all the marked points are among $\frac{3^k}{2},k=1,2,\dots.$ It's an easy observation that all the integers inside $[0,n]$ must be covered with closed intervals $[m-r, m+r]$ centered at the points $m=3^k/2,k=1,2\dots$ and a very important condition... these centered intervals must not intersect any negative number (because the pairing is impossible in that case, we pair only positive integers). That's it! So, the configuration on the picture bellow is not good - in this case no centered interval at $3^k/2$ can cover $n$. So, the last number of the form $3^k/2$ inside $[0,n]$ must be greater than $n/2$. Further, the same should hold for $3^{k-1}/2$ if we delete all the numbers in the interval centered at $3^k/2$ and which right end is $n$. This observation (calculations are needed of course, but this is the right trail) implies that all the ternary digits of $n$ should be among $\{0,2\}$. And, this also gives us a way to do the matching.

Obviously $n$ is even Claim 1: All the nice numbers can be represented as: 1)$3^k-1$ 2)$3^k-x-1$ where $x$ is another smaller nice number Let $k \in \mathbb{N}$ be a number such that $3^k<n<3^{k+1}\implies$ the maximum sum in a subset is $3^{k+1}\implies$ all numbers greater than or equal to $3^k$ are in a subset with sum $3^{k+1}$ $\implies n$ must be grouped with $3^{k+1}-n$, $n+1$ must be grouped with $3^{k+1}-(n+1)$, $n+2$ must be grouped with $3^{k+1}-(n+2)$, $\cdot\cdot\cdot$, $\frac{3^{k+1}+n-1}{2}$ must be grouped with $\frac{3^{k+1}+n+1}{2}$ If $n\leq \frac{3^{k+1}-1}{2}$ such a grouping is not possible because $3^{k+1}-n$ is not in the set $\implies n$ is not nice If $\frac{3^{k+1}+1}{2}\leq n<2\cdot 3^k$ after the grouping there remains an ungrouped number $3^{k+1}-n-1>3^k\implies n$ is not nice If $2\cdot 3^k\leq n<3^{k+1}-1$ after the grouping the numbers $1$, $2$, $3$, $\cdot\cdot\cdot$, $3^{k+1}-n-1$ remain ungrouped. Note that $3^{k+1}-n-1<3^k<n$ $\implies n$ is nice if and only if $3^{k+1}-n-1$ is nice If $n=3^{k+1}-1$ then all the numbers are grouped $\implies n$ is nice Let $a_k$ be the number of nice numbers less than $3^k$ $a_{k+1}=2\cdot a_k+1$ for $k\in\mathbb{N}$ and $a_1=1$ I will prove that $a_k=2^k-1$ by induction. Base: $k=1$ We will assume that $a_k=2^k-1$ $\implies a_{k+1}=2\cdot (2^k-1)+1=2^{k+1}-1$ Induction proof is finished $a_{2022}=2^{2022}-1$

We can group the set into subsets of the form $\{a,a+1,a+2\cdots,b\}$ with outer elements $a$ and $b$ where $a<b$ and $a+b$ is a power of 3 where we pair the elements using Gauss' Idea. This must be true since the largest element in the set $\{1,2,3\cdots,n\}$ must pair with $3^{k+1}-n$ where $3^k<n<3^{k+1}$, from which $n-1$ must pair with $3^{k+1}-n+1$ and so on. Once we run out of numbers that sum to $3^{k+1}$, we do the same process with the remaining numbers in the set. This process is mandatory. If we work backwards, then the subsets must be $\{1,2\cdots(3^{a_1}-1)\}, \{3^{a_1}, 3^{a_1}+1,\cdots{3^{a_2}-3^{{a_1}}}\},\{{3^{a_2}-3^{{a_1}}}+1, {3^{a_2}-3^{{a_1}}}+2\cdots{3^{a_3}-{(3^{a_2}-3^{{a_1}}}+1)}\}\cdots$ where $\{a_1,a_2\cdots{a_s}\}$ is a strictly increasing sequence of positive integers with $s$ not exceeding $2022$ and all $a_i\in\{1,2,3\cdots2022\}$. Note that all of these subsets must have outer elements that sum to distinct powers of 3 since even the 2 largest elements in a subset, say $b$ and $b-1$, will sum to $2b-1<3^{k+1}$ if $3^{k-1}<b<3^{k}$. Therefore, we are just looking for the number of ways to choose a nonempty subset from $\{1,2,3\cdots2022\}$ to assign the values that outer elements of a subset will sum to. There are $\sum_{i=1}^{2022}{\binom{2022}{i}}=2^{2022}-1$ ways. Therefore, there are $2^{2022}-1$ positive integers.

the_game_master wrote: I think this problem is too easy for JBMO p4. I think it is suitable for p1 or p2 max. Actually, it was considered to be the hardest problem on the whole exam, and those who solved it (or were close to) were revered. Also, our team leader (and other professors) taught us basic induction and told us that we probably don’t need it.

I would say second easiest on the exam tbh, I struggled solving 3 but not this.