Maths Olympiad Prep

Library / /14 of 520

Combinatorics Difficulty 6.1 National olympiad Find the answer

It is known that there are 33 buildings in the same shape which are located in an equilateral triangle. Each building has a 20152015 floor with each floor having one window. In all three buildings, every 11st 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 1010th floor can see the colors of the 99th and 1010th floor windows for the other buildings (a total of 44 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 11 window of each color. How many ways are there to color those windows?

Solution

1. Define the problem and notation:
- We have three buildings AA, BB, and CC each with 2015 floors.
- Each floor has one window, and each window can be colored red (1), green (2), or blue (3).
- Residents on the kk-th floor can see the colors of the windows on the kk-th and (k1)(k-1)-th floors of the other two buildings.
- We need to color the windows such that each resident can see at least one window of each color.

2. **Analyze the possible configurations for the kk-th floor:**
- Denote the colors of the windows on the kk-th floor as Tk=(ak,bk,ck)T_k = (a_k, b_k, c_k).
- We need to determine the possible values for Tk+1=(ak+1,bk+1,ck+1)T_{k+1} = (a_{k+1}, b_{k+1}, c_{k+1}).

3. **Case 1: TkT_k contains a single color:**
- Assume Tk=(1,1,1)T_k = (1, 1, 1).
- Each pair (ak+1,bk+1)(a_{k+1}, b_{k+1}), (bk+1,ck+1)(b_{k+1}, c_{k+1}), (ak+1,ck+1)(a_{k+1}, c_{k+1}) must contain both numbers 2 and 3, which is impossible.
- Hence, no solution for Tk+1T_{k+1} in this case.

4. **Case 2: TkT_k contains 2 distinct colors:**
- Assume Tk=(1,1,2)T_k = (1, 1, 2).
- The possible solutions for Tk+1T_{k+1} are (2,3,3)(2, 3, 3) and (3,2,3)(3, 2, 3).

5. **Case 3: TkT_k contains 3 distinct colors:**
- Assume Tk=(1,2,3)T_k = (1, 2, 3).
- The possible solutions for Tk+1T_{k+1} are (2,3,1)(2, 3, 1) and (3,1,2)(3, 1, 2).

6. Conclusion for valid configurations:
- For a valid configuration of TkT_k (2 or 3 distinct colors), there are exactly 2 possible configurations for Tk+1T_{k+1}.

7. Calculate the number of ways to color the windows:
- The number of ways to color the windows is N=n122014N = n_1 \cdot 2^{2014}, where n1n_1 is the number of valid configurations for T1T_1.

8. **Count the valid configurations for T1T_1:**
- For 2 distinct colors:
- Use twice the color xx and once the color yy, where x,y{1,2,3}x, y \in \{1, 2, 3\} and xyx \neq y.
- There are 6 possible ordered pairs (x,y)(x, y) and for each (x,y)(x, y) there are 3 triplets (x,x,y)(x, x, y), (x,y,x)(x, y, x), (y,x,x)(y, x, x).
- Hence, there are n2=63=18n_2 = 6 \cdot 3 = 18 possible triplets T1T_1 with 2 distinct colors.
- For 3 distinct colors:
- There are n3=3!=6n_3 = 3! = 6 possible triplets T1T_1.
- Therefore, n1=n2+n3=18+6=24n_1 = n_2 + n_3 = 18 + 6 = 24.

9. Final calculation:
- The number of ways to color the windows is N=2422014N = 24 \cdot 2^{2014}.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.