# Difference between revisions of "2006 Romanian NMO Problems/Grade 7/Problem 2"

Brut3Forc3 (talk | contribs) ((made a table)) |
|||

(3 intermediate revisions by 3 users not shown) | |||

Line 2: | Line 2: | ||

A square of side <math>n</math> is formed from <math>n^2</math> unit squares, each colored in red, yellow or green. Find minimal <math>n</math>, such that for each coloring, there exists a line and a column with at least 3 unit squares of the same color (on the same line or column). | A square of side <math>n</math> is formed from <math>n^2</math> unit squares, each colored in red, yellow or green. Find minimal <math>n</math>, such that for each coloring, there exists a line and a column with at least 3 unit squares of the same color (on the same line or column). | ||

==Solution== | ==Solution== | ||

+ | For <math>n\leq6</math>, consider this coloring for a 6x6 board: | ||

+ | |||

+ | <cmath>\begin{tabular}{|c|c|c|c|c|c|} | ||

+ | \hline R&Y&G&R&Y&G \\ | ||

+ | \hline G&R&Y&G&R&Y \\ | ||

+ | \hline Y&G&R&Y&G&R \\ | ||

+ | \hline R&Y&G&R&Y&G \\ | ||

+ | \hline G&R&Y&G&R&Y \\ | ||

+ | \hline Y&G&R&Y&G&R \\ | ||

+ | \hline | ||

+ | \end{tabular}</cmath> | ||

+ | |||

+ | We can take the top <math>n</math>-by-<math>n</math> grid of this board as a coloring not satisfying the conditions. | ||

+ | For <math>n\geq7</math>, we note that each row or column must have at least one color with 3 or more squares by the pigeonhole principle, so our answer is 7. | ||

+ | |||

==See also== | ==See also== | ||

*[[2006 Romanian NMO Problems]] | *[[2006 Romanian NMO Problems]] | ||

+ | [[Category:Olympiad Combinatorics Problems]] |

## Latest revision as of 02:48, 18 March 2009

## Problem

A square of side is formed from unit squares, each colored in red, yellow or green. Find minimal , such that for each coloring, there exists a line and a column with at least 3 unit squares of the same color (on the same line or column).

## Solution

For , consider this coloring for a 6x6 board:

We can take the top -by- grid of this board as a coloring not satisfying the conditions. For , we note that each row or column must have at least one color with 3 or more squares by the pigeonhole principle, so our answer is 7.