Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2006 Romanian NMO Problems/Grade 7/Problem 2"
((made a table))
 
(2 intermediate revisions by 2 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]]
 
[[Category:Olympiad Combinatorics Problems]]

Latest revision as of 01:48, 18 March 2009

Problem

A square of side $n$ is formed from $n^2$ unit squares, each colored in red, yellow or green. Find minimal $n$, 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 $n\leq6$, consider this coloring for a 6x6 board:

\[\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}\]

We can take the top $n$-by-$n$ grid of this board as a coloring not satisfying the conditions. For $n\geq7$, 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

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2006_Romanian_NMO_Problems/Grade_7/Problem_2&oldid=30783"