Maths Olympiad Prep

Library / /55 of 56

Combinatorics Difficulty 7.4 National Olympiad, round 2 Prove it JBMO

Problem:

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

Solution

Solution:

For a nice number nn and a given partition of the set {1,2,,n}\{1,2, \ldots, n\} into two-element subsets such that the sum of the elements in each subset is a power of 33, we say that a,b{1,2,,n}a, b \in \{1,2, \ldots, n\} are paired if both of them belong to the same subset.

Let xx be a nice number and kk be a (unique) non-negative integer such that 3kx<3k+13^{k} \leq x < 3^{k+1}. Suppose that xx is paired with y<xy < x. Then, x+y=3sx + y = 3^{s}, for some positive integer ss. Since
3s=x+y<2x<23k+1<3k+2 3^{s} = x + y < 2x < 2 \cdot 3^{k+1} < 3^{k+2}
we must have s<k+2s < k+2. On the other hand, the inequality
x+y3k+1>3k x + y \geq 3^{k} + 1 > 3^{k}
implies that s>ks > k. From these we conclude that ss must be equal to k+1k+1, so x+y=3k+1x + y = 3^{k+1}. The last equation, combined with x>yx > y, implies that x>3k+12x > \frac{3^{k+1}}{2}.

Similarly as above, we can conclude that each number zz from the closed interval [3k+1x,x][3^{k+1} - x, x] is paired with 3k+1z3^{k+1} - z. Namely, for any such zz, the larger of the numbers zz and 3k+1z3^{k+1} - z is greater than 3k+12\frac{3^{k+1}}{2} which is greater than 3k3^{k}, so the numbers zz and 3k+1z3^{k+1} - z must necessarily be in the same subset. In other words, each number from the interval [3k+1x,x][3^{k+1} - x, x] is paired with another number from this interval. Note that this implies that all numbers smaller than 3k+1x3^{k+1} - x are paired among themselves, so the number 3k+1x13^{k+1} - x - 1 is either nice or equals zero. Also, the number 3k3^{k} must be paired with 23k2 \cdot 3^{k}, so x23kx \geq 2 \cdot 3^{k}.

Finally, we prove by induction that an=2n1a_{n} = 2^{n} - 1, where ana_{n} is the number of nice positive integers smaller than 3n3^{n}. For n=1n = 1, the claim is obviously true, because 22 is the only nice positive integer smaller than 33. Now, assume that an=2n1a_{n} = 2^{n} - 1 for some positive integer nn. We will prove that an+1=2n+11a_{n+1} = 2^{n+1} - 1. To prove this, first observe that the number of nice positive integers between 23n2 \cdot 3^{n} and 3n+13^{n+1} is exactly an+1ana_{n+1} - a_{n}. Next, observe that 3n+113^{n+1} - 1 is nice. For every nice number 23nx<3n+112 \cdot 3^{n} \leq x < 3^{n+1} - 1, the number 3n+1x13^{n+1} - x - 1 is also nice and is strictly smaller than 3n3^{n}. Also, for every positive integer y<3ny < 3^{n}, obviously there is a unique number xx such that 23nx<3n+112 \cdot 3^{n} \leq x < 3^{n+1} - 1 and 3n+1x1=y3^{n+1} - x - 1 = y. Thus,
an+1an=an+1an+1=2an+1=2(2n1)+1=2n+11 a_{n+1} - a_{n} = a_{n} + 1 \Leftrightarrow a_{n+1} = 2 a_{n} + 1 = 2(2^{n} - 1) + 1 = 2^{n+1} - 1
completing the proof.

In summary, there are 2202212^{2022} - 1 nice positive integers smaller than 320223^{2022}.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.