2014 UMO Problems/Problem 1

Revision as of 15:30, 12 February 2020 by Programjames1 (talk | contribs) (Solution)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

Problem

Todd and Allison are playing a game on the grid shown below. At the beginning, an orange stone is placed in the center intersection on the grid. They take turns, with Todd going first. In each of Todd’s turns, he must move the orange stone from its current position to a horizontally or vertically adjacent intersection that is not occupied by a blue stone, and then he places a blue stone in the orange stone’s previous spot. In each of Allison’s turns, she places a blue stone on exactly one unoccupied intersection. Todd loses the game when he is forced to move into one of the corner intersections, labeled by $A, B, C$, and $D$ in the diagram below. Allison loses if Todd can’t move. Allison tries to force Todd to lose in as few as turns as possible, and Todd tries to survive as long as possible. If both of them play as best they can, how many blue stones will be on the board at the end of the game? (You may assume that Todd always loses.)

[asy] size(200); for(int k=0;k<9;++k) { D((0,k)--(8,k),black);D((k,0)--(k,8),black); } MP("A",(0,8),NW);MP("B",(0,0),SW);MP("C",(8,0),SE);MP("D",(8,8),NE); D(CR((4,4),.2),black); fill(CR((4,4),.2),orange); [/asy]

Solution

WLOG, assume Todd moves to the left. Note that you can always force Todd to move down or left. Then it's a matter of just counting how many steps it takes to get Todd to the bottom left corner, multiplying by 2, and subtracting one (because you don't play on the last turn). We get $15$.

See Also

2014 UMO (ProblemsAnswer KeyResources)
Preceded by
First Problem
Followed by
Problem 2
1 2 3 4 5 6
All UMO Problems and Solutions
Invalid username
Login to AoPS