The tip of a colorful triangle

Question

Original source: Problem 1 of British Informatics Olympiad 2017, Round 1

---

You're given a bunch of red (R), green (G), and blue (B) balls. I arrange some balls on a line. Then I ask you to complete the triangle of balls under the following simple rules, and tell me the color of the ball at the last row:

• Below two balls of the same color, place a ball of that color. (For example, a G must be placed under two G's.)
• Below two balls of different colors, place a ball of the third color. (For example, a B must be placed under a R and a G.)

If I gave you the balls "R R G B R G B B", you would place the balls like the following, and tell me "it's green":

R R G B R G B B
 R B R G B R B
  G G B R G G
   G R G B G
    B B R R
     B G R
      R B
       G

Now, I'll give you a sequence of 60,000 balls. I won't even show you all the balls' colors; the only information available to you is that it starts with 999 balls of the pattern RGB RGB RGB ... RGB, and ends with 999 balls of the pattern BGR BGR BGR ... BGR.

Using the same rules, can you guess the color of the ball on the last row? The answer is unique, and an answer with mathematical explanation is preferred.

Answer 1

This game is a modified Pascal triangle.

First,

let's look at size 4. If you were to permute all the possible inputs and look at the first ball given, last ball given, and the color of the ball on the last row, you can see they are also conforming to the rules given.

We then

try 10. We can look at this like so, since size 4 works:

 (R)* * B * * B * *(G)
   * * * * * * * * *
    * * * * * * * *
     G * * B * * R
      * * * * * *
       * * * * *
        R * * G
         * * *
          * *
          (B)
 

In fact,

this works if the number is $3^n + 1$.

Alright,

let's say the colors red, green, and blue are numbers 0, 1, and 2 respectively.

We then visualize a Pascal mod 3 and the game flipped of size 10, with the top portion being one:

     Pascal mod 3    |       The game
          1          |          1
         1 1         |         2 2
        1 2 1        |        1 2 1
       1 0 0 1       |       2 0 0 2
      1 1 0 1 1      |      1 1 0 1 1
     1 2 1 1 2 1     |     2 1 2 2 1 2
    1 0 0 2 0 0 1    |    1 0 0 2 0 0 1
   1 1 0 2 2 0 1 1   |   2 2 0 1 1 0 2 2
  1 2 1 2 1 2 1 2 1  |  1 2 1 2 1 2 1 2 1
 1 0 0 0 0 0 0 0 0 1 | 2 0 0 0 0 0 0 0 0 2
 

This result looks similar - as Pascal's formula (mod 3) is

$${{n}\choose{k}} \equiv {{n - 1}\choose{k - 1}} + {{n - 1}\choose{k}} \pmod 3$$ denoting the nth row and kth column. But what about the game?

As $1 + 0 \equiv 2 \pmod 3$ and $2 + 0 \equiv 1 \pmod 3$ for the game,
while $1 + 0 \equiv 1 \pmod 3$ and $2 + 0 \equiv 2 \pmod 3$, we want to switch the terms, and that's simple. We negate this equation. The formula for the game is then:
$${{n}\choose{k}} \equiv -\left[{{{n - 1}\choose{k - 1}} + {{n - 1}\choose{k}}}\right] \pmod 3$$
then:
$${{n}\choose{k}} \equiv -{{n - 1}\choose{k - 1}} - {{n - 1}\choose{k}} \pmod 3$$

Alright, now let's show why size 4 works. We assign each column in the first row $a, b, c, d$, and we will use the above formula.

 a         b        c         d
   -a-b       -b-c     -c-d
       a+2b+c      b+2c+d
           -a-3b-3c-d
 

We modulo by 3 the expression in the last row and we get $-a-d \pmod 3$, and that also conforms to the provided equation above.

Because the question is modified,

and 60,000 is not $3^n + 1$, we must find the highest power of 3 plus 1 that's smaller than this, which is 59050 ($3^{10} + 1$).

Subtracting 60000 to 59050 gives us 950, the (n+1)th-to-last element (starting from the first ball). We use $\bmod 3$ because of the pattern, giving us $2$.

Now, starting from the first ball which is R, and looking at the 3rd to last, which is B gives us G.
Looking at the second ball which is G, and looking at the 2nd to last, which is G gives us G.
The third ball is B, and looking at the 1st-to-last, which is R gives us G.
Since the next balls are repeating, it will be always periodic, but notice how it's always a G? That must mean the next colors, and the last row is Green!