Up Is Down

Remembering to post solutions to stuff takes alot of work. Anyway, I guess its time to do my semi-incomplete solution to the card puzzle from last time. I managed to think more about the puzzle to come up with a slightly better solution than I had before, apparently there is a 26 card solution, but I only know of a 25 card one.

First of all, note that in any solution we can easily get the last card trivially just by counting. We can even get the last two cards easily, if they are the same then we know that, and if they are different we can use the second last card as 'up' if they appear in alphabetical order and 'down' if they appear in reverse alphabetical order. This can be appended to any strategy to get the last two cards, so we don't need to worry about them.

For the remaining cards, we can group them into threes in a similar method as the Sam and Ray problem. We spend our first card to specify the most common colour of the next three (up for black, down for red, say) and then on each of those three cards we use the back of the card to specify exactly which suit it is (up for clubs or hearts, down for spades or diamonds). On the one that is off colour (the one black on the group of red), there is no reason for the assistant to specify the suit (the psychic will get it wrong anyway), so he uses that one to specify the most common colour of the next group of three. If none of the three are off colour, we will simply use the third card instead (so the psychic knows if he gets the first two of three right, then the third one is going to be spent on that).

Using this strategy we get the first card wrong, followed by two of three right for the next 11 sets of three (that is 22 right of 33 cards) and then we get the last two right using the earlier strategy. This gives us 24 correct, and this was as much as I was able to get without reading comments from Tanya's blog.

The next thing to do is to make use of a 'surprise' in our strategy, we have the assistant purposely get something wrong and use that to communicate further (actually I have since learned that this can be used in the Sam and Ray problem to get a much simpler solution). So, this time we get our first card wrong, and then use 8 groups of 3 cards (we should be able to get 16 right, but the assistant will mess exactly one of those up, so we will only get 15 right). Thats 25 cards so far, and we have gotten 15 of them right, we will also get the last two right, so we have 9 cards left and we had better be able to get at least 8 of them right if we want this to actually be an improvement. How much can we specify with our 'surprise' strategy? We get 1 of the 16 cards wrong, so that is 4 bits in just choosing which card, and we also have 1 bit from the last card we got wrong (that one that would be specifying the next group of three). So with 5 bits and 9 cards left, what can we do?

It is natural to try to divide the 9 cards into 3 groups of 3, but I wasn't able to do anything with that, in particular I couldn't find a way to get 8 of them right. What I found did work was to split the 9 cards into 5 and 4, use our 5 bits to specify the colours of the next 5 cards, and use the backs of those cards to specify the exact cards. We can get all 5 of those right at the cost of our 5 bits, but then we use another surprise strategy. On one of those 5 cards, we arrange to get one of them wrong, allowing us to specify a number between 1 and 5, but also we can get it wrong in one of three ways (if we order the suits as clubs, diamonds, hearts, then spades, then when we get the suit wrong we can be off by 1, 2, or 3 full steps). Thus we can specify as many as 3*5=15 unique things. We also had the option to not get one wrong at all, that being a 16th choice. Using all of this, we can spend 5 bits on 5 cards to get 4 (or maybe 5) of them right and come out the other end with 4 bits. Those 4 bits can be spent to give the colours of the 4 remaining cards, and then we use the backs of those cards to get them right. Finally we have the last two cards by the earlier method.

This is the best solution that I know of, getting 25 of the 36 cards. On Tanya Khovanova's blog she says there is a 26 card solution, but I haven't found it yet.