Maths Olympiad Prep

Library / /26 of 27

Combinatorics Difficulty 9.0 IMO level Prove it Saudi Arabia

We consider all partitions of a positive integer nn into a sum of (non-negative integer) exponents of 22 (i.e. 1,2,4,8,1, 2, 4, 8, \dots). A number in the sum is allowed to repeat an arbitrary number of times (e.g. 7=2+2+1+1+17 = 2 + 2 + 1 + 1 + 1) and two partitions differing only in the order of summands are considered to be equal (e.g. 8=4+2+1+18 = 4 + 2 + 1 + 1 and 8=1+2+1+48 = 1 + 2 + 1 + 4 are regarded to be the same partition). Let E(n)E(n) be the number of partitions in which an even number of exponents appear an odd number of times and O(n)O(n) the number of partitions in which an odd number of exponents appear an odd number of times. For example, for n=5n = 5 partitions counted in E(n)E(n) are 5=4+15 = 4 + 1 and 5=2+1+1+15 = 2 + 1 + 1 + 1, whereas partitions counted in O(n)O(n) are 5=2+2+15 = 2 + 2 + 1 and 5=1+1+1+1+15 = 1 + 1 + 1 + 1 + 1, hence E(5)=O(5)=2E(5) = O(5) = 2. Find E(n)O(n)E(n) - O(n) as a function of nn.

Solutions — 2

Solution 1

Let D(n)=E(n)O(n)D(n) = E(n) - O(n). We trivially have O(1)=1O(1) = 1 and E(1)=0E(1) = 0, thus D(1)=1D(1) = -1, and E(2)=O(2)=1E(2) = O(2) = 1 (respectively 2=1+12 = 1+1 and 2=22 = 2), hence D(2)=0D(2) = 0. We will show by total induction that D(n)=0D(n) = 0 for all n>2n > 2. Assume it holds for all numbers from 22 to n1n-1. If nn is odd, a partition must contain at least one 11. Since the addition of 11 changes the parity of the number of one's it follows that E(n)=O(n1)E(n) = O(n-1) and O(n)=E(n1)O(n) = E(n-1), hence since D(n)=D(n1)=0D(n) = -D(n-1) = 0. If nn is even the partition must contain an even number 2k2k of 11s. If it contains 2k=n2k = n or 2k=n22k = n-2, then we have the unique solutions
1+1++1 and 2+1+1++1, 1+1+\cdots+1 \text{ and } 2+1+1+\cdots+1,
the first adding to E(n)E(n), the second to O(n)O(n). For other, smaller, values of kk we note that the remaining exponents are all even, and we can thus apply the inductive hypothesis to n2k2\frac{n-2k}{2}. Thus, it follows that for even nn we will also have D(n)=0D(n) = 0. This completes the proof. \square

Solution 2

Let G(x)=1+i=1D(i)xiG(x) = 1 + \sum_{i=1}^{\infty} D(i)x^i be the generating function for the sequence we desire. To count partitions with an odd number of odd-appearing exponents as negative, we will multiply those choices as negative. Thus, we have that
G(x)=(1x+x2x3+x4)(1x2+x4x6+x8)(1x4+x8x12+x16), G(x) = (1-x+x^2-x^3+x^4-\dots)(1-x^2+x^4-x^6+x^8-\dots)(1-x^4+x^8-x^{12}+x^{16}-\dots)\dots,
where the ii-term corresponds to choosing the number of times 2i12^{i-1} is represented in the partition. Taking the expression for each power series, one now finds
G(x)=11+x11+x211+x411+x8 G(x) = \frac{1}{1+x} \frac{1}{1+x^2} \frac{1}{1+x^4} \frac{1}{1+x^8} \dots
However,
G(x)1x=11x11+x11+x2=11x211+x211+x4=11x411+x411+x8==1. \begin{aligned} \frac{G(x)}{1-x} &= \frac{1}{1-x} \frac{1}{1+x} \frac{1}{1+x^2} \cdots = \frac{1}{1-x^2} \frac{1}{1+x^2} \frac{1}{1+x^4} \cdots \\ &= \frac{1}{1-x^4} \frac{1}{1+x^4} \frac{1}{1+x^8} \cdots = \cdots = 1. \end{aligned}
Thus, G(x)=1xG(x) = 1-x from which it follows that D(1)=1D(1) = -1 and D(n)=0D(n) = 0 for all n>1n > 1. \square

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 and solution reproduced as published; topic and difficulty added by this site.