26 cards

Looks strongly like this will actually make a not-too-horrible math fair project. Hmm.

The original problem comes all the way from 2004 Tournament of Towns. So, as simply as possible, there’s this magician who wants to wow his crowd by guessing the suits of a randomly shuffled deck of 36 cards, with 9 cards each from 4 suits. He guesses the suit of the top card and then it’s revealed and they do this 36 times somehow without the crowd getting bored or walking off.

The backs of the cards are not symmetric, however, and the magician has a confederate who can inexplicably look at the whole deck of cards and rotate cards so that some of the backs are right-side-up and the others are wrong-side-down (this is not heads-I-win-tails-you-lose syndrome, also inexplicably) but isn’t allowed to rearrange the cards and can do all this without the audience wondering why the preparation is taking so long. But this is math so the audience is very patient. You get the idea. And so the confederate can pass one binary signal to the magician just before he guesses each card. Of course they’re allowed to secretly plan how to set or interpret the signals a long time ago, and since this is math, the plan can be basically as complicated as one can imagine.

No biggie, right? There are only about 10^38700000000000000000 ways to set the signals and 10^{floating point overflow} ways to guess.

Now, asks the 2004 question, can the magician come up with a strategy that guarantees (a) at least 19 guesses right? (b) at least 20 guesses right?

Well, that wasn’t exactly simple. But anyway.

As you possibly guessed from the title the answer is yes and yes and in fact we can go all the way to 26 cards. Except all this is history because people have also done this for math fairs.

Well, it’s better than working on the Secretary Problem. Which came out in 1960 and probably easily has a thousand papers on variants. Blech. True story.

Oh wait, my progress. Well, basically I’ve been able to obtain some nontrivial bounds on the maximum number of guaranteed guesses with a recurrence.

It’s more awesome than it sounds.

I hope.