Some blue and red circular disks of identical size are packed together to form a triangle. The top level has one disk and each level has 1 more disk than the level above it. Each disk not at the bottom level touches two disks below it and its colour is blue if these two disks are of the same colour. Otherwise its colour is red. Suppose the bottom level has 2048 disks of which 2014 are red. What is the colour of the disk at the top?
Problem
Source:
Tags: induction
fattypiggy123
28.06.2014 12:51
Sketch: Assign the numbers $1$ to red disks and $0$ to blue disks. Show via induction that the parity of the top disk is same as that of the sum of numbers on the $2^k$th row for any positive integer $k$.
Element118
29.06.2014 14:53
Sketch #2: If we proceed by induction, the induction hypothesis gives that parity of the $2^k$ disks row is the same as the $2^{k-1}$ disks row. Then using the first and last $2^k$ disks of the $2^{k+1}$ disks row, you can move up to the $3 \times 2^{k-1}$ disks row. Using the first and last $2^k$ disks of the $3 \times 2^{k-1}$ disks row, you can move up to the $2^k$ disks row (note that the middle $2^{k-1}$ disks of the $3 \times 2^{k-1}$ disks row are used twice, so they do not affect the parity).