USSR Math Olympiad Puzzle

Date: 04/16/2003 at 17:48:21
From: Michael
Subject: Proofs

This is a problem I found in The USSR Math Olympiad. The version I 
have has no solutions. The problem is as follows: 

Begin with a string of 10 A's, B's, and C's, such as ABCCBABCBA. 
Underneath it, form a new row of length one letter shorter, as 
follows: between 2 letters that are different write the third letter, 
and between two letters that are the same write that same letter 
again. Continue this process until you have only one letter in the 
new row. Here is an example: 

                 ABCCBABCBA
                 CACACCAAC
                 BBBBCBAB
                 BBBAACC
                 BBCABC
                 BABCA
                 CCAB
                 CBC
                 AA
                 A

Prove that no matter what string you start with, the letters at the 
corners of the resulting triangle are either all the same or all 
different. To what other numbers could you change the 'string of 10 
letters' and still have the assertion be true?

Date: 04/17/2003 at 17:00:04
From: Doctor Peterson
Subject: Re: Proofs

Hi, Michael.

Interesting problem! I spent a little time playing with it, and 
though I can't say I have a complete proof, I found enough to 
convince myself I have the answer. I'll give you a few hints based on 
my discoveries.

First, I just looked at one sample triangle, to see if I could make a 
guess at the answer to the last question first: what size triangles 
are guaranteed to have the same property? I found that all triangles 
with 2 (of course) or 4, as well as the single 10-unit triangle, 
worked out; for other sizes, some did and some didn't. It was very 
convenient that in making one triangle of 10, I had already made so 
many smaller triangles to examine in order to find this pattern.

That discovery let me start by playing with 4's, like

    A B C C
     C A C
      B B
       B

in order to have a smaller problem to solve. It's always nice when 
you can find a smaller problem of the same type, to reduce the number 
of possibilities to try out.

At the same time, I asked myself what 2, 4, and 10 have in common, 
and I noticed that they are one more than 1, 3, and 9 -- powers of 3. 
So I had my conjecture: if you start with 3^n + 1 letters, the three 
corners will be all the same or all different.

That also suggested that 3 seemed to be an important number here. And 
we have three different letters, too. Thinking about threes gave me 
the idea to use three numbers rather than letters -- maybe base 3 
would come into this. So I switched to using 0, 1, and 2 instead of 
A, B, and C.

So now we have things like

    0 0   0 1   0 2   1 0   1 1   1 2   2 0   2 1   2 2 
     0     2     1     2     1     0     1     0     2

In fact, those are all the possibilites. Now, is there any nice way 
to express the rule numerically? Yes; in each case, the sum of the 
three numbers is a multiple of 3: if they are different, they are 
0+1+2 = 3, and if they are the same, they are 3 of the same number. I 
don't know whether you have heard of modular arithmetic, but one nice 
way to say this is that the sum of the three numbers is 0 (mod 3); so 
the number you write under the pair x,y is -(x+y) (mod 3). That is, 
add the numbers, find the remainder when you divide by 3, and 
subtract that from 3.

Now we are in a position to start using algebra. Suppose we start 
with four numbers a, b, c, and d. I'll leave you to do the rest: what 
is the bottom number going to be, in terms of these variables, and 
why will it be -(a+d) (mod 3) regardless of what b and c are?

If you take the route I took, and don't find a better shortcut, 
you'll find yourself using Pascal's triangle, among other things. I 
wouldn't be surprised if there is a much quicker, simpler way to get 
to the answer, but by describing my process rather than a neat final 
result, I think I'm giving a better picture of how math works, and of 
the fun of exploration and discovery in an interesting problem like 
this.

If you have any further questions, feel free to write back.

- Doctor Peterson, The Math Forum
  http://mathforum.org/dr.math/ 

Date: 04/17/2003 at 23:22:31
From: Michael
Subject: Proofs

Hi, Dr. Peterson.

Wow! Your method of attacking the problem was ingenious! I have a 
couple of questions concerning your solution. 

  (A) How can I prove that 3^n + 1 are the number of letters that 
      work for the given assertion? I'm guessing one can do it by 
      mathematical induction, but I'm not sure.

  (B) How can I prove that the letter at the very bottom of the 
      triangle will be -(a+z)(mod 3), where a and z are the last 
      letters one uses for the triangle with a first row of a....z?

Thank you in advance,
Michael

Date: 04/18/2003 at 08:34:25
From: Doctor Peterson
Subject: Re: Proofs

Hi, Michael.

Once you have proved it for 4, you can find a way to build up each 
successive power of 3 from the previous one (so, yes, this is 
inductive). Just make a 10-unit triangle and see how you can 
partition it into 4-unit triangles, making use of the fact that only 
the top corners affect the result at the bottom.

Again, since you just have to prove the claim from scratch for the 
4-unit case, you only have to do the algebra:

    a      b      c      d
     -(a+b) -(b+c) -(c+d)     (mod 3)

and so on. You should see it for this case pretty easily.

If you have to prove that it ONLY works for 3^n + 1, and not for 
others, you can use the same approach as for 4, and use a basic fact 
about Pascal's triangle to show that other cases can't work, or at 
least find a counterexample for each n.

- Doctor Peterson, The Math Forum
  http://mathforum.org/dr.math/