Positive integers $n$ and $k$ satisfying $n\geq 2k+1$ are known to Alice. There are $n$ cards with numbers from $1$ to $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
Source: 2022 Taiwan TST Round 3 Mock Exam Problem 6
Tags: combinatorics, Taiwan
11.07.2022 18:25
To clarify, is the following true: Alice can only see the numbers on the first $2k+1$ cards, and SIGN ONLY ON ONE CARD. When she has flipped $j$ cards, must she sign on the $j+1$th card?
11.07.2022 19:41
CANBANKAN wrote: To clarify, is the following true: Alice can only see the numbers on the first $2k+1$ cards, and SIGN ONLY ON ONE CARD. When she has flipped $j$ cards, must she sign on the $j+1$th card? (1) Yes, only one card. (2) After she flipped the $j$-th card, she may decide whether or not to sign on the $j$-th card before flipping the $j+1$-th card.
14.07.2022 00:47
14.07.2022 04:42
Some small comments: (1) In fact there is a way to unify Bob's strategy in both cases. Basically one can show that if $p,q\geq 0$ are integers with $p+q=n-k+1$ and $q\geq k$, then Bob can always make sure that $|X-M|\geq \min(p,q)$. This evaluates exactly to the answer we expect. (2) This was sent to IMO 2021 but was not taken into the shortlist. My guess is that the form of the answer is not that pleasant to deal with, which is a bit unfortunate. I guess the shortlisted combi problems all turned out to be pretty decent (aside from the two purely constructive problems which I generally dislike XD)(and now you know my opinion on 2022 IMO P6). (3) CANBANKAN wrote:
Lol yeah when we were arranging the problems we also noticed that we had several hard (as in >= IMO P2/5) combi problems where it's harder than usual to guess the answer: https://artofproblemsolving.com/community/c6h2820940p24925904 https://artofproblemsolving.com/community/c6h2820160p24917798 I personally struggled the most with coming up a strategy for Bob though :/ once I've done $k=1,2$ I was pretty convinced that I had the right guess.