Difference between revisions of "2016 UMO Problems/Problem 1"
(Created page with "==Problem == == Solution == == See Also == {{UMO box|year=2016|before=First Problem|num-a=2}} [[Category:]]") |
|||
| Line 1: | Line 1: | ||
==Problem == | ==Problem == | ||
| + | Ada and Otto are engaged in a battle of wits. In front of them is a figure with six dots, and nine sticks are placed between pairs of dots as shown below. The dots are labeled <math>A, B, C, D, E, F</math>. Ada begins the game by placing a pebble on the dot of her choice. Then, starting with Ada and alternating turns, each player picks a stick adjacent to the pebble, moves the pebble to the dot at the other end of the stick, and then removes the stick from the figure. The game ends when there are no sticks adjacent to the pebble. The player who moves last wins. A sample game is described below. If both players play optimally, who will win? | ||
| + | <asy> | ||
| + | pair A=(1,0),B=(1/2,sqrt(3)/2),C=(-1/2,sqrt(3)/2),D=(-1,0),E=(-1/2,-sqrt(3)/2),E=(-1/2,-sqrt(3)/2),F=(1/2,-sqrt(3)/2); | ||
| + | draw(A--B--C--D--E--F--A,dot); | ||
| + | draw(A--C--E--A,dot); | ||
| + | MP("A",A,(1,0));MP("B",B,NE);MP("C",C,NW);MP("D",D,W);MP("E",E,SW);MP("F",F,SE); | ||
| + | </asy> | ||
| + | |||
| + | Sample Game | ||
| + | |||
| + | 1. Ada places the pebble at B. | ||
| + | |||
| + | 2. Ada removes the stick BC, placing the pebble at C. | ||
| + | |||
| + | 3. Otto removes the stick CD, placing the pebble at D. | ||
| + | |||
| + | 4. Ada removes the stick DE, placing the pebble at E. | ||
| + | |||
| + | 5. Otto removes the stick EA, placing the pebble at A. | ||
| + | |||
| + | 6. Ada removes the stick AB and wins. | ||
== Solution == | == Solution == | ||
| + | |||
| + | Ada will win. Here is one possible strategy. Turn 1: Ada begins by putting the pebble at A. Turn 2: Ada removes stick AB, and places the pebble at B. Turn 3: The only remaining stick for Otto to choose is stick BC, so Otto removes this stick, placing the pebble at C. Turn 4: Ada removes stick CD, placing the pebble at D. Turn 5: Otto is again forced to choose the only remaining adjacent stick, DE. So Otto removes this stick, and places the pebble at E. Turn 6: Ada removes stick EF, placing the pebble at F. Turn 7: Otto is forced to remove stick FA, placing the pebble at A. Turn 8: Ada removes stick AC, placing the pebble at C. Turn 9: Otto is forced to remove stick CE, placing the pebble at E. Turn 10: Ada removes stick EA, leaving no remaining sticks. At this point, there are no valid moves, so Ada will win because every one of Otto’s moves is forced. | ||
== See Also == | == See Also == | ||
{{UMO box|year=2016|before=First Problem|num-a=2}} | {{UMO box|year=2016|before=First Problem|num-a=2}} | ||
| − | [[Category:]] | + | [[Category: Intermediate Combinatorics Problems]] |
Latest revision as of 03:52, 22 January 2019
Problem
Ada and Otto are engaged in a battle of wits. In front of them is a figure with six dots, and nine sticks are placed between pairs of dots as shown below. The dots are labeled 
. Ada begins the game by placing a pebble on the dot of her choice. Then, starting with Ada and alternating turns, each player picks a stick adjacent to the pebble, moves the pebble to the dot at the other end of the stick, and then removes the stick from the figure. The game ends when there are no sticks adjacent to the pebble. The player who moves last wins. A sample game is described below. If both players play optimally, who will win?
![[asy] pair A=(1,0),B=(1/2,sqrt(3)/2),C=(-1/2,sqrt(3)/2),D=(-1,0),E=(-1/2,-sqrt(3)/2),E=(-1/2,-sqrt(3)/2),F=(1/2,-sqrt(3)/2); draw(A--B--C--D--E--F--A,dot); draw(A--C--E--A,dot); MP("A",A,(1,0));MP("B",B,NE);MP("C",C,NW);MP("D",D,W);MP("E",E,SW);MP("F",F,SE); [/asy]](http://latex.artofproblemsolving.com/a/0/e/a0e0e3376b5da2c6f74e8ed31f84d927b8d37331.png)
Sample Game
1. Ada places the pebble at B.
2. Ada removes the stick BC, placing the pebble at C.
3. Otto removes the stick CD, placing the pebble at D.
4. Ada removes the stick DE, placing the pebble at E.
5. Otto removes the stick EA, placing the pebble at A.
6. Ada removes the stick AB and wins.
Solution
Ada will win. Here is one possible strategy. Turn 1: Ada begins by putting the pebble at A. Turn 2: Ada removes stick AB, and places the pebble at B. Turn 3: The only remaining stick for Otto to choose is stick BC, so Otto removes this stick, placing the pebble at C. Turn 4: Ada removes stick CD, placing the pebble at D. Turn 5: Otto is again forced to choose the only remaining adjacent stick, DE. So Otto removes this stick, and places the pebble at E. Turn 6: Ada removes stick EF, placing the pebble at F. Turn 7: Otto is forced to remove stick FA, placing the pebble at A. Turn 8: Ada removes stick AC, placing the pebble at C. Turn 9: Otto is forced to remove stick CE, placing the pebble at E. Turn 10: Ada removes stick EA, leaving no remaining sticks. At this point, there are no valid moves, so Ada will win because every one of Otto’s moves is forced.
See Also
| 2016 UMO (Problems • Answer Key • Resources) | ||
| Preceded by First Problem |
Followed by Problem 2 | |
| 1 • 2 • 3 • 4 • 5 • 6 | ||
| All UMO Problems and Solutions | ||
