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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994-2013 The Math Forum