We call an even positive integer [i]nice[/i] if the set can be partitioned into two-element subsets, such that the sum of the elements in each subset is a power of . For example, is nice, because the set can be partitioned into subsets , , . Find the number of nice positive integers which are smaller than .
Solution
Consider an even positive integer . The task is to determine the number of such that can be partitioned into two-element subsets such that the sum of the elements in each subset is a power of . Such an integer is termed as "nice".
### Step 1: Pairing Elements
We begin by examining the set . We need to partition this set into pairs such that:
for some integer .
### Step 2: Power of Structure Analysis
The powers of can be expressed as:
Given that is even, the sum of all numbers from to is:
### Step 3: Nice Condition
For to be nice, the total sum should permit pairing into sums that are powers of 3. Knowing:
and since , we must ensure that for each power of , the elements and exist within the set.
### Step 4: Determining Number of "Nice" Integers
We are tasked with ensuring that can match up to various powers of 3. The key lies in understanding the binary representation that enables such a partition.
For an integer to be partitioned in such a way, must take the form:
where each term implies the possibility of partitioning into pairs for different .
### Step 5: Counting
To find the number of "nice" integers smaller than , observe that each power contributes a degree of freedom through its binary representation. Specifically, the possibility arises if:
An even can be expressed as some configuration of formed sums listed above where each contributes as a viable pairing option.
Now, every unique combination of existence or absence (binary relevant state) of a situational corresponds to an allowed . For such configurations:
There are valid combinations (as all must select at least one viable condition for pairing).
Thus, the number of nice integers smaller than is: