We are going to colour the cells of a $2015 \times 2015$ board such that there are none of the following: $1)$ Three cells with the same colour where two of them are in the same column, and the third is in the same row and to the right of the upper cell, $2)$ Three cells with the same colour where two of them are in the same column, and the third is in the same row and to the left of the lower cell. What is the minimum number of colours $k$ required to make such a colouring possible?
Problem
Source: Turkey TST 2015
Tags: Turkey, TST, 2015, combinatorics
toto1234567890
17.02.2016 10:27
Hmm.... Any answers??
IsoLyS
18.02.2016 16:31
Easy that each color is used at most 4029 times, hence there are at least 1008 colors. Indeed, there is an example with 1008Like this:
1 1 2 2 3 3 4 4 5
5 1 1 2 2 3 3 4 4
5 5 1 1 2 2 3 3 4
4 5 5 1 1 2 2 3 3
4 4 5 5 1 1 2 2 3
3 4 4 5 5 1 1 2 2
3 3 4 4 5 5 1 1 2
2 3 3 4 4 5 5 1 1
2 2 3 3 4 4 5 5 1.
Assassino9931
16.06.2024 20:45
IsoLyS wrote: Easy that each color is used at most 4029 times Can you explain, please?
bin_sherlo
26.11.2024 00:35
Answer is $1008$. See the example below in the figure for $7\times 7$. Pick a square $A$. If there cannot exist same coloured squares with $A$ in its row left to it and in its column up to it. If there is no same coloured square left to it, then draw an arrow showing left, similarily if there is no same coloured square up to it, then draw an arrow showing up. If some squares' arrows show left in a certain row, then these squares have pairwise distinct colours. If there are $\leq 1007$ colours, then there can be at most $1007$ left-arrows in each row and $1007$ up-arrows in each column. However, $1007\times 2015+1007\times 2015=2014\times 2015<2015\times 2015$ which results in a contradiction. Hence there are at least $1008$ colours as desired.$\blacksquare$
Attachments:
