Waste less time on Facebook — follow Brilliant.

Combinatorics #3

A \(4\times19\) rectangle is composed of unit squares, each colored either red, green or blue. Prove that there exists a rectangle whose sides are parallel to the sides of the \(4\times19\) rectangle formed by connecting the centers of \(4\) squares of the same color.

Note by Victor Loh
3 years, 4 months ago

No vote yet
1 vote


Sort by:

Top Newest

Nice problem!

First you have to understand how such a rectangle can be formed: by having two \(4\times 1\) rectangles inwhich two of their squares are colored with the same colors and they are in the same positions.

Looking at the \(4\times 1\) rectangles, since \(4\) squares are colored with \(3\) colors, by PHP(short for pigeonhole principle from now on :) ) there exists two squares with the same color, we will call these two squares "linked".

Since there are \(19\) of these rectangles, by PHP there exists \(\lceil \frac {19}{3} \rceil=7\) rectangles inwhich the colors of their "linked" squares are the same. Note that there are \({4\choose 2}=6\) possible ways for the "linked" squares to position, Hence by PHP there exists two rectangles inwhich their "linked" squares are in the same positions and we are done.

Xuming Liang - 3 years, 4 months ago

Log in to reply

Keep up the good work! I'll be posting more interesting problems (Around Level 3 perhaps)

Victor Loh - 3 years, 4 months ago

Log in to reply

Thanks! I'm trying to improve my solution writing skills for combinatorics problems..

Xuming Liang - 3 years, 4 months ago

Log in to reply


Problem Loading...

Note Loading...

Set Loading...