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.

## Comments

Sort by:

TopNewestNice 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, 1 month ago

Log in to reply

– Victor Loh · 3 years, 1 month ago

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

– Xuming Liang · 3 years, 1 month ago

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