Associated Topics || Dr. Math Home || Search Dr. Math

```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
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.
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?

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/
```
Associated Topics:
High School Number Theory
High School Puzzles

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search