MathDB

Positive integers

n

and

k

satisfying

n\geq 2k+1

are known to Alice. There are

n

cards with numbers from

1

n

, randomly shuffled as a deck, face down. On her turn, she does the following in order:
(i) She first flips over the top card of the deck, and puts it face up on the table. (ii) Then, if Alice has not signed any card, she can sign the newest card now.
The game ends after

2k+1

turns, and Alice must have signed on some card. Let

A

be the number on the signed cards, and

M

be the

(k+1)^{\textup{st}}

largest number among all

2k+1

face-up cards. Alice's score is

|M-A|

, and she wants the score to be as close to zero as possible.
For each

(n,k)

, find the smallest integer

d=d(n,k)

such that Alice has a strategy to guarantee her score no greater than

d

.
Proposed by usjl

Problem Statement