Difference between revisions of "2012 IMO Problems/Problem 3"
Line 31: | Line 31: | ||
This completes the induction. In particular, since <math>g(m)<1.999^{k+1}</math> at all times, A will never indicate that <math>x\neq i</math> more that <math>k</math> times in a row. So player B will never be able to rule out any element of <math>\{1,2,\dots,N\}</math> and submit a set of <math>n</math> integers that are guaranteed to contain <math>x</math>. | This completes the induction. In particular, since <math>g(m)<1.999^{k+1}</math> at all times, A will never indicate that <math>x\neq i</math> more that <math>k</math> times in a row. So player B will never be able to rule out any element of <math>\{1,2,\dots,N\}</math> and submit a set of <math>n</math> integers that are guaranteed to contain <math>x</math>. | ||
+ | |||
+ | ==See Also== | ||
+ | |||
+ | {{IMO box|year=2012|num-b=2|num-a=4}} |
Latest revision as of 01:23, 19 November 2023
The liar’s guessing game is a game played between two players A and B. The rules of the game depend on two positive integers and
which are known to both players.
At the start of the game the player A chooses integers and
with
. Player A keeps
secret, and truthfully tells
to the player B. The player B now tries to obtain information about
by asking player A questions as follows: each question consists of B specifying an arbitrary set
of positive integers (possibly one specified in some previous question), and asking A whether
belongs to
. Player B may ask as many questions as he wishes. After each question, player A 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 B has asked as many questions as he wants, he must specify a set of at most
positive integers. If
, then B wins; otherwise, he loses. Prove that:
(a) If then B has a winning strategy.
(b) There exists a positive integer such that for every
there exists an integer
for which B cannot guarantee a victory.
Solution to Part (a)
It suffices to show that there is a winning strategy for , as a winning strategy for any
easily gives a winning strategy for
.
Player B first divides all integers through
into
nonempty sets
, where
is some binary string of length
. On the
question for
, player B asks whether the set containing
is labeled with a string that has a
in the
position. After asking these questions, there is one set that player A must indicate does not contain
at
times in a row; WLOG we may assume this set is
.
On the next question, B asks if . If A says 'no', then B can rule out
. If A says 'yes', then B asks if
. If A says 'no', then B can rule out
. If A says 'yes', then B asks if
. If A says 'no', then B can rule out
, while if A says 'yes', B can rule out
.
In any case, B can ascertain that for some string
, thus reducing the number of possibilities for
. Player B can repeat this procedure as long as at least
elements remain, eventually reducing the number of possible values of
to at most
.
Solution to Part (b)
Take sufficiently large so that there is some positive integer
with
but
.
Player A sets . Let
denote the number of times in a row that A has just indicated that
. In other words, if A indicates on the
step that
was in a set containing
, then
, while if A indicates otherwise, we would have
.
At the step, player A makes a decision so as to minimize the sum:
I claim that, by using this strategy, A will preserve the invariant that
. We can prove this by induction on
.
Note that initially,
.
Suppose that . Note that if B asks if
for some
, then the two possibilities for
are:
and
Note that
. Therefore, we have that:
This completes the induction. In particular, since at all times, A will never indicate that
more that
times in a row. So player B will never be able to rule out any element of
and submit a set of
integers that are guaranteed to contain
.
See Also
2012 IMO (Problems) • Resources | ||
Preceded by Problem 2 |
1 • 2 • 3 • 4 • 5 • 6 | Followed by Problem 4 |
All IMO Problems and Solutions |