Problem A. 827. (May 2022)

A. 827. Let \(\displaystyle n>1\) be a given integer. In a deck of cards the cards are of \(\displaystyle n\) different suites and \(\displaystyle n\) different values, and for each pair of a suite and a value there is exactly one such card. We shuffle the deck and distribute the cards among \(\displaystyle n\) players giving each player \(\displaystyle n\) cards. The players' goal is to choose a way to sit down around a round table so that they will be able to do the following: the first player puts down an arbitrary card, and then each consecutive player puts down a card that has a different suite and different value compared to the previous card that was put down on the table. For which \(\displaystyle n\) is it possible that the cards were distributed in such a way that the players cannot achieve their goal? (The players work together, and they can see each other's cards.)

Proposed by Anett Kocsis, Budapest

(7 pont)

Deadline expired on June 10, 2022.

Solution. For every \(\displaystyle n\) it is possible that the cards has been distributed in a way that the players cannot achieve their goal.

For a card in the \(\displaystyle i^{th}\) suite and of value \(\displaystyle j\) let us assign pair \(\displaystyle (i,j)\). Now we will show a distribution for which the players cannot sit down in the required way. For \(\displaystyle 1\leq k \leq k-1\) let the \(\displaystyle k^{th}\) player get cards \(\displaystyle (k,l)\) where \(\displaystyle 1\leq l\leq n\) and \(\displaystyle l\neq k\), and also card \(\displaystyle (n,k)\). The \(\displaystyle n^{th}\) player gets the remaining cards, i.e. cards \(\displaystyle (l,l)\) for \(\displaystyle 1\leq l\leq n\). It is easy to check that every card was given to a player and each player got exactly \(\displaystyle n\) cards.

Let us assume that the players can sit down in an appropriate orders and can get rid of all their cards. Assuming that the \(\displaystyle n^{th}\) player is not the first one let \(\displaystyle k\) denote the number of the player who sits right before the \(\displaystyle n^{th}\) player. If the \(\displaystyle n^{th}\) player is the first one at the table, let \(\displaystyle k\) denote the player right after him. Note that \(\displaystyle k\) was chosen in a way that the \(\displaystyle n^{th}\) and the \(\displaystyle k^{th}\) player will put down cards consecutively \(\displaystyle n\) times. Thus their cards can be paired up in a way that in each pair the two cards have different suites and different values. But this is clearly impossible because card \(\displaystyle (k,k)\) of the \(\displaystyle n^{th}\) player cannot be paired with any of the cards of the \(\displaystyle k^{th}\) player.

Thus we have proved our initial statement.

Statistics:

3 students sent a solution.
7 points:	Ben Gillott, Kökényesi Márk Péter.
0 point:	1 student.

Problems in Mathematics of KöMaL, May 2022