Randomly generated number N defines the initial quantity of matches (or marbles, tokens, cards etc) on the table.
Assume N< 333
Two players, A & B take turns taking some matches from the pile, provided the quantity taken is an integer power of 2, i.e. 1, 2, 4…
Winner is the player taking the last batch.
Would you prefer to be the 1st player?
What would be your winning strategy?
My strategy would be to always leave my opponent with a multiple of 3 objects remaining. All powers of 2 are either 1 mod 3 or 2 mod 3, so if he starts with a multiple of 3 this is achievable. If he takes 1 mod 3 objects, I take 2 and vice versa.
He would never win, since no multiple of 3 is an integer power of 2, and eventually would be forced to leave me with 1 or 2 objects, which I'd take for the win.
Assuming I don't know the value of N before I have to choose, I'd prefer to go first, which would give me a 2/3 chance of winning (if I know the value of N, obviously I'd prefer to go second if N is a multiple of 3).

Posted by tomarken
on 20220221 08:19:14 