There is a board with the shape of an equilateral triangle with side $n$ divided into triangular cells with the shape of equilateral triangles with side $ 1$ (the figure below shows the board when $n = 4$). Each and every triangular cell is colored either red or blue. What is the least number of cells that can be colored blue without two red cells sharing one side?
Problem
Source: Mathematics Regional Olympiad of Mexico Center Zone 2020 P1
Tags: combinatorics, Coloring, Equilateral
14.11.2021 12:51
Let blue=a and red=b. In any row there is $2i+1$ cells. So there should be at least $i$ a. And for the minimum case there is constraction like this: In any row write b,a,b,a,...,a,b. So the answer is $\frac{n(n-1)}{2}$
23.07.2022 02:34
The answer bellow is correct but I've found something interesting enough to share. I claim that the solution is also $\lfloor(\frac{n^{2} - 1 }{2})\rfloor - k +1$ where $n \in \{2k-1, 2k\}$ and $k \ge 1$. First you can observe that intuitively the distribution of colors in the figures are almost evenly distributed since there are just two colors. Moreover the constrain of the problem forces you to have each row in the form $ b, a, b, a, ..., a, b$ just like the solution above. So, in each row of lenght $2m + 1$ there must necesseraly be $\lceil(\frac{2m+1}{2})\rceil $ red triangles and $\lfloor(\frac{2m+1}{2})\rfloor$ blue triangles. Now since each row is a consecutive odd number, there are exactly $n^2$ triangles in a big triangle of side lenght $n$. You can prove by induction that there are always $\lfloor(\frac{n^{2} - 1}{2})\rfloor + k$ red triangles and $\lfloor(\frac{n^{2} - 1}{2})\rfloor + 1 - k$ blue triangles in each configuartion. More precisely you can divide the proof into the cases when $n$ is odd and when $n$ is even.
23.07.2022 02:37
That would in theory, also prove the indentity $ \frac{n(n-1)}{2} =\lfloor(\frac{n^{2} - 1}{2})\rfloor + 1 - k$ for each integer $n$ $ \in \{2k-1,2k\}$ and integer $k$