Difference between revisions of "2018 IMO Problems/Problem 4"
(→Solution) |
|||
| Line 10: | Line 10: | ||
== Solution == | == Solution == | ||
| + | The maximal K is 100. | ||
| + | Amy can reach at least 100 by playing only on sites for which x+y is even. There are 200 such sites, none are of distance <math>\sqrt{5}</math> from each other and Ben can occupy at most half of them. | ||
| + | On the other hand Ben can prevent Amy from reaching more than 100 using the following strategy: | ||
| + | Picture the sites as a 20 by 20 board and divide it into 25 non overlapping 4-by-4 squares. We label each site in the square as follows: | ||
| + | <cmath>1, 2, 3, 4</cmath> | ||
| + | <cmath>5, 6, 7, 8</cmath> | ||
| + | <cmath>8, 7, 6, 5</cmath> | ||
| + | <cmath>4, 3, 2, 1</cmath> | ||
| + | |||
| + | Whenever Amy plays in a square Ben plays in the same square and in the site with the same label. In each square Amy can place at most 2 stones in sites labeled 1,4,6,7 (no three sites with labels from this set are free from distance <math>\sqrt{5}</math> and Amy can play one stone on each label since Ben plays the other). Likewise for the sites labeled 2,3,5,8. So in total Amy can place at most 4 stones in each of the 25 squares for a total of 100 stones. | ||
Revision as of 04:11, 12 July 2018
Problem 4. A site is any point 
in the plane such that 
and 
are both positive integers less
than or equal to 20.
Initially, each of the 400 sites is unoccupied. Amy and Ben take turns placing stones with Amy
going first. On her turn, Amy places a new red stone on an unoccupied site such that the distance
between any two sites occupied by red stones is not equal to 
. On his turn, Ben places a new blue
stone on any unoccupied site. (A site occupied by a blue stone is allowed to be at any distance from
any other occupied site.) They stop as soon as a player cannot place a stone.
Find the greatest 
such that Amy can ensure that she places at least red stones, no matter
how Ben places his blue stones.
Solution
The maximal K is 100.
Amy can reach at least 100 by playing only on sites for which x+y is even. There are 200 such sites, none are of distance from each other and Ben can occupy at most half of them.
On the other hand Ben can prevent Amy from reaching more than 100 using the following strategy:
Picture the sites as a 20 by 20 board and divide it into 25 non overlapping 4-by-4 squares. We label each site in the square as follows:
![\[1, 2, 3, 4\]](http://latex.artofproblemsolving.com/0/3/c/03cc25b3a17ecb8bb93dca5f751df3736f0b1f89.png)
![\[5, 6, 7, 8\]](http://latex.artofproblemsolving.com/9/e/a/9ead054422b9e90e16a2726c73813b9a4d8fd7de.png)
![\[8, 7, 6, 5\]](http://latex.artofproblemsolving.com/e/8/3/e83b63518a2bdd9dbe7a094f7cce433a644983fe.png)
![\[4, 3, 2, 1\]](http://latex.artofproblemsolving.com/a/d/8/ad83f37e1cfffd05995259ee4a1460e3f62e9d25.png)
Whenever Amy plays in a square Ben plays in the same square and in the site with the same label. In each square Amy can place at most 2 stones in sites labeled 1,4,6,7 (no three sites with labels from this set are free from distance and Amy can play one stone on each label since Ben plays the other). Likewise for the sites labeled 2,3,5,8. So in total Amy can place at most 4 stones in each of the 25 squares for a total of 100 stones.
