Maths Olympiad Prep

Library / /51 of 97

Number theory Difficulty 8.0 National olympiad, round 2 Find the answer

An integer partition, is a way of writing n as a sum of positive integers. Two sums that differ only in the order of their summands are considered the same partition.
For example, 4 can be partitioned in five distinct ways:
4
3 + 1
2 + 2
2 + 1 + 1
1 + 1 + 1 + 1
The number of partitions of n is given by the partition function p(n)p\left ( n \right ). So p(4)=5p\left ( 4 \right ) = 5 .
Determine all the positive integers so that p(n)+p(n+4)=p(n+2)+p(n+3)p\left ( n \right )+p\left ( n+4 \right )=p\left ( n+2 \right )+p\left ( n+3 \right ).

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

We need to determine all positive integers n n such that
p(n)+p(n+4)=p(n+2)+p(n+3), p(n) + p(n+4) = p(n+2) + p(n+3),
where p(n) p(n) denotes the partition function, which counts the number of ways n n can be partitioned into positive integers.

To solve this, we consider the equivalent equation by setting N=n+4 N = n + 4 :
p(N)+p(N4)=p(N1)+p(N2). p(N) + p(N-4) = p(N-1) + p(N-2).

We analyze the behavior of the partition function using coarse partitions. A partition of n n is called coarse if all parts are at least three. Let q(n) q(n) denote the number of coarse partitions of n n .

By generating functions, we derive the following identity for N5 N \geq 5 :
p(N)+p(N4)p(N1)p(N2)=q(N)q(N3)q(N5)q(N7)q(N9). p(N) + p(N-4) - p(N-1) - p(N-2) = q(N) - q(N-3) - q(N-5) - q(N-7) - q(N-9) - \dots.

We then examine the cases for odd and even N N :

1. **Odd N5 N \geq 5 **:
q(N)q(N3)+q(N5)+q(N7)+, q(N) \leq q(N-3) + q(N-5) + q(N-7) + \dots,
with equality if and only if N=5,7,9 N = 5, 7, 9 .

2. **Even N N **:
- For N{6,8,10,12} N \in \{6, 8, 10, 12\} :
q(N)1=q(N3)+q(N5)+q(N7)+. q(N) - 1 = q(N-3) + q(N-5) + q(N-7) + \dots.
- For N14 N \geq 14 :
q(N)<q(N3)+q(N5)+q(N7)+. q(N) < q(N-3) + q(N-5) + q(N-7) + \dots.

From the above analysis, we find that the only solutions to the equation are N=5,7,9 N = 5, 7, 9 . Converting back to the original variable n n using N=n+4 N = n + 4 , we obtain the solutions:
n=1,3,5. n = 1, 3, 5.

The answer is: 1,\boxed{1,} 3, 5}.

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.