# Riddler Express, August 17 2018

This week’s seems a little more involved than the Expresses usually are (although I’ll admit July 27^{th}‘s really stumped me!):

Take a standard deck of cards, and pull out the numbered cards from one suit (the cards 2 through 10). Shuffle them, and then lay them face down in a row. Flip over the first card. Now guess whether the next card in the row is bigger or smaller. If you’re right, keep going.

If you play this game optimally, what’s the probability that you can get to the end without making any mistakes?

I got nowhere when I tried visualising this as a decision tree. Too wide and deep for me to understand it. Then I did the sensible thing, and broke it down into simpler problems. I also tried staying away from Excel for a while, a new one for me!

What happens if there are fewer than nine cards, and you only have to guess correctly once?

With one card, there’s no guess to make, and with two cards, your best guess must be correct. Three cards is where it starts to get interesting.

With three cards, you might first turn over the highest card, in which case you can guess lower and definitely be correct. There’s a one third chance of that. Symmetrically, you can first turn over the lowest card, guess higher, and certainly be correct, again with a one third chance. The worst case is that you first turn over the middle card, in which case, whether you guess higher or lower, you have only a 50% chance of being right. So with two out of three of the possible first turns giving you a 100% chance of “guessing” correctly, and one out of three giving you a 50% chance, then your chance *before* you turn over the first card is ^{5}/_{6}.

Two things to note straight away:

- if you’re lucky enough to turn over the lowest or highest card from a set, then you will know for sure whether the next card is higher or lower.
- the worst case is turning over the middle card of a set – this means the next card is equally likely to be higher or lower, so your guess has only a 50% chance of being correct.

Before you turn over the first card (from a set of three or more cards), you don’t know how risky the guess will be. But you do know that the chance of your guess being right must be somewhere between 50% and 100%.

Regardless of how large the set of cards is, the closer your first flipped card is to the middle of the group, the less likely your guess is to be correct. The closer your first flipped card is to one of the extremes, the better your chances are of guessing correctly. If you have N cards in your set, your chances of guessing correctly after the first flip depend on the position of your flipped card within the set, like this:

If that’s the general outline, what are the exact values? If there are *N* cards in a set, and you turned over the *q*th card in that set, then the chance of you guessing correctly is:

The denominator is easy to understand: *N*-1 is the total number of cards left after you flip the first card. The max() function is a little more tricky. Truthfully I don’t know if that’s the normal way to write this, but that’s what I would do in Excel, so that’s what I’ve done here. *N-q* is the number of cards greater than the *q*th card, and *q*-1 is the number of cards less than the *q*th card. Which of those is the larger determines whether you would guess that the next card is higher or lower.

For example, if you flip the lowest card in the set (*q*=1) first, then there are zero cards lower than it, and *N*-1 cards higher than it. You will guess that the next card is higher, and you will always be correct. If you flip the seventh lowest card in the set (*q*=7, and *N≥*7), there will be six cards lower than it, and *N-q* cards greater than it. Whether you guess that the next card will be higher or lower depends on which is greater, six, or *N-q*.

With that first equation done — so we know the chance of guessing correctly given the card we flipped first — we can now work out the expected chance of guessing correctly before we flip the first card. We will just take the average value of the first equation, given all the cards we could flip first.

The *sum* of all the probabilities is this (the ∑ sign here means “add together all of the values for this equation, starting from *q*=1, adding one to *q* each time, until *q*=*N)*:

And the *average* of all the probabilities is just the sum of them, divided by how many there are:

Which simplifies to:

So that’s how likely you are to guess correctly, without knowing what the first card you will flip is. (The factor of ^{1}/_{(N(N-1))} makes me think of the sum from 1 to *N* (= ^{N(N-1)}/_{2}), and I have an idea as to why, but I have to finish this post somewhere!)

If you want to calculate the chance of guessing successfully through multiple flips, as in the question, you need to multiply the values from formula 4 together, for decreasing values of *N:*

(The ∏ character is similar to the ∑ character, but instead of adding together, it means multiply together.) Your chance of succeeding from start to finish with nine cards (the original question) is your chance of succeeding with just one flip from a nine-card set, times the chance of succeeding with just one flip from an eight-card set,* et cetera*, down to a two-card set.

After all that algebra, what are the actual numbers? They’re not too complex:

In the triangular section, you can see *max*((*N*–*q*),(*q*-1)) for the values of *N* in row two, and *q* in column C. The sum of those values, for a particular *N*, is in row 24, and *N*(*N*-1) is calculated in row 25. Dividing row 24 by row 25 gives the value of formula 4, and is on row 27 in decimal form, and on row 28 as a fraction. Lastly, multiplying values on line 27 together gives the values on line 30, equal to formula 5.

[I did not expect pairs of consecutive values of *N*, with the odd number smaller, would have the same value in row 28. I don’t understand why that is, and it’s quite unexpected.]

So the answer to the original question is 0·213, or ^{121}/_{567}.

One thing to note is that the values on line 27 are getting progressively closer to 0·75. Intuitively I expect that: looking at the hand-drawn diagram above, the average value on the *y*-axis should be 0·75. No idea how to prove that, though.

And the extra credit part is fairly simple after that:

What if there were more cards — 2 through 20, or 2 through 100? How do your chances of getting to the end change?

The value for 2 through 20 is also visible on the spreadsheet, it’s 0·0117. As each card is added, the chance of getting to the end successfully decreases, by a factor of about 0·75.

Nice to solve you, to solve you, nice!