Maths Olympiad Prep

Library / /3 of 7

Combinatorics Difficulty 4.7 AIME Prove it Japan

Find the number of 20-tuple (p1,p2,,p10,q1,q2,,q10)(p_1, p_2, \dots, p_{10}, q_1, q_2, \dots, q_{10}) of positive integers with p1=q10=1p_1 = q_{10} = 1 and pi+1<qipip_i+1 < q_i - p_i for all i=1,2,,9i = 1, 2, \dots, 9.

Solution

Generally, let SnS_n be the number of 2n2n-tuple (p1,p2,,pn;q1,q2,,qn)(p_1, p_2, \dots, p_n; q_1, q_2, \dots, q_n) of positive integers with p1=qn=1p_1 = q_n = 1 and pi+1qipiqi+1=1p_{i+1}q_i - p_iq_{i+1} = 1 for all i=1,2,,n1i = 1, 2, \dots, n-1. We use semicolons to make the boundary simple.
Let (p1,p2,,pn;q1,q2,,qn)(p_1, p_2, \dots, p_n; q_1, q_2, \dots, q_n) a tuple with the desired conditions. We first prove that there uniquely exists ii such that pi=qi=1p_i = q_i = 1.
Assume that there does not exist such ii. Then q11q_1 \neq 1 and pn1p_n \neq 1.

Since the sequence pj/qjp_j/q_j is increasing, there exists jj such that
pjqj<1<pj+1qj+1. \frac{p_j}{q_j} < 1 < \frac{p_{j+1}}{q_{j+1}}.
But then
pj+1qj+1pjqj1qj+1+1qj2qjqj+1, \frac{p_{j+1}}{q_{j+1}} - \frac{p_j}{q_j} \ge \frac{1}{q_{j+1}} + \frac{1}{q_j} \ge \frac{2}{q_j q_{j+1}},
hence pj+1qjpjqj+12p_{j+1}q_j - p_jq_{j+1} \ge 2, a contradiction. So there exists ii such that pi=qi=1p_i = q_i = 1. Uniqueness is clear.

Now we consider the number of tuples which meets the condition for fixed ii such that pi=qi=1p_i = q_i = 1.

(1) Case i=1i=1:
Assume that (1,p2,,pn;1,q2,,qn)(1, p_2, \dots, p_n; 1, q_2, \dots, q_n) meets the condition. Let pj=pjqjp'_j = p_j - q_j. Then the 2(n1)2(n-1)-tuple (p2,p3,,pn1;q2,q3,,qn)(p'_2, p'_3, \dots, p'_{n-1}; q_2, q_3, \dots, q_n) meets the condition.
Conversely, assume that a 2(n1)2(n-1)-tuple (p1,,pn1;q1,,qn1)(p_1, \dots, p_{n-1}; q_1, \dots, q_{n-1}) meets the condition. Let pj=pj+qjp'_j = p_j + q_j. Then (1,p1,p2,,pn1;1,q1,q2,,qn1)(1, p'_1, p'_2, \dots, p'_{n-1}; 1, q_1, q_2, \dots, q_{n-1}) meets the condition.
Since each of these two operations gives the inverse of the other, it follows that the number of 2n2n-tuples with p1=q1=1p_1 = q_1 = 1 which meets the condition is equal to Sn1S_{n-1}.

(2) Case 1<i<n1 < i < n:
Assume that (p1,,pi1,1,pi+1,,pn;q1,,qi1,1,qi+1,,qn)(p_1, \dots, p_{i-1}, 1, p_{i+1}, \dots, p_n; q_1, \dots, q_{i-1}, 1, q_{i+1}, \dots, q_n) meets the condition. Let qj=qjpjq'_j = q_j - p_j and pj=pjqjp''_j = p_j - q_j. Then two tuples (p1,,pi1;q1,,qi1)(p_1, \dots, p_{i-1}; q'_1, \dots, q'_{i-1}) and (pi+1,,pn;qi+1,,qn)(p''_{i+1}, \dots, p''_n; q_{i+1}, \dots, q_n) meet the condition.
Conversely, assume that a 2(i1)2(i-1)-tuple (p1,,pi1;q1,,qi1)(p_1, \dots, p_{i-1}; q_1, \dots, q_{i-1}) and a 2(ni)2(n-i)-tuple (p~1,,p~ni;q~1,,q~ni)(\tilde{p}_1, \dots, \tilde{p}_{n-i}; \tilde{q}_1, \dots, \tilde{q}_{n-i}) meet the condition. Let qj=pj+qjq'_j = p_j + q_j and p~j=p~j+q~j\tilde{p}''_j = \tilde{p}_j + \tilde{q}_j. Then (p1,,pi1,1,p~1,,p~ni;q1,,qi1,1,q~1,,q~ni)(p_1, \dots, p_{i-1}, 1, \tilde{p}''_1, \dots, \tilde{p}''_{n-i}; q'_1, \dots, q'_{i-1}, 1, \tilde{q}_1, \dots, \tilde{q}_{n-i}) meets the condition.
Since each of these two operations gives the inverse of the other, it follows that the number of 2n2n-tuples with pi=qi=1p_i = q_i = 1 which meets the condition is equal to Si1SniS_{i-1}S_{n-i}.

(3) Case i=ni = n:
Thinking similarly to the case i=1i=1, the number of 2n2n-tuples with pn=qn=1p_n = q_n = 1 which meets the condition is equal to Sn1S_{n-1}.

From arguments above, we obtain a recursive relation
Sn=Sn1+S1Sn2++Sn2S1+Sn1. S_n = S_{n-1} + S_1 S_{n-2} + \dots + S_{n-2} S_1 + S_{n-1}.
With this formula and the initial value S1=1S_1 = 1, we can compute and get S10=16796S_{10} = 16796.

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.