Given a positive integer $n\ge 3$, colour each cell of an $n\times n$ square array with one of $\lfloor (n+2)^2/3\rfloor$ colours, each colour being used at least once. Prove that there is some $1\times 3$ or $3\times 1$ rectangular subarray whose three cells are coloured with three different colours. (Russia) Ilya Bogdanov, Grigory Chelnokov, Dmitry Khramtsov
Problem
Source: Romanian Master Of Mathematics 2012
Tags: floor function, ceiling function, geometry, rectangle, combinatorics proposed, combinatorics, double counting
04.03.2012 00:01
http://rmm.lbi.ro/index.php?id=solutions_math
06.03.2012 08:00
denote $f(n)$ to be the maximum number of colors that can be used in an $ n\times n $ square, each color used at least once, without having a straight triomino whose three cells are coloured with three different colours. Obviously $f(0)=0,f(1)=1,f(2)=4$. We shall prove when $n \ge 3$, $f(n) \le f(n-3)+2n$,for $n$ is even and $f(n) \le f(n-3)+2(n-1)$,for $n$ is odd. Consider the first $n \times 3$ cells. The first row can have at most two colors, whenever we add two rows ( or $2 \times 3$ cells) to it, we can use at most 2 new colors. Suppose on the contrary, any two of the 3 new colors cannot be on the same column, and the three cells whose row has two new colors should all be painted with these two new colors, then we have one $3 \times 1$ subarray that are colored with three different colours,contradiction. So the first $n \times 3$ cells can be painted with at most $2\lceil \frac{n+1}{2} \rceil$ colors. Similarly, the bottom $3 \times (n-3)$ (excluding the left bottom $3 \times 3$ cells) can be painted with at most $2\lceil \frac{n-3}{2} \rceil$ new colors. So the first $n \times 3$ and the bottom $3 \times n$ cells can be painted with at most $2n$($n$ is even), or $2(n-1)$ ($n$ is odd) colors in total. We have $f(3)=4, f(4)=9, f(5) \le 12$, and $f(n) \le f(n-6)+4n-8$. So \[ f(n) \le \frac{n(n+2)}{3} (n=6k,6k+1),f(n) \le \frac{n(n+2)+4}{3} (n=6k+2) \] \[ f(n) \le \frac{n(n+2)-3}{3} (n=6k+3),f(n) \le \frac{n(n+2)+3}{3} (n=6k+4) \] \[ f(n) \le \frac{n(n+2)+1}{3} (n=6k+5) \] if the square is painted with at least $f(n)+1$ colors, there is some straight triomino whose three cells are coloured with three different colours
07.12.2014 18:06
Suppose otherwise, we count the total number of trominoes that need to be filled with a pair of same colours, which is exactly $2n^2-4n$. Now consider each colour and let there be $a_1,...,a_{\lfloor (n+2)^2/3\rfloor}$ of each colour. We claim that for each colour $i$, the number of new trominoes it can fill such that each of them have a pair of cells with colour $i$, is at most $3a_i-3$. For $a_i=1,2$ this is clearly true. For $a_i>2$, we look at the distribution of colour $i$ in each row/column. WLOG consider a row. We can assume that the distance between two adjacent colour $i$ cells in this row is $0$ or $1$ (if $>2$, bringing them closer fills more trominoes). Now let the distribution of colour $i$ cells in this row be blocks of $b_1,...b_k$, where between $b_j$ and $b_{j+1}$ is $1$ other colour cell. In each $b_j$, the number of trominoes filled with pair of cells coloured $i$ both from $b_j$ is $b_j$, except when $b_j=1$ it is $0$. (If a tromino has $3$ colour $i$ cells it is counted once). Then between adjacent blocks $b_j$ and $b_{j+1}$, there is an extra tromino that is filled with a pair. Let there be $m$ $b_j$'s that are $1$. Hence total trominoes covered is $\leq(b_1+...+b_k-m)+(k-1)$ $\leq(b_1+...+b_k-m-1)+(\frac{b_1+...+b_k-m}{2}+m)$ (assuming max $k$) $\leq\frac{3(b_1+...+b_k)}{2}-1$. Hence if a row has $x\geq 1$ cells coloured $i$, it has at most $\frac{3x}{2}-1$ trominos covered. Since $a_i>2$ there are at least $3$ rows and columns with cells coloured $i$, hence total number of trominoes covered is $\leq\frac{3a_i}{2}+\frac{3a_i}{2}-3=3a_i-3$ Hence total trominoes covered over all colours is $\leq 3n^2-3(\lfloor (n+2)^2/3\rfloor)\leq 3n^2-3\frac{(n+2)^2-1}{3}=2n^2-4n-3$, contradiction.
20.01.2015 05:36
Let $ k $ be the number of colors (that floor thing). Let there be $f_i$ squares of color $I$. Define a "rocol" to be a row or a column. Let $G(i)$ be the number of rocols with an odd number of squares of color $i$, and $Y(i)$ be the number of rocols with an even nonnegative number of squares of color $i$. Let $l_i$ be the number of rectangles that are "occupied" by color $i$. We have $\sum fi=n^2$, $f_i \ge 0$, $\sum l_i = 2n(n-2)$. Now it is easy to see that $l_i \le 3f_i - (3/2)G(i)-Y(i) $. This can be proven by analyzing each rocol separately. Let $G= \sum G(i)$, $Y= \sum Y(i)$. We arrive at $(3/2)G+Y < (n+2)^2$ It is easy to see that if $f_i \le 3$ then $(3/2)G(i)+Y(i) \ge f_i+2$ and otherwise, $(3/2)G(i)+Y(i) \ge 2\sqrt{f_i}$. Let $f_1, ..., f_l \le 3$ and $f_{l+1}, .., f_k \ge 4$. Subtracting $\sum f_i$ we arrive at $2l + \sum_{i>l} (2\sqrt{f_i}-f_i) < 4n+4$. By karamata, since $2\sqrt{x}-x$ is concave, the sum is minimized when $f_{l+1}, ..., f_{k-1}=4 $ and $f_k$ is whatever else is needed for $\sum f_i=n^2$. Call $F=f_k$. If $F \ge 10$, we see that the sum is becomes less when we replace $f_{l+1}=1$ instead of $f_{l+1}=4$. (If $F \le 9$ we finish easily). Therefore WLOG $l=k-1$ and $F=n-k^2+1$. We need to prove that $k-1+\sqrt{F}-\frac{F}{2} \ge 2n+2$ $n^2-2n-2 \ge \frac{3F}{2} - \sqrt{F}$ We notice that $F = n^2- \lfloor \frac{(n+2)^2}{3} \rfloor + 1 \ge n^2-\frac{n(n+4)}{3} $. This can be proven since $(n+2)^2$ is 1 or 0 mod 3. Since $\sqrt{x}-(3x/2) $ is decreasing for $x > 1$, we can safely assume $F=n^2-\frac{n(n+4)}{3}$. We must prove $ (n-1)^2 \ge (3n^2-n^2-4n)/2 +3 - \sqrt{F} $ $(n-1)^2 \ge (n-1)^2+2-\sqrt{F}$ which is true so we're done.
21.02.2018 01:39
Say that a color blocks a tromino if the tromino contains at least two cells of that color. The central claim is that if there are $m$ colored cells then at most $3m-3$ trominos are blocked by that color. This is clear for $m=1$ so suppose that $m>1$. We count the number of pairs of colored cells and blocked trominos that contain that cell. Allow trominos to leave the grid, as they can only contribute extra blocked trominos. Note that every colored cell is a part of $6$ trominos, leading to at most $6m$ such pairs. Furthermore, any vertical tromino whose bottommost cell is a topmost colored cell or whose topmost cell is a bottommost colored cell, as well as any horizontal tromino whose leftmost cell is a rightmost colored cell or whose rightmost cell is a leftmost colored cell, cannot be blocked. There are at least $6$ of these, as $m>1$ so the colored cells occupy at least $3$ distinct rows/columns, each of which contain two such invalid trominos. Hence, we have at most $6m-6$ such pairs, leading to at most $3m-3$ blocked trominos as each blocked tromino is in at least two such pairs, as desired. Now, suppose that we color the grid with $k$ colors such that every tromino is blocked. At most $\sum 3m-3=3n^2-3k$ trominos are blocked, while all of the $2n(n-2)=2n^2-4n$ distinct trominos in the grid must be blocked. Hence, $3n^2-3k\ge 2n^2-4n\implies k\le\frac{n^2+4n}3<\left\lfloor\frac{(n+2)^2}3\right\rfloor$, so some tromino must contain all distinct colors when we color with $\left\lfloor\frac{(n+2)^2}3\right\rfloor$ colors, as desired.
14.08.2018 06:12
Here is a solution following the "counting in two ways" paradigm: We prove that if there is no $3$-colored such subarray, then the number of distinct colors $M$ on the board is at most $\lfloor (n+2)^2 / 3 \rfloor - 1$. Given an $n \times n$ board, let a $3 \times 1$ or $1 \times 3$ tile be called a "supertile" if at least one of its cells lies on the board (so the supertiles are the set of all $3 \times 1$ or $1 \times 3$ tiles on the board, plus the ones that are hanging off of the sides). Fix a coloring of the board and assume that there is no $3 \times 1$ or $1 \times 3$ tile colored by three different colors. We will count the set $X$ of pairs of a supertile and a color $c$ which appears in a cell covered by that supertile. On the one hand -- counting by supertiles -- each supertile must then be incident to at most two colors. Even more: the ones which hang off the board with only one covered cell actually on the board have only one incident color. So $|X| \le 2(n+2)^2 - 4n = 2n^2+4n+8$. On the other hand -- counting by colors -- for any color $c$ appearing on the board in some cell $x$, the color $c$ is incident to at least $6$ different supertiles: the horizontal one with $x$ in the leftmost position, the horizontal one with $x$ in the center position, the horizontal one with $x$ in the rightmost position, and all the corresponding ones for the vertical supertiles. So $6M \le |X|$. Thus, $6M \le 2n^2+4n+8 \Rightarrow M \le (n^2+2n+4) / 3 \le \lfloor (n+2)^2 / 3 \rfloor - 1$.
29.04.2020 12:15
@above I think the proof is wrong. I think $|X|\le 4n^2$ (asymptotically), so the proof shows $M\le 2n^2/3$ (asymptotically), which is not good enough. Indeed, the proof idea is too weak since the grid structure is not being used at all. Sigh dumb global. Call a tromino a $1\times 3$ or $3\times 1$ subarray. Suppose for sake of contradiction that all trominoes have at most $2$ distinct colors. Now, consider all pairs $(t,c)$ where $t$ is a tromino and $c$ is a color that appears twice in the tromino. Let $T$ be the number of such pairs. By assumption, $T$ is actually just the number of trominoes total, which is \[T=2(n-2)^2.\]We now count $T$ by colors. Indeed, we have the following claim which does just that. Claim: Suppose a color $c$ has $k$ occurrences in the grid. Then, there are at most $3k-3$ trominoes with at least $2$ squares of color $c$. Proof: Suppose $k\ge 2$ as $k=1$ is trivial. This is actually a somewhat weak bound, in that it suffices to solve the 1D version. Call a tromino good if it contains two of $c$. Indeed, suppose we have a $1\times n$ row, and the appearances of color $c$ are in contiguous blocks of lengths $a_1,\ldots,a_t$. If we shift the blocks so they are just $1$ apart, then the number of good dominoes does not decrease, so WLOG all the gaps are $1$. Then, it is not hard to see that the number of good trominoes is \[a_1+\cdots+a_t+t-\ell-1\]where $\ell$ is the number of $i$ such that $a_i=1$. We see that \[a_1+\cdots+a_t\ge 2t-\ell,\]so $t\le\frac{\ell}{2}+\frac{a_1+\cdots+a_t}{2}$, so the number of good trominoes is at most \[\frac{3}{2}(a_1+\cdots+a_t)-1.\] Summing over all rows and columns, we see that the number of good trominoes overall is at most \[\sum_{i=1}^n \frac{3}{2}r_i+\sum_{i=1}^n\frac{3}{2}c_i - e=3k-e\]where $r_i$ is the number of color $c$s in row $i$, $c_i$ for column $i$, and $e$ is the number of rows and columns that have some color $c$. Since $k\ge 2$, we have $e\ge 3$, so we're done. $\blacksquare$ Let the colors be $1,2,\ldots,m$, and let $k_i$ be the number of occurrences of color $i$. Then by the above claim, \[T\le\sum_{i=1}^m(3k_i-3) = 3n^2-3m,\]so \[m\le n^2-\frac{2}{3}(n-2)^2<\lfloor (n+2)^2/3\rfloor,\]which is the desire contradiction. Remark: Asymptotic equality is achieved when all squares satisfying $x+y\equiv 1,2\pmod{3}$ are white, and each other square is a different color.
19.09.2020 23:13
@above, nice solution . I think this is a small typo. yayups wrote: \[T=2(n-2)^2.\] Shouldn't this be $2n(n-2)$ if I'm not clowning Here's another proof of the key claim. yayups wrote: Claim: Suppose a color $c$ has $k$ occurrences in the grid. Then, there are at most $3k-3$ trominoes with at least $2$ squares of color $c$.