Today we discuss some more Olympiad problems:
Italy TST 2009
A and B play the following game. First A writes a permutation of the numbers from 1 to n, where n is a fixed positive integer greater than 1. In each player’s turn, he or she must write a sequence of numbers that has not been written yet such that either:
a) The sequence is a permutation of the sequence the previous player wrote, OR
b) The sequence is obtained by deleting one number from the previous player’s sequence
For example, if A first writes 4123, B could write 3124 or 413. The player who cannot write down a sequence loses. Determine who has a winning strategy.
Let us focus on the endgame. when n = 2, B wins after A's first move B deletes the number 2 and is left with the sequence {1}. Then A has no move.
With this end game, we now create a progression using induction Suppose B wins n = k, then we want a strategy for n = k + 1 B's aim is to make A be the first player to delete a number from the sequence. Then from this point the game is reduced to a game with k numbers. How to do this, for every sequence that A writes for k+1 numbers, there will be a permutation that A has not written because permutations are factorial(k+1) which is even. For example, one such sequence would be to write it backwards.
Another Olympiad question:
The Y2K Game is played on a 1 × 2000 grid as follows. Two players in turn write either an S or an O in an empty square. The first player who produces three consecutive boxes that spell SOS wins.
If all boxes are filled without producing SOS then the game is a draw. Prove that the second player has a winning strategy.
Let us say an empty square is bad when it leads to the formation of the given pattern SOS.
The claim here is that an empty square is bad only when it occurs in between S empty empty S formation that we denote by S__S.
The claim follows from the configuration that an empty square is bad when it is flanked by an S on one side and an empty on the other. Clearly both the empty squares above is bad.
Italy TST 2009
A and B play the following game. First A writes a permutation of the numbers from 1 to n, where n is a fixed positive integer greater than 1. In each player’s turn, he or she must write a sequence of numbers that has not been written yet such that either:
a) The sequence is a permutation of the sequence the previous player wrote, OR
b) The sequence is obtained by deleting one number from the previous player’s sequence
For example, if A first writes 4123, B could write 3124 or 413. The player who cannot write down a sequence loses. Determine who has a winning strategy.
Let us focus on the endgame. when n = 2, B wins after A's first move B deletes the number 2 and is left with the sequence {1}. Then A has no move.
With this end game, we now create a progression using induction Suppose B wins n = k, then we want a strategy for n = k + 1 B's aim is to make A be the first player to delete a number from the sequence. Then from this point the game is reduced to a game with k numbers. How to do this, for every sequence that A writes for k+1 numbers, there will be a permutation that A has not written because permutations are factorial(k+1) which is even. For example, one such sequence would be to write it backwards.
Another Olympiad question:
The Y2K Game is played on a 1 × 2000 grid as follows. Two players in turn write either an S or an O in an empty square. The first player who produces three consecutive boxes that spell SOS wins.
If all boxes are filled without producing SOS then the game is a draw. Prove that the second player has a winning strategy.
Let us say an empty square is bad when it leads to the formation of the given pattern SOS.
The claim here is that an empty square is bad only when it occurs in between S empty empty S formation that we denote by S__S.
The claim follows from the configuration that an empty square is bad when it is flanked by an S on one side and an empty on the other. Clearly both the empty squares above is bad.
No comments:
Post a Comment