Solution to June 2001 Problem

Normand Laliberté (Ontario) and Juan Mir Pieras (Spain) used similar arguments to prove that

For an initial word of 3N + 1 letters, the letters in the corners (*)
of the resulting triangle are all the same or all different.
Here we combine their arguments to provide an answer to part (a) and a partial answer to part (b). Both solvers illustrate their arguments with examples, which we omit here; the reader is encouraged to provide examples for greater understanding, particularly for the triangles that begin with 4- or 5-letter words. Our proof proceeds by induction on the exponent N.

For N = 0, the initial word has length 30 + 1 = 2, and the claim is true by definition. It is convenient to replace the letters A, B, C by integers modulo 3. Using modular arithmetic, we see that the rule becomes

write below x and y the number - (x + y) (mod 3). To verify that this works, note that -(x + x) = -2x which is congruent to x (mod 3), while if x, y, z are in {0, 1, 2} and are all different, then - (x + y) is congruent to z (mod 3). Thus the process that moves us from one word to the next is a function f that takes a word (x0, x1, x2,..., xk) of length k + 1 to the word f(x0, x1, x2,..., xk) =(-(x0 + x1), -(x1 + x2),..., -(xk-1 + xk)) of length k below it.

Returning to the induction, we assume that (*) holds for a word of length 3K - 1+ 1 and show it follows that (*) holds for words of length 3K + 1. Just to see how the argument works, look first at the 4-letter word x0x1x2x3:

Note how the triangle of size 3+1 is divided into six overlapping triangles of size 30 + 1. This dissection generalizes to the case where the initial word has length 3K + 1 and the six overlapping triangles have initial word length 3K-1 + 1:


Thus, when x0 and are at the upper corners, -(x0 + x3N) (mod 3) is at the bottom as desired.

To complete part (b) we must address the question of whether there can be word lengths other than 3N + 1 that guarantee the conclusion of (*). To see that the answer is no, we return to the solution of Juan Mir Pieras, who discovered for himself a theorem of Kummer (from 1852) together with a couple remarkable consequences. Kummer was interested in the highest power ph of a prime number p that will divide evenly into a given binomial coefficient; that is, ph divides while ph+1 does not. To determine h one writes the numbers k and n-k in base p notation; Kummer's theorem says that h equals the number of carries in the addition k + (n - k) = n when done in p-ary arithmetic. What follows is a shortened version of Mir's approach to part (b), including his proof of Kummer's theorem for p = 3. The argument begins with a restatement of the original problem in terms of mod 3 arithmetic.

1.When the initial word (x0, x1, x2,..., xn) has length n+1 (where the xi are integers mod 3), the resulting number (at the bottom corner of the triangle) is


The proof of this claim is by a straightforward induction on n. As an immediate consequence,

2.The resulting number is congruent to - (x0 + xn) (mod 3) if and only if n is odd and the interior binomial coefficients are all divisible by 3; that is, if 3 divides for k = 1, 2,..., n-1.

Our goal is therefore to prove that the situation described in (2) happens if and only if n is a power of 3. For the proof we develop an easy way to compute the number of times n! is divisible by 3. Denote this number by F(n). (That is, divides n! while does not.) It is easy to see that

