Difference between revisions of "1998 USAMO Problems/Problem 4"

(Created page with "== Problem == == Solution == {{solution}} ==See Also== {{USAMO newbox|year=1998|num-b=3|num-a=5}} Category:Olympiad Combinatorics Problems")
 
(Solution)
(4 intermediate revisions by 3 users not shown)
Line 1: Line 1:
 
== Problem ==
 
== Problem ==
 +
A computer screen shows a <math>98 \times 98</math> 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 ==
 
== Solution ==
 
{{solution}}
 
{{solution}}
 +
 +
Answer: 98.
 +
 +
There are 4·97 adjacent pairs of squares in the border and each pair has one black and one white square. Each move can fix at most 4 pairs, so we need at least 97 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 98 moves are needed.
 +
 +
It is easy to see that 98 suffice: take 49 1x98 rectangles (alternate rows), and 49 98x1 rectangles (alternate columns).
 +
 +
credit: https://mks.mff.cuni.cz/kalva/usa/usoln/usol984.html
 +
 +
editor: Brian Joseph
  
 
==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}}

Revision as of 23:52, 1 October 2016

Problem

A computer screen shows a $98 \times 98$ 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

This problem needs a solution. If you have a solution for it, please help us out by adding it.

Answer: 98.

There are 4·97 adjacent pairs of squares in the border and each pair has one black and one white square. Each move can fix at most 4 pairs, so we need at least 97 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 98 moves are needed.

It is easy to see that 98 suffice: take 49 1x98 rectangles (alternate rows), and 49 98x1 rectangles (alternate columns).

credit: https://mks.mff.cuni.cz/kalva/usa/usoln/usol984.html

editor: Brian Joseph

See Also

1998 USAMO (ProblemsResources)
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. AMC logo.png