Hilbert’s paradox of the Grand Hotel, or simply Hilbert’s hotel, is a thought experiment which illustrates a counterintuitive property of infinite sets. It is demonstrated that a fully occupied hotel with infinitely many rooms may still accommodate additional guests, even infinitely many of them, and that this process may be repeated infinitely often. The idea was introduced by David Hilbert in a 1924 lecture
If you’re in the UK, don’t just think about the highlighted issues like immigration; take a moment to consider how thoroughly the EU rules our lives (to the extent that no-one in the EU even knows exactly how many laws they’ve made), and take that into account when you vote on June 23rd.
Mathematical YouTuber Matt Parker recently celebrated his 100,000th subscriber with a video in which he successfully flips a coin ten times with alternating heads and tails – a neat trick to pull off, if you didn’t already figure out that he will have recorded himself flipping coins over and over until the correct sequence came up.
Of course Matt owns up to using this method of deception, and then challenges his viewers to guess how many coin flips it took him to to achieve this feat. But if you know Matt, you’ll also suspect there may be even more to this trick than meets the eye. Watch the video and see what you think, and then I’ll explain below how I believe he did this in the minimum amount of time…
OK. First things first. Note the jump cut at 1:18. Clearly the introduction was filmed separately so that it didn’t have to be recorded over and again. But this is where I suspect Matt’s misdirection first shows, in that I believe the intro was shot after the coin flipping, not before. The reason for this is that I think Matt didn’t set out with the objective of achieving just a run of HTHTHTHTHT coin flips, it’s simply that this was the first of four possible patterns that he obtained. In fact, I suspect he had decided that there are four sequences that would all look equally convincing, as follows:
It was then a matter of Matt filming himself, along with some witty banter relating to how the flips were turning out. For example, if the first two flips were both either heads or tails then he would give the talk about trying for a sequence of 10 of either heads or tails. But if one was a head and one a tail, then he’d talk about trying for an alternating run of repeating heads then tails (or tails then heads, depending which was flipped first).
Why this Deviousness?
The reason for wanting to resort to such deviousness would be to cut down substantially on the time taken to film the video. This is because trying to obtain any particular run or sequence of 10 flips (such as HTHTHTHTHT) is going to take an average of 2^10 (or 1024) flips, because on the first flip there’s a 1 in 2 chance (H or T), then for the second there’s a 1 in 4 chance (HH, HT, TH, or TT), and so it continues to double up until you reach 1024. Therefore, on average it will take 1024 flips to obtain the run you desire. And the more often you try for it and average out the flips, the closer to this figure you will get.
However, if you time each of Matt’s flips you’ll see it takes him about 6 seconds for each, and with 1024 flips, that would be about 6144 seconds, or around 1 hour 42 minutes. But if he were to allow two possible sequences (such as HTHTHTHTHT and THTHTHTHTH), he could halve the number of potential flips needed to just 512, taking only 51 minutes or so. And by adding in another two potential sequences (HHHHHHHHHH and TTTTTTTTTT) he can halve this number again to only 256 flips on average, taking a likely 25 minutes or so before hitting one of the sequences.
To further explain how to work out the average number of flips required to obtain a given selection of 10 in a row, if Matt could have come up with 1024 different acceptable sequences, then he could have guaranteed to obtain one of these on his very first set of 10 flips. The reason for this is that the numbers 0 to 1023 (1024 of them in total) can be represented by the binary values 0000000000 through 1111111111., which is the same as a sequence of ten heads or tails, with heads representing 0, and tails being 1 (or vice versa).
The first program simply assumes that there was no trickery on Matt’s behalf, and conducts random coin flips over and again until the sequence HTHTHTHTHT is reached. If at any time the pattern breaks then the loop starts again, but the number of flips taken so far is retained. Here’s what it looks like in action:
Total Wins: 20653
Flips this Win: 1115
This Sequence: HTHTHTHTHT
Average Flips: 1024
The third program is more interesting in that it accepts either of the patterns HTHTHTHTHT or THTHTHTHTH, and if you run it you’ll see the average time taken to find one or the other converges on 512 flips:
Finally, the fifth program accepts any of the patterns HTHTHTHTHT, THTHTHTHTH, HHHHHHHHHH and TTTTTTTTTT, and it quickly converges on an average of 256 flips required to find any one of the four sequences.
Is this the way Matt made the video, or is there an even sneakier method, or did he just do it the hard way? And how many flips do you think it took him? Leave a comment on his video before March 8th 2016, and you could win a prize!