[ Dirichlet's Principle (continued). ] [Partitions into pairs and groups; bijections]

Before a clairvoyant lies a deck of 36 cards face down (4 suits, 9 cards of each suit). He names the suit of the top card, after which the card is revealed to him. Then he names the suit of the next card, and so on. The task of the clairvoyant is to guess the suit as many times as possible. The backs of the cards are asymmetrical, and the clairvoyant can see which of the two positions the top card is in. The clairvoyant's assistant knows the order of the cards in the deck, cannot change it, but can arrange the back of each card in one way or another. Could the clairvoyant have agreed with the assistant, when the latter still did not know the order of the cards, to ensure guessing the suit of at least

a) 19 cards;

b) 23 cards
a) The first two cards can "encode" the suit of the second card, the next two cards can encode the suit of the fourth card, and so on. When only two cards are left in the deck, it is sufficient to encode only their order, which can be done using the back of the 35th card. Thus, the clairvoyant will guess the suits of 19 cards.

b) We will call the 1st, 3rd, 5th, ..., 35th cards odd. Consider the following 17 cards: all odd cards except the first and the second-to-last, and the second card. Among them, there will be five cards of the same suit. We will call this suit the main suit. The position of the first two cards in the deck can encode the main suit. The position of the $(2k-1)$-th and $2k$-th cards (for $2 \leq k \leq 17$) can encode the suit of the $2k$-th card. The position of the back of the second-to-last card can encode the suits of the last two cards (see the solution to part a).

The clairvoyant should name the main suit for each of the 17 selected cards. Then he will guess the suits of at least five of these 17 cards. In addition, the clairvoyant will guess the suits of all even cards except the second and the last, as well as the suits of the last two cards. In total, he will guess the suits of at least 23 cards.

## Answer

a), b) Yes.