Teacher version IMC preparation seminar Games, processes, invariants Mihail Poplavskyi, [email protected] Each of the following games are played by two players, I and II. Player I always starts and players alternate turns until one of them wins or loses. If a player cannot make a move then he loses. Winning and losing positions. Def. Consider any game with finite number of possibilities. Then any possible state we can call winning (W) or losing (L) depending on whether there is a winning strategy starting with this state. If we have any game with finite number of states, then we can try to identify each position with W or L by the following algorithm: - The last state is always L. - If there is a move from unidentified state to L, then this state is W. - If any move from unidentified state leads to W, then this state is L. Warm-up 1. Two players start with two piles of m and n coins respectively. On each move it is allowed to take from one pile any amount of coins which is a divisor of coins number in the other pile. Who will win for (a) m = 101, n = 201 (b) m = 100, n = 201 (Folklor, ) Solution: By the following proposition in case (a) second player wins, and first player does in case (b). Proposition. Positions with odd amounts of coins in both piles are losing positions. Positions with odd amount in one pile and even in the other pile are winning positions. Proof. We will proof both statements by induction over total amount S of coins. If S = 1, then there is only one case of piles (1, 0) and it is obviously winning position. Assume now that the statement is true for all S ≤ k. We will prove the statement for S = k + 1. If both amounts are odd, then it is evident that current player can take only odd number of coins from one of the piles. It will yield to the position with less total amount and odd+even numbers in piles. By induction assumption the opponent can win the game starting with this position, so current player will lose with any move, and odd+odd position is a losing one. If one start with odd+even position, then he can take one coin from ’even’ pile and end up with odd+odd position and S = k, which is losing for his opponent. Therefore, odd+even position is a winning one. Problems Teacher version 2. Alice and Bob play a game in which they take turns removing stones from a heap that initially has n stones. The number of stones removed at each turn must be one less than a prime number. The winner is the player who takes the last stone. Alice plays first. Prove that there are infinitely many n such that Bob has a winning strategy. (For example, if n = 17, then Alice might take 6 leaving 11; then Bob might take 1 leaving 10; then Alice can take the remaining stones to win.) (Putnam, 2006, A2) Solution: Since this is a game with finite number of possibilities, there is always a winning strategy, either for the first player, or for the second. Arguing by contradiction, let us assume that there are only finitely many ns, say n1 , n2 , . . . , nm for which Bob has a winning strategy. Then for every other non-negative integer n, Alice must have some move on a heap of n stones leading to a position in which the second player wins. This means that any other integer n is of the form p − 1 + nk for some prime p and some 1 ≤ k ≤ m. We will prove that this is not the case. Choose an integer N greater than all the nk ’s. Solution 1. Let p1 , p2 , . . . , pN be the first N prime numbers. By the Chinese Remainder Theorem, there exists a positive integer x such that x ≡ −1 (mod p21 ) x ≡ −2 (mod p22 ) ... x ≡ −N (mod p2N ). Then the number x + N − 1 is not of the form p − 1 + nk , because each of the numbers x + N − nk is composite, being a multiple of p2N −nk . We have reached a contradiction, which proves the desired conclusion. Solution 2. Take x = (N + 1)! − 1, assuming that N > 2 and N > nk + 1. Otherwise take bigger N at the beginning. Then x is not of the form p − 1 + nk , because each of the numbers x + 1 + N − nk is divisible by N − nk , bigger than N − nk and N − nk ≥ 2. 3. At a round table there are 2014 boys playing a game with a deck of n cards. Initially, one boy holds all the cards. At each turn, if at least one boy holds at least two cards, one of these boys must pass a card to each of his two neighbours. The game ends when and only when each boy is holding at most one card. (a) Prove that if n ≥ 2014, then the game cannot end. (b) Prove that if n < 2014, then the game must end. (IMO 1994, Shortlist) Teacher version Solution: (a) If n > 2014, it follows from the pigeon hole principle that there is one boy holding at least two cards. Hence the game cannot end. Suppose n = 2014. Label the boys B1 , B2 , . . . , B2014 and let B1 holds all the cards initially. Define the current value of a card to be i if it is being held by Bi . Initially, the sum of the total current values of the cards is 2014. If a boy other than B1 or B2014 passes cards, the sum does not change ( 2 ∗ i → (i − 1) + (i + 1)). If B1 or B2014 passes cards, sum increases or decreases by 2014. Hence it is a good idea to choose as an invariant the residue of the sum of the values of all cards modulo 2014. If the game is to end, each boy must be holding exactly one card, and sum have to be equal 1 + 2 + . . . + 2014 = 1012 ∗ 2015 ≡ 1012 (mod 2014). But this cannot happen, since the final sum is not divisible by 2014, whereas the initial one is. Hence the game cannot terminate. (b) Whenever a card is passed from one boy to another for the first time, let both sign their names on it. Thereafter, if one of them is passing cards and holding this one, he must pass it back to the other. Thus a signed card is stuck between two neighbouring boys. If n < 2014, there are two neighbouring boys who never exchanged cards, because there are exactly 2014 pairs of them. For the game to go on forever, at least one boy must pass cards infinitely often. Hence there exists a boy who does so, while a neighbour of him passes cards only a finite number of times. When the neighbour eventually stops passing cards, he will continue to accumulate cards indefinitely. This is clearly impossible. Homework 1. A two player game is played on a m × n grid. A token starts in the bottom left corner of the grid. On each turn, a player can move the token one or two units to the right, or to the leftmost square of the above row. The last player who is able to move wins. Determine which positions of the token are winning positions and which are losing. 2. Two people, A and B, play a game in which the probability that A wins is p, the probability that B wins is q, and the probability of a draw is 1 − p − q. At the beginning, A has m dollars and B has n dollars. At the end of each game, the winner takes a dollar from the loser. If A and B agree to play until one of them loses all his/her money, what is the probability of A winning all the money? 3. Consider a polyhedron with at least five faces such that exactly three edges emerge from each vertex. Two players play the following game: the players sign their names alternately on precisely one face that has not been previously signed. The winner is the player who succeeds in signing the name on three faces that share Teacher version a common vertex. Assuming optimal play, prove that the player who starts the game always wins. 4. A solitaire game is played on an m × n regular board, using mn markers that are white on one side and black on the other. Initially, each square of the board contains a marker with its white side up, except for one corner square, which contains a marker with its black side up. In each move, one may take away one marker with its black side up but must then turn over all markers that are in squares having an edge in common with the square of the removed marker. Determine all pairs (m, n) of positive integers such that all markers can be removed from the board.
© Copyright 2020