AoPS - Problem

Source: 2022 Taiwan TST Round 3 Mock Exam Problem 6

Tags: combinatorics, Taiwan

USJL

06.07.2022 08:12

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

CANBANKAN

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?

USJL

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.

CANBANKAN

14.07.2022 00:47

Rephrase the problem as follows: Bob picks and orders $2k+1$ distinct integers in $\{1,\cdots,N\}$ unknown to Alice, call $a_1,\cdots,a_{2k+1}$. He reveals the cards in the order $a_1,\cdots,a_{2k+1}$, so when he reveals $a_j$ Alice knows $a_1,\cdots,a_j$. At this time, Alice can choose to select $A=a_j$ if she hasn't chosen $A$ already. She must choose one card. Let $M$ be the median of $a_1,\cdots,a_{2k+1}$. Alice wishes to minimize $|A-M|$ while Bob wishes to maximize $|A-M|$. As a function of $N,k$ what is the minimum value of $f(N,k)=|A-M|$ that Alice can achieve? Claim: If $N\le 3k+1, f(N,k)=N-(2k+1)$ Proof: Clearly, the median and one of the numbers Bob picks is between $k+1, N-k$, and their difference is at most $N-(2k+1)$. It remains to show this is achievable. (WLOG Bob can change cards not shown to Alice) Consider the sequence $(k+1, N-k, k, N-k+1, k-1, \cdots, 1)$. If Alice doesn't sign a card, Bob plays cards in the order of the sequence. If Alice signs a card $\le k+1$ then Bob just makes sure $N-k, \cdots, N$ are all in the first $2k+1$ cards so the median is $N-k$. If Alice signs the last card, her score is $k \le N-(2k+1)$ Now I claim $f(3k+t,k)=k+\lfloor \frac{t-1}{2} \rfloor$ for all $t\ge 1$. Bob's strategy: WLOG $t=2m+1$ is odd, since $t+1$ asks for the same answer and we can apply the strategy for $t$ on $t+1$. Consider the sequence $(k+m+1, 2k+m+2, k+m, 2k+m+3, \cdots, m+2, 3k+m+1,1)$ check that it works. Alice's strategy: WLOG $t=2m$ is even, and we want to show the answer is $k+m-1$. Note the median must be in $[k+1, 2k+2m]$. This means if Bob picks a number in $[(2k+2m)-(k+m-1), k+1+(k+m-1)] = [k+m+1, 2k+m]$, Alice immediately signs it. Otherwise, call a number small if it is in $[1,k+m]$ and large if it is in $[2k+m+1, 3k+2m]$. There must be at least $k+1$ small numbers or at least $k+1$ large numbers. Once Bob has picked $k+1$ small numbers, Alice signs that small number and that guarantees the difference is at most $(k+m)-1$.

USJL

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.