As we talked about here, there was plans afoot to group-solve online an interesting and problem from the IMO. The online discussion going on *right now* (unless, of course, you’re reading this later). They decided to work on Question 3. Here it is:

**Problem 3.** The *liar’s guessing game* is a game played between two players and . The rules of the game depend on two positive integers and which are known to both players.

At the start of the game, chooses two integers and with . Player keeps secret, and truthfully tells to player . Player now tries to obtain information about by asking player A questions as follows. Each question consists of specifying an arbitrary set of positive integers (possibly one specified in a previous question), and asking whether belongs to . Player may ask as many such questions as he wishes. After each question, player must immediately answer it with *yes* or *no*, but is allowed to lie as many times as she wishes; the only restriction is that, among any consecutive answers, at least one answer must be truthful.

After has asked as many questions as he wants, he must specify a set of at most positive integers. If belongs to , then wins; otherwise, he loses. Prove that:

- If , then can guarantee a win.
- For all sufficiently large , there exists an integer such that cannot guarantee a win.

Check out (and join in on) the discussion here.

### Like this:

Like Loading...

*Related*