那 Bob 呢？
What About Bob?
题目详情
Two players, Alice and Bob, will play a game. Alice chooses any integer from 1 thru 9 (inclusive; all intervals are inclusive). Bob then chooses any integer from 1 thru 9, but can’t pick the number Alice just chose. Then Alice chooses any number from 1 thru 9 but can’t pick the number Bob just chose. They go on in this fashion and keep a running tally of all the chosen numbers so far.
The first player to make this running tally reach exactly N (some positive integer) wins the game. A player can never choose a number that would make the tally be greater than N, and if a player cannot validly choose any numbers under the rules, then he/she loses the game.
To clarify, numbers can potentially be repeated during the game, but just not consecutively. There is no guarantee that Bob will get a turn (for small enough N).
If Alice and Bob each play with perfect strategies, what are the 3 smallest values of N such that Bob wins the game?
Two players, Alice and Bob, will play a game. Alice chooses any integer from 1 thru 9 (inclusive; all intervals are inclusive). Bob then chooses any integer from 1 thru 9, but can’t pick the number Alice just chose. Then Alice chooses any number from 1 thru 9 but can’t pick the number Bob just chose. They go on in this fashion and keep a running tally of all the chosen numbers so far.
The first player to make this running tally reach exactly N (some positive integer) wins the game. A player can never choose a number that would make the tally be greater than N, and if a player cannot validly choose any numbers under the rules, then he/she loses the game.
To clarify, numbers can potentially be repeated during the game, but just not consecutively. There is no guarantee that Bob will get a turn (for small enough N).
If Alice and Bob each play with perfect strategies, what are the 3 smallest values of N such that Bob wins the game?
解析
This month’s puzzle proved pretty tricky, and we received many submissions which were very close but not quite right. The smallest 3 numbers for which Bob will win the game are 11, 22, and 32. In fact, for larger numbers, Bob will win if N is congruent to 11, 22, or 0 mod 32.
*Alice can obviously win for N=1 up to N=9, and she can also win when N=10 if she says 5 (forcing Bob to pick something other than 5).
*When N=11, Bob wins: If Alice picks some k>1, Bob will be able to pick 11-k. If Alice picks 1, Bob will be able to pick 5.
*For N = 12 up to N = 20, Alice can win by picking the number which gives Bob the tally of N-11. For N = 21, Alice can also win if she picks 5, since Bob must pick something other than 5. If he picks anything other than 8, Alice can win easily. If he picks 8, Alice can counter with 4, Then Bob with 2, then Alice with 1, and thus Alice wins anyway.
*When N = 22, Bob wins, for similar reasons as when N = 11.
*When N = 32, Bob wins as well. If Alice says any k other than 5, Bob can say 10-k. If Alice says 5, Bob can say 8, leaving Alice with a remaining sum of 19 but unable to say 8, which again forces a Bob win.
Congratulations to everyone who solved this month’s puzzle!
Original Explanation
This month’s puzzle proved pretty tricky, and we received many submissions which were very close but not quite right. The smallest 3 numbers for which Bob will win the game are 11, 22, and 32. In fact, for larger numbers, Bob will win if N is congruent to 11, 22, or 0 mod 32.
*Alice can obviously win for N=1 up to N=9, and she can also win when N=10 if she says 5 (forcing Bob to pick something other than 5).
*When N=11, Bob wins: If Alice picks some k>1, Bob will be able to pick 11-k. If Alice picks 1, Bob will be able to pick 5.
*For N = 12 up to N = 20, Alice can win by picking the number which gives Bob the tally of N-11. For N = 21, Alice can also win if she picks 5, since Bob must pick something other than 5. If he picks anything other than 8, Alice can win easily. If he picks 8, Alice can counter with 4, Then Bob with 2, then Alice with 1, and thus Alice wins anyway.
*When N = 22, Bob wins, for similar reasons as when N = 11.
*When N = 32, Bob wins as well. If Alice says any k other than 5, Bob can say 10-k. If Alice says 5, Bob can say 8, leaving Alice with a remaining sum of 19 but unable to say 8, which again forces a Bob win.
Congratulations to everyone who solved this month’s puzzle!