Enter the maze

Are you sure the magic always works?

This magic trick works because putting their chosen pile (column) in the middle of the other two piles and re-dealing the cards in effect limits where their card can go.

Magician with computer

Deal Number 1

Let's work through it. After the first deal of the cards into three piles, say your friend chooses the Queen of Hearts. The seven-card pile holding that Queen is put in the middle of the other two.

Deal Number 2

You deal the cards into three new piles. Where do the 7 cards from the middle pile go? The Queen has to be in one of those 7 places. The 7 places are: the fourth or fifth card of the first pile; the third, fourth or fifth card of the middle pile, or the third or fourth card of the last pile. You ask them to say which pile, and again put that pile between the other two and deal again.

We prove it works whatever the starting combination

Deal Number 3

This time, the Queen has to be the fourth card - the middle card - of the first, middle or last pile. Why? Because wherever it was it's pile is first moved to the middle. That means it can then only be in the third, fourth or fifth card of the middle pile. There are only 3 possible places and they each get moved to the middle of their pile as they are dealt out again. In fact more than 40% of the time, it'll be in the middle pile (can you see why?), so that's a good pile for you to guess if you want. Once your friend tells you which of the three piles has their card, you know exactly where their card is.

Deal Number 4

The fourth deal simply moves the chosen card to the middle card of the middle pile, which really is just for effect.

A Proof

What we have just done is give a convincing (we hope) argument that the trick (algorithm) always works. That is all that mathematical proofs are: convincing arguments where there is no room for doubt if you follow the detail. Here we were just proving that a trick works, but as we saw the instructions of the trick are an algorithm - just like a computer program. It is very important that programs always work too. The normal way to ensure that is to "test": that is try it out lots of times. Ideally you would check all the possibilities. For our card trick that means doing the trick for every possible starting order of the 21 cards. Try it ... how many orders did you do before you got bored? It's a lot of combinations...

There are far too many combinations to test all of them.

Testing every combination for a program is also impractical, so instead as many as possible are tested. If it works each time then you assume it works in the cases you didn't try too (and hope!).

An alternative is to do the sort of proof we did. If the proof has no flaws then it proves the trick (or program) works whatever the combination..and you don't need to test any of them.

Using proof you get an answer without testing any!

Of course you can use a mixture of logical reasoning and testing: the proof is used to reduce the number of tests. For example in the above, we can reason that the only thing that matters is the initial position of the chosen card. What the other cards are is immaterial. That means we only need to test 21 combinations: one for each start position. That is better than testing the vast number of combinations needed, though the full proof is still quicker.

So if you want to be sure your trick (or program) works why not try a proof.