Maths Olympiad Prep

Library / /107 of 115

Combinatorics Difficulty 7.8 National olympiad, round 2 Find the answer

Integers nn and kk are given, with nk2.n\ge k\ge 2. You play the following game against an evil wizard.
The wizard has 2n2n cards; for each i=1,...,n,i = 1, ..., n, there are two cards labeled i.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 kk 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 kk chosen cards and turns them back face-down. Then, it is your turn again.
We say this game is winnable\textit{winnable} if there exist some positive integer mm and some strategy that is guaranteed to win in at most mm moves, no matter how the wizard responds.
For which values of nn and kk is the game winnable?

A number or a short expression. Spacing and $ signs are ignored.

Solution

Case I:
We first prove that the game is winnable whenever n>kn > k by demonstrating a winning strategy in this case.
On the ii th move, choose the kk cards in positions ii through i+k1.i+k-1. Assuming that you do not win on any earlier move, repeat this for 1i2nk+1.1\le i \le 2n-k+1.
Assume that you did not win on any of the first 2nk+12n-k+1 moves, as described above. Let jj be an integer such that 1j2nk.1\le j\le 2n-k. On the jj th move, the wizard revealed the cards in positions jj through j+k1,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)(j+1) th move, the wizard revealed the cards in positions j+1j+1 through j+k,j+k, which means that you get to see all of the cards that were moved to positions j+1j+1 through j+k.j+k. This means that you can uniquely determine the label on card j,j, since you knew all of the labels from jj through j+k1,j+k-1, and the card in position jj could not have moved anywhere else since your last move.
It follows that, after the sequence of 2nk+12n-k+1 moves described above, you know the labels on the first 2nk2n-k cards. Since n>k,n > k, we have 2nkn+1,2n-k \ge n+1, so there must be a pair of cards with matching labels in this group of 2nk2n-k cards, by the Pigeonhole Principle. On your next move, you can pick a group of kk 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=2nk+2m = 2n-k+2 moves. Thus, the game is winnable for all n>k.n > k.
Case II:
We now prove that the game is not winnable if n=k.n=k. We will say that the game is in a state SS if your knowledge about the card labels is of the following form:
There exists a group of nn cards for which you know that those nn cards have all of the labels 1,2,...,n1, 2, ..., n (i.e. you know that they have all distinct labels) in some order, but you know nothing about which of those nn cards have which labels. (Call this group of cards Group A.A. )
Suppose that the game is in such a state S.S. We will now show that, regardless of your next move, you cannot guarantee victory or an escape from state S.S.
Clearly, the nn cards that are not in Group AA must also have all of the labels 1,2,...,n.1, 2, ..., n. (You might know something about which cards have which labels, or you might not.) Call this other collection of cards Group B.B.
If, on the next move, you pick all of the cards from Group AA or all of the cards from Group B,B, then you clearly will not get a matching pair. The wizard will then arbitrarily permute those cards. Thus, for those nn chosen cards, you know their labels are all distinct, but you know nothing about which cards have which labels. Thus, you are back in state S.S.
Now, suppose you pick xx cards from Group AA and nxn-x cards from Group B,B, where xx is an integer and 1xn1.1\le x\le n-1. Then, the cards chosen from Group BB will form a set of labels PZn,P\subset Z_n, where Zn={1,2,...,n}Z_n = \left\{ {1, 2, ..., n} \right\} and P=nx.|P| = n-x. However, you know nothing about which cards in Group AA have which labels. Thus, there is no way for you to prevent the xx cards from Group AA to form the exact set of labels Q=ZnP.Q = Z_n\setminus P. In such a case, there will be no matching cards, so you will not win. Furthermore, the wizard will then arbitrarily permute these nn cards, so you will know that they have all nn distinct labels, but you will know nothing about which cards have which labels. Therefore, you are again in state S.S.
We have covered all cases, so it follows that, once you enter state S,S, you cannot guarantee escape from state SS or victory.
Now, look at the very first move you make. Obviously, you cannot guarantee victory on the first move, as you know nothing about which cards have which labels. Assuming that you do not win on the first move, the nn cards you chose have all distinct labels. The wizard then permutes the nn cards you chose, so you now know that those nn cards have all distinct labels but know nothing about which cards have which labels. Therefore, if you do not win on your first move, then the game enters state S,S, and we have already proven that you cannot guarantee victory from this point.
We therefore conclude that the game is not winnable if n=k.n=k. We proved earlier that the game is winnable if n>k,n>k, so the game is winnable if and only if n>k2.n>k\ge 2.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.