It is known that there are $3$ buildings in the same shape which are located in an equilateral triangle. Each building has a $2015$ floor with each floor having one window. In all three buildings, every $1$st floor is uninhabited, while each floor of others have exactly one occupant. All windows will be colored with one of red, green or blue. The residents of each floor of a building can see the color of the window in the other buildings of the the same floor and one floor just below it, but they cannot see the colors of the other windows of the two buildings. Besides that, sresidents cannot see the color of the window from any floor in the building itself. For example, resident of the $10$th floor can see the colors of the $9$th and $10$th floor windows for the other buildings (a total of $4$ windows) and he can't see the color of the other window. We want to color the windows so that each resident can see at lest $1$ window of each color. How many ways are there to color those windows?
Problem
Source: Indonesia MO (INAMO) 2015 P8
Tags: combinatorics, Coloring
17.09.2018 10:00
$\quad$ We use the notations for colors: $\text{red}=1, \text{green}=2, \text{blue}=3$. $\quad$ Denote $A,B,C$ the buildings and $a_k$ (respectively $b_k, c_k$) the color of the window situated on the $k$-th floor of the building $A$ (respectively $B,C$). $\quad$ If the colors of the windows on the $k$-th floor forms the triplet $T_k=(a_k, b_k, c_k)$, we determine the possible values for the triplet $T_{k+1}=(a_{k+1}, b_{k+1}, c_{k+1})$, where $k\in\mathbb{N}, k\le2014$. $\quad$ $\textbf{Case 1}: T_k$ contains a single color. Assume $T_k=(1,1,1)$. Each pair $(a_{k+1}, b_{k+1}), (b_{k+1}, c_{k+1}), (a_{k+1}, c_{k+1})$ must contain the both numbers $2$ and $3$, impossible. Hence, no solution $T_{k+1}$ in this case. $\quad$ $\textbf{Case 2}: T_k$ contains $2$ distinct colors. Assume $T_k=(1,1,2)$. Result two possible solutions, $T_{k+1}\in((2,3,3), (3,2,3))$. $\quad$ $\textbf{Case 3}: T_k$ contains $3$ distinct colors. Assume $T_k=(1,2,3)$. Result two possible solutions, $T_{k+1}\in((2,3,1), (3,1,2))$. $\quad$ Conclusion: For a valid configuration of $T_k$ ($2$ or $3$ distinct colors), result exactly $2$ possible configurations for $T_{k+1}$. $\quad$ Results: The number of the ways to color the windows is $N=n_1\cdot2^{2014}$, where $n_1$ is the number of the valid configurations for $T_1$. $\quad$ For $2$ distinct colors: We use twice the color $x$ and once the color $y$, where $x,y\in\{1,2,3\}, x\ne y$. There exist $6$ possible ordered pairs $(x,y)$ and for each $(x,y)$ exist $3$ triplets $T_1$ $((x,x,y), (x,y,x), (y,x,x))$. Hence, there exist $n_2=6\cdot3=18$ possible triplets $T_1$ with $2$ distinct colors. $\quad$ For $3$ distinct colors, there exist $n_3=3!=6$ possible triplets $T_1$. $\quad$ $n_1=n_2+n_3=24=2^3\cdot3$ and results the number of the ways to color the windows: $\quad$ $N=3\cdot2^{2017}$.