6. An extrasensory perception (ESP) practitioner has a deck of 36 cards face down in front of him (four suits, nine 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 ESP practitioner is to guess the suit as many times as possible.

The backs of the cards are not symmetrical, and the ESP practitioner can see which of the two positions the top card is in. The ESP practitioner's assistant knows the order of the cards in the deck, cannot change it, but can position the back of each card in one of two ways.

Could the ESP practitioner have agreed with the assistant, before the assistant knew the order of the cards, to ensure guessing the suit of at least a) 19 cards; b) 23 cards?

If you have come up with a way to guess a different number of cards, more than 19, please also write it down.

10 k l a s s
6. a) Note that guessing 18 cards is not difficult. Indeed, the first two backs can "encode" the suit of the second card (by associating each suit with one of the four possible arrangements of the two backs), the next two backs can encode the suit of the fourth card, and so on.

When only two cards remain in the deck, the clairvoyant knows what they are (since he saw which 34 cards came out), and therefore the assistant only needs to encode the order in which they lie; this is easily done using the back of the 35th card. Indeed, the clairvoyant and the assistant can agree on which suit is "older," after which the assistant can indicate with the position of the 35th card which of the cards is older - the 35th or the 36th. 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. By the pigeonhole principle (see fact 1), among these seventeen cards, there must 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 \leqslant k \leqslant 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 selected seventeen cards. Then he will guess the suits of at least five of the selected seventeen 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.

Comment. We will show how the clairvoyant could guess the suits of 24 cards. For this, it is sufficient to guess the suits of at least 22 out of the first 34 cards (see the end of the solution to part "a"). Divide these 34 cards, except the first, into 11 consecutive triplets. The position of the first card (not included in any triplet) will indicate whether there are more black or red suits in the first triplet. Without loss of generality, assume there are more black suits.

Consider the cards of the first triplet. Call the first two black cards natural. The remaining card is called unnatural (it can be either black or red). By rotating the back of each of the two natural cards, the assistant will show which of the two black suits the clairvoyant should name. Using this information, the clairvoyant will guess the suits of both natural cards. By rotating the back of the unnatural card, the assistant encodes the color that is more frequent in the next triplet. (Note that if the red card in the first triplet is not the last, the clairvoyant will be able to recognize its unnaturalness only after it is revealed.)

Now the same can be done with the second triplet - in this case, the clairvoyant will guess two suits out of three and learn the dominant color of the next triplet, and so on. Thus, he will guess the suits of all cards except, perhaps, the first card and one card in each triplet, i.e., at least 24 cards in total.

A (much more complex) algorithm is known that ensures the guessing of the suits of 26 cards (see [89], [90]).

10 c l a s s