Simple Games are not always Simple.
"Would you want to play a game with me?" Alex said to Bob.
"What game is it? Tell me!" Bob said excitedly.
"It is very simple. I have chosen a positive integer, which is very large, and you are supposed to guess it!" Alex said cheerfully to Bob.
"Seriously? That's impossible!" Bob said sadly.
"Fine. I will make the game easier just for you. I will say what is the remainder when my chosen number is divided by increasing prime numbers . At any point of time in the game, you have one chance to say what remainder will the next prime number give when being divided by my chosen number. If you answer correctly, you win the game. If you answer incorrectly, or fail to guess until the end of the game, then you lose. As you might be cunning and listen to all the modulus of the prime numbers just before my chosen number, I have the right of choosing how much information to tell you, but I will definitely say more than half of the prime numbers within the chosen number."
Bob is a very logical person, so he would not make any guesses until he is certain of the remainder.
Assuming this game is played optimally, who will win?
Note: Bob does not need to find out Alex's chosen number, he just needs to find out what remainder will the next prime number give when divided by the chosen number. So if for example Alex said " 2(mod 3) ", Bob needs to find out what remainder will mod 5 give. If he cannot deduce the remainder, he will keep on listening to Alex's statements until he is sure of the remainder.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
Sadly, the modulus are all prime numbers, so you cannot infer one of Alex's statements to another. There are always more than one possible remainder for the next statement Alex will say, and once he says the statement, you cannot use the information to help you deduce the next remainder! Hence by induction, and because Bob will not hear the modulus of all the prime numbers below the chosen number (giving him uncertainty), Bob will never be certain of the remainder, so he would not make a guess, making Alex win the game.