那 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!
英文解析
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!