The numbers $1$ to $15$ are each coloured blue or red. Determine all possible colourings that satisfy the following rules: • The number $15$ is red. • If numbers $x$ and $y$ have different colours and $x + y \le 15$, then $x + y$ is blue. • If numbers $x$ and $y$ have different colours and $x \cdot y \le 15$, then $x \cdot y$ is red.
Problem
Source: Dutch MNO 2018 p2
Tags: combinatorics, Coloring
13.09.2019 22:22
Denote $c_k$ the color of the number $k\in\{1,2,\dots,15\}$; $A=\{k\in\{1,2,\dots,15\}|c_k=\text{red}\}; B=\{k\in\{1,2,\dots,15\}|c_k=\text{blue}\}$. A solution is: all the numbers are red. Next, we study the case: at least a number is blue. Then exists at least a number $k\ge2$ such that $c_1\ne c_k$. Let be $a=\min_{k\in A}k$. Case 1: $k=2\Longrightarrow c_2=\text{red}$. Results: $c_3=c_{1+2}=\text{blue}; c_6=c_{2\cdot3}=\text{red}$; $c_7=c_{1+6}=\text{blue}; c_{14}=c_{2\cdot7}=\text{red}$; $c_{15}=c_{1+14}=\text{blue}$, contradiction with the initial condition $c_{15}=\text{red}$. Case 2: $k=3\Longrightarrow c_1=c_2=\text{blue};c_3=\text{red}$. $c_4=c_{1+3}=\text{blue}; c_5=c_{2+3}=\text{blue}; c_6=c_{2\cdot3}=\text{red}$; $c_7=c_{1+6}=c_{3+4}=\text{blue}; c_8=c_{2+6}=c_{3+5}=\text{blue}$; If $c_9=\text{blue}$, results $c_{15}=c_{6+9}=\text{blue}$, contradiction. Hence: $c_9=\text{red}$. $c_{10}=c_{1+9}=c_{4+6}=\text{blue}; c_{11}=c_{2+9}=c_{5+6}=\text{blue}; c_{12}=c_{3\cdot4}=\text{red}$. $c_{13}=c_{1+12}=c_{4+9}=c_{6+7}=\text{blue};c_{14}=c_{2+12}=c_{5+9}=c_{6+8}=\text{blue}$. Case 3: $k=5$. $c_{10}=c_{2\cdot5}=\text{red}$. $c_{5m+1}=c_{5m+2}=c_{5m+3}=c_{5m+4}=\text{blue}$, for $m\in\{0,1,2\}$. Case 4: $k\ge4, k\nmid 15$. Results: $c_{mk}=\text{red}$ and $c_{mk+r}=\text{blue}, \forall m,r\in\mathbb{Z}, 0\le m\le \left\lfloor\dfrac{15}{k}\right\rfloor, 1\le r\le k-1$. $k\nmid 15\Longrightarrow \exists m_0,r_0\in\mathbb{Z}, 1\le r_0\le k-1$ such that $15=m_0k+r_0$, hence $c_{15}=\text{blue}$, contradiction. Result the possible solutions: a) $A=\{1,2,\dots,15\}; B=\phi$; b) $A=\{3,6,9,12,15\}; B=\{1,2,4,5,7,8,10,11,13,14\}$; c) $A=\{5,10,15\}; B=\{1,2,3,4,6,7,8,9,11,12,13,14\}$.