Difference between revisions of "1998 USAMO Problems/Problem 4"
(It was on the Internet) |
(fixed duplicate solution and whatnot) |
||
| (2 intermediate revisions by 2 users not shown) | |||
| Line 3: | Line 3: | ||
== Solution == | == Solution == | ||
| − | + | Answer: <math>98</math>. | |
| − | Answer: 98. | ||
| − | There are | + | There are <math>4\cdot97</math> adjacent pairs of squares in the border and each pair has one black and one white square. Each move can fix at most <math>4</math> pairs, so we need at least <math>97</math> moves. However, we start with two corners one color and two another, so at least one rectangle must include a corner square. But such a rectangle can only fix two pairs, so at least <math>98</math> moves are needed. |
| − | It is easy to see that 98 suffice: take 49 | + | It is easy to see that 98 moves suffice: take 49 <math>1\times98</math> rectangles (alternate rows), and 49 <math>98\times1</math> rectangles (alternate columns). |
credit: https://mks.mff.cuni.cz/kalva/usa/usoln/usol984.html | credit: https://mks.mff.cuni.cz/kalva/usa/usoln/usol984.html | ||
editor: Brian Joseph | editor: Brian Joseph | ||
| + | |||
| + | second editor: integralarefun | ||
| + | |||
==See Also== | ==See Also== | ||
{{USAMO newbox|year=1998|num-b=3|num-a=5}} | {{USAMO newbox|year=1998|num-b=3|num-a=5}} | ||
[[Category:Olympiad Combinatorics Problems]] | [[Category:Olympiad Combinatorics Problems]] | ||
{{MAA Notice}} | {{MAA Notice}} | ||
Latest revision as of 17:56, 10 May 2023
Problem
A computer screen shows a 
chessboard, colored in the usual way. One can select with a mouse any rectangle with sides on the lines of the chessboard and click the mouse button: as a result, the colors in the selected rectangle switch (black becomes white, white becomes black). Find, with proof, the minimum number of mouse clicks needed to make the chessboard all one color.
Solution
Answer: 
.
There are 
adjacent pairs of squares in the border and each pair has one black and one white square. Each move can fix at most 
pairs, so we need at least 
moves. However, we start with two corners one color and two another, so at least one rectangle must include a corner square. But such a rectangle can only fix two pairs, so at least moves are needed.
It is easy to see that 98 moves suffice: take 49 
rectangles (alternate rows), and 49 
rectangles (alternate columns).
credit: https://mks.mff.cuni.cz/kalva/usa/usoln/usol984.html
editor: Brian Joseph
second editor: integralarefun
See Also
| 1998 USAMO (Problems • Resources) | ||
| Preceded by Problem 3 |
Followed by Problem 5 | |
| 1 • 2 • 3 • 4 • 5 • 6 | ||
| All USAMO Problems and Solutions | ||
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. 
