Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2020 CAMO Problems/Problem 6"

m (→‎Solution)
 
Line 14: Line 14:
  
 
==See also==
 
==See also==
−
{{CAMO newbox|year=2020|num-b=1|num-a=3}}
+
{{CAMO newbox|year=2020|num-b=5|after=Last Problem}}
  
 
[[Category:Olympiad Combinatorics Problems]]
 
[[Category:Olympiad Combinatorics Problems]]
 
{{MAC Notice}}
 
{{MAC Notice}}

Latest revision as of 12:18, 18 October 2020

Problem 6

Let $n$ be a positive integer. Eric and a squid play a turn-based game on an infinite grid of unit squares. Eric's goal is to capture the squid by moving onto the same square as it.

Initially, all the squares are colored white. The squid begins on an arbitrary square in the grid, and Eric chooses a different square to start on. On the squid's turn, it performs the following action exactly $2020$ times: it chooses an adjacent unit square that is white, moves onto it, and sprays the previous unit square either black or gray. Once the squid has performed this action $2020$ times, all squares colored gray are automatically colored white again, and the squid's turn ends. If the squid is ever unable to move, then Eric automatically wins. Moreover, the squid is claustrophobic, so at no point in time is it ever surrounded by a closed loop of black or gray squares. On Eric's turn, he performs the following action at most $n$ times: he chooses an adjacent unit square that is white and moves onto it. Note that the squid can trap Eric in a closed region, so that Eric can never win.

Eric wins if he ever occupies the same square as the squid. Suppose the squid has the first turn, and both Eric and the squid play optimally. Both Eric and the squid always know each other's location and the colors of all the squares. Find all positive integers $n$ such that Eric can win in finitely many moves.

Solution

First, we should note that there are some starting positions for which Eric can never win, if the squid starts first. For example, if Eric is right next to the squid, then he can just get covered entirely by black squares in 6 moves. In general, if we have a coordinate system with origin at the squid's starting position, with Eric's coordinates $x$, $y$, then they must be such that:

$x$ $+$ $y$ $>$ $2013$, otherwise Eric can always be covered in the first turn.

Now, assuming that it isn't possible for that to happen, then we change the origin of the coordinate system to the squid's most recent position. Say $x + y = 2014$, then if $n < 2013$, then the squid can cover Eric in the very next turn. Hence, $n > 2013$. Now we try to get a strategy for which Eric wins. The sum of Eric's coordinates should be greater than $2013$ after any squid-move for the squid to avoid defeat. On any move in which the squid cannot win directly, it must focus on getting away. If initially $x + y = 2014$, then after the squid's move, $x + y < 4035$. If $n > 4034$, the squid can always be caught in the next move. If $n < 4034$, the squid can always get away/win. Hence, $n > 4034$ Our answer is all $n$ greater than $4034$

See also

2020 CAMO (Problems • Resources)
Preceded by
Problem 5 		Followed by
Last Problem
1 • 2 • 3 • 4 • 5 • 6
All CAMO Problems and Solutions

The problems on this page are copyrighted by the MAC's Christmas Mathematics Competitions. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2020_CAMO_Problems/Problem_6&oldid=135239"