31
$\begingroup$

Consider a downward-pointing triangle of letters X, Y, and Z formed by the following algorithm.

  • Start with a sequence of 10 letters each of which is X, Y, or Z.
  • Under each row, construct the next row as follows. If two adjacent letters are the same, write the same letter beneath them; if they're different, write the third letter beneath them.

A couple of examples to demonstrate:

          X Y Z Z X Z X Z X Y          Y Z X Z X Z Y Z Y Y
           Z X Z Y Y Y Y Y Z            X Y Y Y Y X X X Y
            Y Y X Y Y Y Y X              Z Y Y Y Z X X Z
             Y Z Z Y Y Y Z                X Y Y X Y X Y
              X Z X Y Y X                  Z Y Z Z Z Z
               Y Y Z Y Z                    X X Z Z Z
                Y X X X                      X Y Z Z
                 Z X X                        Z X Z
                  Y X                          Y Y
                   Z                            Y

The problem: prove that no matter what letter sequence we start with, the letters at the three vertices of the resulting triangle must always be either all the same or all different.

Bonus problem: what values can we replace 10 with (i.e. what sequence lengths can we start with) such that this is still true?

Inspired by a question from the USSR Mathematical Olympiad.

$\endgroup$
  • $\begingroup$ This could be brute-forced easily, seeing as there are at most 10^3 combinations $\endgroup$ – Areeb Sep 17 '16 at 23:33
  • $\begingroup$ @Areeb That wouldn't be a very nice proof though, would it? :-) Added the [no-computers] tag. $\endgroup$ – Rand al'Thor Sep 17 '16 at 23:39
  • $\begingroup$ @randal'thor that's true, however if I did find an algorithm that could figure out what the last three letters would be based on only the first row, I might be on to something $\endgroup$ – Areeb Sep 17 '16 at 23:41
  • 3
    $\begingroup$ It's 3^10 starting configurations, not 10^3. Fifty-nine times bigger space. That's a pretty big difference (still brute-forceable). $\endgroup$ – Nij Sep 18 '16 at 5:41
  • 1
    $\begingroup$ Call the first element X without loss of generality, and the second element either X or Y, similarly WLOG, and there are are $2 \times 3^8$ starting configurations. $\endgroup$ – h34 Sep 18 '16 at 8:41
24
$\begingroup$

We start by proving this is true when the initial row is of length 4.

A B C D
 E F G
  H I
   K

For any three numbers in the above array P, Q and R, all adjacent and in a downward triangle, the rule implies that P + Q + R = 0 (mod 3). In particular, adding up several of these downward zero triangles, we get that (where all equality from now on is mod 3)

$$(A+B+E)+(C+D+G)+(H+I+K)+\\2(B+C+F)+2(E+F+H)+2(F+G+I)=0$$ After rearranging a bit, this becomes $$ (A+D+K)+3(B+C+E+G+H+I+2F)=0 $$ But three times anything is zero mod 3, so the above equation implies $A+D+K=0$. This implies that $A, D, K$ are all the same or all different, since the only other possibility is that two are equal and one is different, but $P + P + Q$ is always nonzero mod 3 when $P\neq Q$.

When you start with 10 numbers, apply the 4 number case to the highlighted elements in the below triangle. Similarly, the 10 number case can be extended to 28, then 82, and in general to any number one more than a power of 3.

A . . B . . C . . D
 . . . . . . . . .
  . . . . . . . .
   E . . F . . G
    . . . . . .
     . . . . .
      H . . I
       . . .
        . .
         K

Edit: In case it wasn't clear, heres how the 10 case extends to the 28 case.

 A   (8 dots)   B   (8 dots)   C  (8 dots)  D

                    (8 rows)

        E   (8 dots)   G   (8 dots)   h

                    (8 rows)

                I   (8 dots)   G

                    (8 rows)

                        K
