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

For N = 0, the initial word has length 3⁰ + 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

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

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:

To complete part (b) we must address the question of whether there can be word lengths other than 3^N + 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 p^h of a prime number p that will divide evenly into a given binomial coefficient; that is, p^h divides while p^h+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

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.

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 3^N-1 + 1 satisfy (*) (that is, the letters in the three corners are either all different or all the same). Consider the triangle of size 3^N-1 + 2 whose first word begins with the letters AA and ends with CA. Then the following line contains a word of 3^N-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 3^N-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 3^N-1 + 2 to 2.3^N-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.3^N-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.3^NŠ1 + 1 and 3.3^N-1 in the same way as the triangles from 3^N-1 + 2 to 2.3^N-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.