Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2016 USAMO Problems/Problem 6"

(Created page with "==Problem== Integers <math>n</math> and <math>k</math> are given, with <math>n\ge k\ge 2.</math> You play the following game against an evil wizard. The wizard has <math>2n</...")
 
Line 11: Line 11:
 
==Solution==
 
==Solution==
 
{{solution}}
 
{{solution}}
 +
We first prove that the game is winnable whenever <math>n > k</math> by demonstrating a winning strategy in this case.
 +
 +
On the <math>i</math>th move, choose the <math>k</math> cards in positions <math>i</math> through <math>i+k-1.</math> Assuming that you do not win on any earlier move, repeat this for <math>1\le i \le 2n-k+1.</math>
 +
 +
Assume that you did not win on any of the first <math>2n-k+1</math> moves, as described above. Let <math>j</math> be an integer such that <math>1\le j\le 2n-k.</math> On the <math>j</math>th move, the wizard revealed the cards in positions <math>j</math> through <math>j+k-1,</math> so you know the labels of all of these cards (just not necessarily in the right order). Then, on the <math>(j+1)</math>th move, the wizard revealed the cards in positions <math>j+1</math> through <math>j+k,</math> which means that you get to see all of the cards that were moved to positions <math>j+1</math> through <math>j+k.</math> This means that you can uniquely determine the label on card <math>j,</math> since you knew all of the labels from <math>j</math> through <math>j+k-1,</math> and the card in position <math>j</math> could not have moved anywhere else since your last move.
 +
 +
It follows that, after the sequence of <math>2n-k+1</math> moves described above, you know the labels on the first <math>2n-k</math> cards. Since <math>n > k,</math> we have <math>2n-k \ge n+1,</math> so there must be a pair of cards with matching labels in this group of <math>2n-k</math> cards, by the Pigeonhole Principle. On your next move, you can pick a group of <math>k</math> cards that includes that pair of matching cards, and you win.
 +
 +
We have created a strategy that is guaranteed to win in at most <math>m = 2n-k+2</math> moves. Thus, the game is winnable for all <math>n > k.</math>
  
 
{{MAA Notice}}
 
{{MAA Notice}}
 
==See also==
 
==See also==
 
{{USAMO newbox|year=2016|num-b=5|aftertext=|after=Last Problem}}
 
{{USAMO newbox|year=2016|num-b=5|aftertext=|after=Last Problem}}

Revision as of 19:11, 27 April 2016

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.$

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

See also

2016 USAMO (Problems • Resources)
Preceded by
Problem 5 		Last Problem
1 • 2 • 3 • 4 • 5 • 6
All USAMO Problems and Solutions
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2016_USAMO_Problems/Problem_6&oldid=78304"