Prooving a number tree

[Lepton]

It should be obvious if you get this one correct...

Prove that, in the following number tree where each number is the sum of the 3 above it (one directly above, one to the left, and one to the right), each line after the second MUST contain an even integer. You my assume that any blank spots are occupied by zeroes.

code:

---

         1


      1 1 1


   1 2 3 2 1


1 3 6 7 6 3 1


.......

---

[edited to confirm that I cannot spell "proove"]

[This message has been edited by Lepton (edited 03-30-2002 02:45 PM).]

[Bicho the Inhaler]

Yikes! I'm just posting to bring the # of replies out of the negatives (it's -1 at the moment)

[Chuck]

I think I did the dirty deed. I posted an answer, saw that it was wrong, and tried to delete it. I got an ISE so I tried again. I guess it counted both deletions.

[HappyMutant]

To prove that every line after the second contains an even integer, it is sufficient to prove that no line after the second consists only of odd integers.

I'm going to use ones and zeroes instead of large integers that are congruent to the original integer mod 2. Thus, the start of the triangle can be written:

code:

---

    1


   111


  10101


 1101011


100010001

---

The rule we use to create lines is as follows: (blank areas are zeroes)

code:

---

This:         000 001 010 100 011 101 110 111


Creates this:  0   1   1   1   0   0   0   1

---

Lemma 1) Every line is symmetrical.
This is because the rule used to create each line is symmetrical, and the beginning of the triangle is symmetrical.

Lemma 2) The center column contains only ones.
Because each line is symmetrical, the two integers to the left and right of the center integer must be the same. According to the rule, "1q1" and "0q0" both result in "q", where q is a 1 or 0. Therefore, the every integer in the center column is the same. Since some of these integers are ones, they are all ones.


We're interested in lines of all ones. What can be above such a line? Let's find out:

code:

---

 ABCDEFGH ... (line b)


11111111 ... (line a)

---

Thus A, A+B, A+B+C, C+D+E, E+F+G, etc. must all be odd. On our representation, they must be ones.

code:

---

 1001001001001001 ... (line b)


1111111111111111 ... (line a)

---

So, to produce a line of ones requires a line of 1001s.
What can be above this line? Using the same principle as above, we find only one answer:

code:

---

 11000011000011000011000011000011 ... (line c)


1001001001001001001001001001001001 ... (line b)

---

Notice that every 1 in line b is below a 0 in the line c. Due to symmetry (resulting from lemma 1), line b must have a 1 in the center, and thus a 0 must be in the center of the next line. However this contradicts lemma 2. Therefore, line c cannot result, so line b and line a cannot be created. Therefore, a line of ones cannot result, and every line (after line two) must contain an even integer.

------------------
Brunch - you'll love it. It's not quite breakfast, it's not quite lunch; but it comes with a slice of cantaloupe at the end.