Maths Olympiad Prep

Library / /64 of 86

Combinatorics Difficulty 7.3 National Olympiad, round 2 Prove it United States

Problem:

Does there exist a row of Pascal's Triangle containing four distinct elements aa, bb, cc and dd such that b=2ab=2a and d=2cd=2c?

Note that the values must be distinct, so aa, bb, cc, dd must be four different numbers.

Recall that Pascal's triangle is the pattern of numbers that begins as follows

Figure 1

where the elements of each row are the sums of pairs of adjacent elements of the prior row. For example, 10=4+610 = 4 + 6. Also note that the last row displayed above contains the four elements a=5a=5, b=10b=10, d=10d=10, c=5c=5, satisfying b=2ab=2a and d=2cd=2c, but these four elements are NOT distinct.

Solution

Solution:

Yes, there are infinitely many such rows. For example,
(20368)=2(20367) and (20385)=2(20383) \binom{203}{68} = 2\binom{203}{67} \text{ and } \binom{203}{85} = 2\binom{203}{83}
There are infinitely many rows having two adjacent elements in a 1:2 ratio, for
2(nk)=(nk+1) 2\binom{n}{k} = \binom{n}{k+1}
reduces to 2(k+1)=nk2(k+1) = n - k, or n=3k+2n = 3k + 2. So as long as n2(mod3)n \equiv 2 \pmod{3}, there will be two adjacent elements in a 1:2 ratio.

Next, we search for "doubles" that are not adjacent. The next easiest case to try is
2(nk)=(nk+2) 2\binom{n}{k} = \binom{n}{k+2}
which reduces to
2(k+2)(k+1)=(nk)(nk1). 2(k+2)(k+1) = (n-k)(n-k-1).
Substitute u=nku = n - k and v=k+2v = k + 2; our equation becomes
2(v2v)=u2u 2(v^2 - v) = u^2 - u
Multiplying both sides by 4 and completing the square yields
2(4v24v+1)=4u24u+1+1, 2(4v^2 - 4v + 1) = 4u^2 - 4u + 1 + 1,
so substituting x=2v1x = 2v - 1, y=2u1y = 2u - 1 reduces the original equation to
2x2y2=1. 2x^2 - y^2 = 1.
This is a Pell's equation with infinitely many solutions which can be generated in the standard way, or we can observe that (1,1)(1,1), (5,7)(5,7) are solutions and that if (x,y)(x, y) is a solution, then (3x+2y,4x+3y)(3x + 2y, 4x + 3y) is also a solution.

It remains to show that one of these solutions produces an nn which is congruent to 22 modulo 33. Since n=x+y21n = \frac{x + y}{2} - 1, we must have x+y0(mod6)x + y \equiv 0 \pmod{6}. The first solution with this property is (5,7)(5,7), but this doesn't work, because it corresponds to n=5n = 5, and the elements of the row are 1,5,10,10,5,11, 5, 10, 10, 5, 1, so the doubles are not distinct. Generating solutions via (x,y)(3x+2y,4x+3y)(x, y) \rightarrow (3x + 2y, 4x + 3y) modulo 66, we have the repeating pattern
(1,1),(1,1),(1,1),(1,1),(1,1), (1,1), (-1,1), (-1,-1), (1,-1), (1,1), \ldots
which shows that every other solution (x,y)(x, y) has the property x+y0(mod6)x + y \equiv 0 \pmod{6}. The next solution after (5,7)(5,7) with this property will correspond to an nn large enough so that the doubles will be distinct. Specifically, the solution is (169,239)(169, 239) which corresponds to n=203n = 203, k=83k = 83.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.