Maths Olympiad Prep

Library / /374 of 520

Combinatorics Difficulty 7.2 National olympiad, round 2 Find the answer

Let nn be a positive integer. A pseudo-Gangnam\emph{pseudo-Gangnam} Style} is a dance competition between players AA and BB. At time 00, both players face to the north. For every k1k\ge 1, at time 2k12k-1, player AA can either choose to stay stationary, or turn 9090^{\circ} clockwise, and player BB is forced to follow him; at time 2k2k, player BB can either choose to stay stationary, or turn 9090^{\circ} clockwise, and player AA is forced to follow him.

After time nn, the music stops and the competition is over. If the final position of both players is north or east, AA wins. If the final position of both players is south or west, BB wins. Determine who has a winning strategy when:

(a) n=20132012n=2013^{2012}

(b) n=20132013n=2013^{2013}

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

To determine who has a winning strategy, we need to analyze the final position of both players after n n moves. The key observation is that the net rotation of both players depends on the parity of n n .

1. Understanding the Moves:
- At odd times 2k1 2k-1 , player A A can either stay stationary or turn 90 90^\circ clockwise, and player B B follows.
- At even times 2k 2k , player B B can either stay stationary or turn 90 90^\circ clockwise, and player A A follows.

2. Net Rotation Analysis:
- Each pair of moves (one by A A and one by B B ) results in a net rotation of 0 0^\circ or 90 90^\circ clockwise.
- If A A and B B both choose to turn 90 90^\circ clockwise, the net rotation is 180 180^\circ .
- If one chooses to turn and the other stays, the net rotation is 90 90^\circ .
- If both stay, the net rotation is 0 0^\circ .

3. Modulo 4 Analysis:
- The direction faced by the players after n n moves depends on nmod4 n \mod 4 :
- n0(mod4) n \equiv 0 \pmod{4} : Final direction is North.
- n1(mod4) n \equiv 1 \pmod{4} : Final direction is East.
- n2(mod4) n \equiv 2 \pmod{4} : Final direction is South.
- n3(mod4) n \equiv 3 \pmod{4} : Final direction is West.

4. **Case (a): n=20132012 n = 2013^{2012} **
- Calculate 20132012mod4 2013^{2012} \mod 4 :
20131(mod4)    20132012120121(mod4) 2013 \equiv 1 \pmod{4} \implies 2013^{2012} \equiv 1^{2012} \equiv 1 \pmod{4}
- Since 201320121(mod4) 2013^{2012} \equiv 1 \pmod{4} , the final direction is East.
- Therefore, A A wins.

5. **Case (b): n=20132013 n = 2013^{2013} **
- Calculate 20132013mod4 2013^{2013} \mod 4 :
20131(mod4)    20132013120131(mod4) 2013 \equiv 1 \pmod{4} \implies 2013^{2013} \equiv 1^{2013} \equiv 1 \pmod{4}
- Since 201320131(mod4) 2013^{2013} \equiv 1 \pmod{4} , the final direction is East.
- Therefore, A A wins.

The final answer is A \boxed{ A } wins in both cases.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.