2016 USAMO Problems/Problem 6

Problem

Integers $n$ and $k$ are given, with $n\ge k\ge 2.$ You play the following game against an evil wizard.

The wizard has $2n$ cards; for each $i = 1, ..., n,$ there are two cards labeled $i.$ Initially, the wizard places all cards face down in a row, in unknown order.

You may repeatedly make moves of the following form: you point to any $k$ of the cards. The wizard then turns those cards face up. If any two of the cards match, the game is over and you win. Otherwise, you must look away, while the wizard arbitrarily permutes the $k$ chosen cards and turns them back face-down. Then, it is your turn again.

We say this game is $\textit{winnable}$ if there exist some positive integer $m$ and some strategy that is guaranteed to win in at most $m$ moves, no matter how the wizard responds.

For which values of $n$ and $k$ is the game winnable?

Solution

This problem needs a solution. If you have a solution for it, please help us out by adding it. We first prove that the game is winnable whenever $n > k$ by demonstrating a winning strategy in this case.

On the $i$ th move, choose the $k$ cards in positions $i$ through $i+k-1.$ Assuming that you do not win on any earlier move, repeat this for $1\le i \le 2n-k+1.$

Assume that you did not win on any of the first $2n-k+1$ moves, as described above. Let $j$ be an integer such that $1\le j\le 2n-k.$ On the $j$ th move, the wizard revealed the cards in positions $j$ through $j+k-1,$ so you know the labels of all of these cards (just not necessarily in the right order). Then, on the $(j+1)$ th move, the wizard revealed the cards in positions $j+1$ through $j+k,$ which means that you get to see all of the cards that were moved to positions $j+1$ through $j+k.$ This means that you can uniquely determine the label on card $j,$ since you knew all of the labels from $j$ through $j+k-1,$ and the card in position $j$ could not have moved anywhere else since your last move.

It follows that, after the sequence of $2n-k+1$ moves described above, you know the labels on the first $2n-k$ cards. Since $n > k,$ we have $2n-k \ge n+1,$ so there must be a pair of cards with matching labels in this group of $2n-k$ cards, by the Pigeonhole Principle. On your next move, you can pick a group of $k$ cards that includes that pair of matching cards, and you win.

We have created a strategy that is guaranteed to win in at most $m = 2n-k+2$ moves. Thus, the game is winnable for all $n > k.$

These problems are copyrighted © by the Mathematical Association of America, as part of the American Mathematics Competitions.

2016 USAMO (Problems • Resources)
Preceded by Problem 5	Last Problem
1 • 2 • 3 • 4 • 5 • 6
All USAMO Problems and Solutions

Page

Toolbox

Search

2016 USAMO Problems/Problem 6

Problem

Solution

See also