| improve this answer | |
$\endgroup$
  • 4
    $\begingroup$ This must be similar to the solution OP was looking for (it proves that any number one more than a power of 3 works, but doesn't show that those are the only ones that do). $\endgroup$ – ffao Sep 18 '16 at 1:16
  • 1
    $\begingroup$ This is indeed what I was looking for. $\endgroup$ – Rand al'Thor Sep 18 '16 at 13:08
23
$\begingroup$

Sierpinksi-like triangle mates with pachinko-like machine

Following selected funnel-shaped dependencies, a large size-10 triangle recursively breaks down into a size-4-triangle-like arrangement of medium size-4 triangles. This amounts to subdivision by a linear factor of 3. Turns out that most top-row letters have no effect on the corners that matter here.

o - o - o - o - o - o - o - o - o - o
 \ / \ / \ / \ / \ / \ / \ / \ / \ /
  o   o   o   o   o   o   o   o   o
   \ / \ /     \ / \ /     \ / \ /                     o - o - o - o
    o   o       o   o       o   o                       \ / \ / \ /
     \ /         \ /         \ /                         o   o   o                     o - o
      o - o - o - o - o - o - o      is equivalent to     \ / \ /    is equivalent to   \ /
       \ / \ / \ / \ / \ / \ /                             o   o                         o
        o   o   o   o   o   o                               \ /
         \ / \ /     \ / \ /                                 o
          o   o       o   o
           \ /         \ /
            o - o - o - o                 o - o - o - o                    o - - - - - o
             \ / \ / \ /                   \ / \ / \ /                      \         /
              o   o   o              if     o - o - o    is equivalent to    \       /
               \ / \ /                       \ / \ /                          \     /
                o   o                         o - o                            \   /
                 \ /                           \ /                              \ /
                  o                             o                                o

As a check, the relevant sub-triangles in the examples do follow the same rules as size-2 triangles.

  X Y Z Z X Z X Z X Y          X - - Z - - X - - Y          X - - - - - - - - Y
   Z X Z Y Y Y Y Y Z            \   / \   / \   /            \               /
    Y Y X Y Y Y Y X              \ /   \ /   \ /              \             /
     Y Z Z Y Y Y Z                Y - - Y - - Z                \           /
      X Z X Y Y X       --->       \   / \   /       --->       \         /
       Y Y Z Y Z                    \ /   \ /                    \       /
        Y X X X                      Y - - X                      \     /
         Z X X                        \   /                        \   /
          Y X                          \ /                          \ /
           Z                            Z                            Z


  Y Z X Z X Z Y Z Y Y          Y - - Z - - Y - - Y          Y - - - - - - - - Y
   X Y Y Y Y X X X Y            \   / \   / \   /            \               /
    Z Y Y Y Z X X Z              \ /   \ /   \ /              \             /
     X Y Y X Y X Y                X - - X - - Y                \           /
      Z Y Z Z Z Z       --->       \   / \   /       --->       \         /
       X X Z Z Z                    \ /   \ /                    \       /
        X Y Z Z                      X - - Z                      \     /
         Z X Z                        \   /                        \   /
          Y Y                          \ /                          \ /
           Y                            Y                            Y

Any top-row combination of x,y,z can be obtained by beginning with all x and converting one position at a time. Thinking of x,y,z as 0,1,2 with modulo-3 wraparound addition, here is a summary of how converting any position maintains the 3-corner rule just the same in a medium size-4 triangle as in the equivalent small size-2 triangle. (0 = no change, 1 = change to the next letter, 2 = change to the twice-next letter = change to the previous letter)

                      drop a 1 on a corner, as in a pachinko machine
                              |
                              V

0   0   0   0                 1   0   0   0
                               \ /
  0   0   0                     2   0   0                                 1   0
                   --->          \ /             which is equivalent to    \ /
    0   0                         1   0                                     2
                                   \ /
      0                             2


                          drop a 1 adjacent to a corner, like a pachinko
                                  |
                                  V

0   0   0   0                 0   1   0   0
                               \ / \ /
  0   0   0                     2   2   0                                 0   0
                   --->          \ / \ /       which is equivalent to
    0   0                         2   1                                     0
                                   \ /
      0                             0

Thanks to symmetry, only the above two cases and the following 6 representations need to be considered. (Actually, there are only 2 truly unique cases below, one where the original top corner letters are the same and one where they differ.)

        .- - - - - - - - - -.                      .- - - - - - - - - -.
     . x   x                 y   x              . x   x                 z   x
    .   \ /       --->        \ /              .   \ /       --->        \ /
    .    x                     z               .    x                     y
    .                                          .
     .  .- - - -. .- - - - -.                   .  .- - - -. .- - - - -.
       0   0     1   0       1   0                0   0     2   0       2   0
        \ /   +   \ /    =    \ /                  \ /   +   \ /    =    \ /
         0         2           2                    0         1           1



        .- - - - - - - - - -.                      .- - - - - - - - - -.
     . y   x                 x   x              . y   x                 z   x
    .   \ /       --->        \ /              .   \ /       --->        \ /
    .    z                     x               .    z                     y
    .                                          .
     .  .- - - -. .- - - - -.                   .  .- - - -. .- - - - -.
       1   0     2   0       0   0                1   0     1   0       2   0
        \ /   +   \ /    =    \ /                  \ /   +   \ /    =    \ /
         2         1           0                    2         2           1



        .- - - - - - - - - -.                      .- - - - - - - - - -.
     . z   x                 x   x              . z   x                 y   x
    .   \ /       --->        \ /              .   \ /       --->        \ /
    .    y                     x               .    y                     z
    .                                          .
     .  .- - - -. .- - - - -.                   .  .- - - -. .- - - - -.
       2   0     1   0       0   0                2   0     2   0       1   0
        \ /   +   \ /    =    \ /                  \ /   +   \ /    =    \ /
         1         2           0                    1         1           2

The effects of each addition ripple down for either no effect or for a combined effect of changing two corners in opposite directions. This preserves the required condition where all three corners are either the same or all different,

Bonus answer, incompletely justified:
The recursive effect clearly scales up by factors of 3 to include all top rows of size $n = 1{+}3^k$. Without explanation, the following diagram is a tilted representation of changing a single letter. It convinced me that this is a 3-fold Sierpinski triangle and that no further sizes will work. Each marked diagonal shows that changing a top letter (by 1) will result in a change at the diagonal's level only if the top change is at a corner. The resultant change (by 2, same as -1) will be opposite in value.

  n = 2   4          10                                  28
   . / . / . . . . . / . . . . . . . . . . . . . . . . . / . . . . . . . . . . . . . . ...
  1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 ..
 . 2 2 / 1 1 . 2 2 / 1 1 . 2 2 . 1 1 . 2 2 . 1 1 . 2 2 / 1 1 . 2 2 . 1 1 . 2 2 . 1 1 . ...
  / 1 / . 2 . . 1 / . 2 . . 1 . . 2 . . 1 . . 2 . . 1 / . 2 . . 1 . . 2 . . 1 . . 2 . . ..
   . 2 1 2 2 1 2 / . . 1 2 1 1 2 1 . . . 2 1 2 2 1 2 / . . 1 2 1 1 2 1 . . . 2 1 2 2 1 ...
    / 1 1 . 1 1 / . . . 2 2 . 2 2 . . . . 1 1 . 1 1 / . . . 2 2 . 2 2 . . . . 1 1 . 1 1 ..
     . 2 . . 2 / . . . . 1 . . 1 . . . . . 2 . . 2 / . . . . 1 . . 1 . . . . . 2 . . 2 ...
      . 1 2 1 / . . . . . 2 1 2 . . . . . . 1 2 1 / . . . . . 2 1 2 . . . . . . 1 2 1 . ..
       . 2 2 / . . . . . . 1 1 . . . . . . . 2 2 / . . . . . . 1 1 . . . . . . . 2 2 . ...
        . 1 / . . . . . . . 2 . . . . . . . . 1 / . . . . . . . 2 . . . . . . . . 1 . . ..
         . 2 1 2 1 2 1 2 1 2 2 1 2 1 2 1 2 1 2 / . . . . . . . . 1 2 1 2 1 2 1 2 1 1 2 ...
          / 1 1 . 2 2 . 1 1 . 1 1 . 2 2 . 1 1 / . . . . . . . . . 2 2 . 1 1 . 2 2 . 2 2 ..
           . 2 . . 1 . . 2 . . 2 . . 1 . . 2 / . . . . . . . . . . 1 . . 2 . . 1 . . 2 ...
            .                               / . . . . . . . . . . .
             .                             / . . . . . . . . . . . .

Further musing: Seems like some hay could be made from the fact that these triangles obey the same rules regardless of which side is considered top and which direction is considered down.

| improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ This is awesome! I hadn't thought of it in terms of Sierpinski triangles, but that's a great way of looking at it. $\endgroup$ – Rand al'Thor Sep 18 '16 at 13:09
6
$\begingroup$

Note that if you associate X,Y,Z to the elements $0,1,2$ in the ring $\mathbb {Z}/3\mathbb {Z} $, then the operation described is the linear combination $f (a,b) = -a -b $ (for the less mathematically inclined: $f(a,b)$ is the remainder of the division of $-a-b$ by 3). Therefore, the final number in the bottom corner must also be a linear combination of the starting ones.

But how much are the coefficients of this combination? Well, we can see that a number is used as many times as there are paths from its starting position to the final position moving down the board. This means that the coefficient of the $n$th number (starting from 0) is , up to sign, equal to $\binom {9}{n} $. The true coefficient must actually be $-\binom {9}{n} $, as there are 9 sign changes, making the final result negative.

This way, the bottom number is $\sum\limits_{i=0}^9 - \binom {9}{i} a_i = -a_0 - a_9$, or exactly the result of applying the operation to both initial corners.

Bonus: we need all coefficients to be zero except for the ones at the borders -- by Lucas' theorem, this happens iff n is of the form $3^k+1$. Furthermore, for there to be an odd number of sign changes, n must be even, which all of the numbers of the previous form are anyway.

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Interesting. I was thinking of blowing up the 10x10 case to a larger one of side 10+9*9=91. Either I cannot count, or 3^k+1 is not an if and only if statement. $\endgroup$ – Matsmath Sep 18 '16 at 0:32
  • 1
    $\begingroup$ @Matsmath Well, I don't think you can't count, it's more likely you made a hasty (and invalid) simplification. At least, assuming my math is right, which I think it is until someone proves otherwise :) If you have the patience for it, you can try doing a few cases for the 91-sided triangle: one of them should violate the property (81 Xs, a Y, and 9 more Xs should do it) $\endgroup$ – ffao Sep 18 '16 at 0:49
  • 1
    $\begingroup$ So I guess you did have a counting problem after all :P $\endgroup$ – ffao Sep 18 '16 at 1:18
  • 2
    $\begingroup$ Off by one errors make fools of us all :P @Matsmath $\endgroup$ – Mike Earnest Sep 18 '16 at 1:23
  • 2
    $\begingroup$ @justhalf What a coincidence, I like this too! :D It might not have the beautiful diagrams the other solutions do, but I think this is easier to reason about because it's just a sum of binomial coefficients. (It makes it easy to see and prove the answer to the bonus formally, as well -- before I posted this several other incorrect forms had been proposed). $\endgroup$ – ffao Sep 19 '16 at 7:21
5
$\begingroup$

Executive summary:

This is a mod-3 game.

You represent X, Y, and Z modulo 3. The rule given by AA->A and AB->C translates to the mod-3 function v(x,y):=2x+2y (mod 3). It is easy to see that v(x,x)=4x=x, whereas v(x,y)=2x+2y=z for all distinct x,y,z in [0,1,2]. The rule given in the puzzle means that below entries x and y you write v(x,y).

This way you build up your triangle, with starting entries in the first row x[1], x[2], ..., x[10]. Then, in the second row you will have entries 2*x[1]+2*x[2], ... , 2*x[9]+2*x[10]. Simple (all right, I am somewhat sloppy here), but automatic computation will show you, that in the last row you are ought to write

512 x[1] + 4608 x[2] + 18432 x[3] + 43008 x[4] + 64512 x[5] + 64512 x[6] + 43008 x[7] + 18432 x[8] + 4608 x[9] + 512 x[10]

which boils down to

2x[1]+2x[10]=v(x[1],x[10]), modulo 3.

That is, in the last row you put exactly a symbol following the rules, based on the two upper corners of your triangle.

Edit: to address the bonus question, thanks to multiple hints from the other answerers (@ffao and @Mike Earnest)...

I believe 10+9*8=82 is another proper case. The reasoning is that this is a blown-up triangle of many smaller triangles of side 10 each (some having common corners). You only focus on what happens on "every 10th" position, which is essentially the same as the case 10. More larger examples can be obtained this way. See @Mike Earnest's answer for a picture. This gives you examples of the form 1+9^k (so misses the observation that the n=4 case is also possible).

| improve this answer | |
$\endgroup$
  • $\begingroup$ +1, but there's a considerably more beautiful and intuitive proof than this, which also answers the bonus question (or at least gives a bunch of numbers 10 can be replaced with - it doesn't prove that that's all of them, but the latter isn't so interesting anyway). $\endgroup$ – Rand al'Thor Sep 18 '16 at 0:06
