### IMO Shortlist 2012 problem C6

Kvaliteta:

Avg: 0.0Težina:

Avg: 8.0 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 integers and with Player keeps secret, and truthfully tells to player . Player now tries to obtain information about by asking player questions as follows: each question consists of specifying an arbitrary set of positive integers (possibly one specified in some previous question), and asking whether belongs to . Player may ask as many 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 wants; 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:

1. If then can guarantee a win.

2. For all sufficiently large , there exists an integer such that cannot guarantee a win.

Proposed by David Arthur, Canada

At the start of the game chooses integers and with Player keeps secret, and truthfully tells to player . Player now tries to obtain information about by asking player questions as follows: each question consists of specifying an arbitrary set of positive integers (possibly one specified in some previous question), and asking whether belongs to . Player may ask as many 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 wants; 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:

1. If then can guarantee a win.

2. For all sufficiently large , there exists an integer such that cannot guarantee a win.

Proposed by David Arthur, Canada

Source: Međunarodna matematička olimpijada, shortlist 2012