Maths Olympiad Prep

Library / /33 of 34

Combinatorics Difficulty 6.7 National olympiad Find the answer

We call an even positive integer nn [i]nice[/i] if the set {1,2,,n}\{1, 2, \dots, 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}\{1, 2\}, {3,6}\{3, 6\}, {4,5}\{4, 5\}. Find the number of nice positive integers which are smaller than 320223^{2022}.

A number or a short expression. Spacing and $ signs are ignored.

Solution

Consider an even positive integer n n . The task is to determine the number of such n<32022 n < 3^{2022} that 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 3 3 . Such an integer n n is termed as "nice".

### Step 1: Pairing Elements

We begin by examining the set {1,2,,n}\{1, 2, \dots, n\}. We need to partition this set into pairs {a,b}\{a, b\} such that:
a+b=3k a + b = 3^k
for some integer k k .

### Step 2: Power of 3 3 Structure Analysis

The powers of 3 3 can be expressed as:
30=1,31=3,32=9, 3^0 = 1, \, 3^1 = 3, \, 3^2 = 9, \, \ldots

Given that n n is even, the sum of all numbers from 1 1 to n n is:
S=n(n+1)2 S = \frac{n(n+1)}{2}

### Step 3: Nice Condition

For n n to be nice, the total sum S S should permit pairing into sums that are powers of 3. Knowing:
a+b=3k a + b = 3^k
and since a,b{1,2,,n} a, b \in \{1, 2, \dots, n\} , we must ensure that for each power of 3k 3^k , the elements a a and b b exist within the set.

### Step 4: Determining Number of "Nice" Integers

We are tasked with ensuring that n n can match up to various powers of 3. The key lies in understanding the binary representation that enables such a partition.

For an integer n n to be partitioned in such a way, n n must take the form:
n=(311)20+(321)21++(3λ1)2(λ1) n = (3^1 - 1) \cdot 2^0 + (3^2 - 1) \cdot 2^1 + \cdots + (3^{\lambda} - 1) \cdot 2^{(\lambda-1)}
where each term implies the possibility of partitioning into (3k1)/2\left(3^k - 1\right)/2 pairs for different k k .

### Step 5: Counting

To find the number of "nice" integers smaller than 32022 3^{2022} , observe that each power contributes a degree of freedom through its binary representation. Specifically, the possibility arises if:

An even n n can be expressed as some configuration of formed sums listed above where each 3k 3^k contributes as a viable pairing option.

Now, every unique combination of existence or absence (binary relevant state) of a situational 2k 2^k corresponds to an allowed n n . For 2022 2022 such configurations:

There are 220221 2^{2022} - 1 valid combinations (as all must select at least one viable condition for pairing).

Thus, the number of nice integers smaller than 32022 3^{2022} is:
220221 \boxed{2^{2022} - 1}

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: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.