There are $n$ players, $n\ge 2$, which are playing a card game with $np$ cards in $p$ rounds. The cards are coloured in $n$ colours and each colour is labelled with the numbers $1,2,\ldots ,p$. The game submits to the following rules: each player receives $p$ cards. the player who begins the first round throws a card and each player has to discard a card of the same colour, if he has one; otherwise they can give an arbitrary card. the winner of the round is the player who has put the greatest card of the same colour as the first one. the winner of the round starts the next round with a card that he selects and the play continues with the same rules. the played cards are out of the game. Show that if all cards labelled with number $1$ are winners, then $p\ge 2n$. Barbu Berceanu
Problem
Source: Romanian TST 2002
Tags: combinatorics proposed, combinatorics
05.02.2011 20:26
A small typo: the requirement is to show that if all cards $1$ are winners, then $p\geq 2n$ (a model with $p=2n$ can easily be exhibited). I have to share with you the funny story of the origin of this problem. Some long time ago I was residing in Canada, and found a little problem in the Bridge World magazine (there $n=4$, they use a normal deck of cards ($p=13$, but the problem had to do with the last $8$), the terminology is simpler, since one can use the term "trick" for a round of cards, the lower card is the deuce, not the Ace, etc.), and I found the idea of the solution so fresh that, during one of my visits, I communicated the problem to my friend Barbu. Lo and behold, after a minor transformation, it was used in a Romanian selection test!
02.11.2019 05:51
Funny problem! Lemma 1. Each of the players has exactly one $1$ card. Proof. Consider the last time somebody wins a round with a $1.$ Note that after a $1$ is played, say a red $1$ WLOG, all other people cannot have red cards, as otherwise the red $1$ is not winning. So at the instant that the last winning $1$ is played, no two players can have cards of the same color. This means that each player must have only one color at this instant. For each player, call one of his/her last colors his/her residual color . Since no two players can have the same residual color, and each player clearly has at least one residual color, every player has exactly one residual color. We claim that every player has a $1$ of his/her residual color at first. It's clear that no player can have a $1$ which is the same color as the residual color of somebody else. This means that everyone either has a $1$ of their residual color or no $1$'s at all. However, since there's $n$ $1$'s and everybody has at most one of them, everybody has exactly one $1$ initially, which is the same color as their residual color. $\blacksquare$ With this lemma, we are surprisingly almost finished. Call a round tasty if the winning card is a $1$ (and therefore must have been the first card played in the round). The following lemma easily follows. Lemma 2. There cannot be two consecutive tasty rounds. Proof. The winner of the first tasty round would have to place down a $1$ on two consecutive rounds. However, this player cannot have two $1$'s by Lemma $1.$ $\blacksquare$ This yields that $p \ge 2n-1$ since there are $p$ rounds. Now, let's show that this cannot be sharp. If it were sharp, then the game must begin with a tasty round. Suppose the first player placed down a red $1$ to begin with. Then, it's clear that nobody else has a red card, as then somebody else would have won the round. Hence, the first player has all the red cards and no other cards. But it is then clear that the first player wins all the rounds, and so the only winning cards are the red cards. This means that all the other $1$'s are not winning, contradiction. Hence, equality cannot be obtained and we have $p \ge 2n.$ $\square$