A problem from the Leningrad Mathematical Olympiad: A and B take turns removing matches from a pile. The pile starts with 500 matches, A goes first, and the player who takes the last match wins. The catch is that the quantity that each player withdraws on a given turn must be a power of 2. Does either player have a winning strategy?
Answer: https://www.futilitycloset.com/2021/05/14/match-point-3/
My idea is for one player to leave an odd number (>1) of matches for the other, so if player 1 takes max 256 (2^8) matches at torn 1, then whatever player 2 takes , follow it by taking 1 (2^0) match next, then whatever player 2 takes, take the max possible thereafter leaving an odd number (>3) for player 2 (or if player 2 takes 1 also, then copy until end.
ReplyDeleteI haven't tried this but it might work! I'm sure someone can work out an algo to solve it!
Good problem
Ian J
Robbo
ReplyDeleteNote that if you leave him 3 he loses. Also note, no power of 2 is a multiple of 3. A winning strategy is to take 2 to leave him 498 which is a multiple of 3, and therefore not a power of 2 win for him. Whatever he does, take either 1 or 2 and leave him with a multiple of 3 again. He can never win so eventually he must leave you a power of 2 winning position.
Nice puzzle.
PS Leningrad?