2
$\begingroup$

Read $X,Y,Z$ as $0,1,2$ and work mod 3. Call the elements in the top row $x_i$, for $1\leq i \leq 10$. The number below $x_i$ and $x_{i+1}$ is given by $-x_i-x_{i+1}$. So the second row begins

$-x_1-x_2$, $-x_2-x_3$, ... (write the first element as $-(1,1)$),

the third begins

$x_1+2x_2+x_3$, $x_2+2x_3+x_4$, ... (write the first element as $(1,2,1)$),

and the first element of row $j$ is given by $(-1)^{j+1}$ times row $(j-1)$ of the Yang Hui Triangle (later called Pascal's).

So the first element of the 10th row, which is its only element, is

$-(1, 9, 36, 84, 126, 126, 84, 36, 9, 1)$.

Reducing mod 3 gives $-(x_1+x_{10})$ as required.

Where $k$ is a power of 3, all the coefficients in the $k$th row of the Yang Hui Triangle except the first and last are multiples of 3, so the result holds for all triangles in which the number of initial elements is 1 more than a power of 3.

| improve this answer | |
$\endgroup$
2
$\begingroup$

It works for initial row length $n$:

when every entry of Pascal's Triangle for the $(n-1)^{th}$ row, except for the first and last (which are both $1$), is divisible by 3.

The final sum (thanks @Matsmath) is $\sum_\limits{k=0}^{n-1}2^{n-1}\binom{n-1}{k}x[k]$.

Modulo $3$, for such a row, all the inner entries disappear, leaving $2^{n-1} \mod 3$ (which is $\equiv 2$ as $n$ is even) times the two initial corners, $x[0]$ and $x[n-1]$.

Borrowing from @Mike Earnest:

If we label each coordinate $XYZ(n,k)$ for row $n$, entry $k$, then we have $XYZ(n,k)+XYZ(n,k+3)+XYZ(n+3,k)\equiv0\mod3$. We also have the original definition: $XYZ(n,k)+XYZ(n,k+1)+XYZ(n+1,k)\equiv0\mod3$.

From these, we can form an initial relation; we have ; $XYZ(0,0)+XYZ(0,1)+XYZ(1,0)\equiv XYZ(0,0)+XYZ(0,3)+XYZ(3,0)\equiv0\mod3$. Using the ratio between the two, I claim $XYZ(0,0)+XYZ(0,9)+XYZ(9,0)\equiv0\mod3$, and generally $XYZ(0,0)+XYZ(0,3^\alpha)+XYZ(3^\alpha,0)\equiv0\mod3$

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.