MathDB
Problems
Contests
International Contests
KoMaL A Problems
KoMaL A Problems 2019/2020
A. 757
A. 757
Part of
KoMaL A Problems 2019/2020
Problems
(1)
Game on [2^n-1] and [2^{n+1}-1]
Source: KöMaL A. 757
10/12/2019
For every
n
n
n
non-negative integer let
S
(
n
)
S(n)
S
(
n
)
denote a subset of the positive integers, for which
i
i
i
is an element of
S
(
n
)
S(n)
S
(
n
)
if and only if the
i
i
i
-th digit (from the right) in the base two representation of
n
n
n
is a digit
1
1
1
.Two players,
A
A
A
and
B
B
B
play the following game: first,
A
A
A
chooses a positive integer
k
k
k
, then
B
B
B
chooses a positive integer
n
n
n
for which
2
n
⩾
k
2^n\geqslant k
2
n
⩾
k
. Let
X
X
X
denote the set of integers
{
0
,
1
,
…
,
2
n
−
1
}
\{ 0,1,\dotsc ,2^n-1\}
{
0
,
1
,
…
,
2
n
−
1
}
, let
Y
Y
Y
denote the set of integers
{
0
,
1
,
…
,
2
n
+
1
−
1
}
\{ 0,1,\dotsc ,2^{n+1}-1\}
{
0
,
1
,
…
,
2
n
+
1
−
1
}
. The game consists of
k
k
k
rounds, and in each round player
A
A
A
chooses an element of set
X
X
X
or
Y
Y
Y
, then player
B
B
B
chooses an element from the other set. For
1
⩽
i
⩽
k
1\leqslant i\leqslant k
1
⩽
i
⩽
k
let
x
i
x_i
x
i
denote the element chosen from set
X
X
X
, let
y
i
y_i
y
i
denote the element chosen from set
Y
Y
Y
.Player
B
B
B
wins the game, if for every
1
⩽
i
⩽
k
1\leqslant i\leqslant k
1
⩽
i
⩽
k
and
1
⩽
j
⩽
k
1\leqslant j\leqslant k
1
⩽
j
⩽
k
,
x
i
<
x
j
x_i<x_j
x
i
<
x
j
if and only if
y
i
<
y
j
y_i<y_j
y
i
<
y
j
and
S
(
x
i
)
⊂
S
(
x
j
)
S(x_i)\subset S(x_j)
S
(
x
i
)
⊂
S
(
x
j
)
if and only if
S
(
y
i
)
⊂
S
(
y
j
)
S(y_i)\subset S(y_j)
S
(
y
i
)
⊂
S
(
y
j
)
. Which player has a winning strategy?Proposed by Levente Bodnár, Cambridge
combinatorics