3. F(n) = (# of multiples of 3 <= n) + (# of multiples of 9 <= n) + ...


If we write n in base 3 notation,


then


Consequently, formula (3) becomes , or (after a change of indices)



Thus,

 
4.


To study the divisibility of we write the numbers n, k, n-k in ternary notation:



5. The number of times that 3 divides into equals

F(n) - F(k) - F(n-k);
this number is equal by step (4) to



or, after collecting terms, to


We are now in a position to prove Kummer's theorem for the case p = 3.


 
6.
Theorem. The total number of times 3 divides into equals the number of carries in the ternary addition k + (n - k).

In particular, we now show that the last sum in step (5) - which is the number of times 3 divides into - equals the number of carries: Set em = 1 if there is a carry from the mth place, and set em = 0 if not. (Also, set e-1 = 0.) Then
am + 3em = bm + cm + em-1.

Hence, the total number of times 3 divides into is
and this last number is the number of carries.

At last we are in a position to return to our problem and prove the desired property of the Pascal triangle taken mod 3.


 
7.
Theorem. is and only if n is a power of 3.

Proof:The theorem in step (6) tells us that 3 divides if and only if bm > am for some m - this is because for the first carry, em = 1 when bm > am, while em = 0 for all m (and there is no carry) when bm<= am for all m. Thus if n = 3N, its ternary digits am = 0 for 0 <= m < N, and consequently when bm is the leading ternary digit of k and 0 < k < N, then for that m we have bm > am. Conversely, should the mth ternary digit of am of n be nonzero and k = 3m, then bm <= am for all m and consequently is not divisible by 3.

As a consequence of step (2), this theorem completes our solution.

Comments and footnotes.
The theorems in steps (6) and (7) have been proved in many different settings. The first place to turn for learning about classical number theory results is Dickson's famous History [2]. He discusses Kummer's theorem, but apparently Kummer did not identify as the number of carries. David Singmaster provides the complete story with numerous references and considerable general information. He provides a proof of the theorems in steps (5) and (6) that is quite similar to Mir's; one sees that Mir's argument easily extends to the corresponding results for any prime, not just 3. Other proofs can be found in French and Spanish ([3] and [4]). Of course one can prove theorem (6) directly, without using theorem (5). An easy argument can be found in [1], but most readers can prove (6) for themselves just by writing out several rows of Pascal's triangle modulo 3, and noticing the obvious pattern of zeros. Once one sees the pattern, a proof by induction causes no difficulty.

Finally, one can solve the entire problem of the month by induction, without any recourse to modular arithmetic:
Return to the second figure above, and suppose that triangles of size 3N-1 + 1 satisfy (*) (that is, the letters in the three corners are either all different or all the same). Consider the triangle of size 3N-1 + 2 whose first word begins with the letters AA and ends with CA. Then the following line contains a word of 3N-1 + 1 letters that begins with A and ends with B, so that the letter C appears at the bottom corner of the resulting triangle (and this triangle fails to satisfy (*)). Similarly with a triangle of size 3N-1 + 3, if the initial word begins with AAA and ends with BAA, the second line begins with AA and ends with CA; consequently, the letter at the bottom is again C and (*) is not satisfied. Continuing in this way, from 3N-1 + 2 to 2.3N-1, it is possible to start and end the initial word with A and arrange that C appears at the bottom, contrary to (*).

Figure 2 above shows that in a triangle of size 2.3N-1 + 1, if the first word begins and ends with the letter A while B appears in the middle, then the letter at the bottom will be C. Hence it is possible to treat triangles of size between 2.3NŠ1 + 1 and 3.3N-1 in the same way as the triangles from 3N-1 + 2 to 2.3N-1. In each case one notes that we can have identical letters in the top corners while the bottom corner is different. Moreover, by rotating such a triangle 120 degrees, one gets an example of a triangle having different letters in the top corners while the bottom corner repeats one of them.

Bibliography.
[1]Lawrence O. Cannon, Locating multiples of primes in Pascal's Triangle. The College Mathematics Journal 20:4 (Sept. 1989) 324-328.
[2]Leonard Eugene Dickson, History of the Theory of Numbers, Vol. I. Chelsea Publ. 1966. (Originally published in 1919.)
[3]O.M. Fomenko, Sur quelques propriétés des coefficients binomiaux. Mathesis 69 (1960) 291-293.
[4]E. G. -Rodeja F. Una propriedad de los coefficientes binomicos. Rev. Mat. Hisp. -Amer. (4) 24 (1964) 250-253.
[5]David Singmaster, Divisibility of binomial and multinomial coefficients by primes and prime powers. A Collection of Manuscripts Related to the Fibonacci Sequence (18th Anniversary Volume of the Fibonacci Association). pp. 98-113. Fibonacci Assoc., Santa Clara CA. 1980.