Happy Hallowe’en! I thought that I’d get into the spirit of the holiday and recount some spooky interactions I’d had recently. These came in the form of some maths brainteasers that I was under some time pressure to solve. I thought I would write about a few of them now that I’ve had time to think about them.
Question: Suppose you have just bought a circular tabletop from a well-known Swedish company. The tabletop comes with three weightless legs of equal length, however the instructions, while charming, are somewhat indecipherable and do not appear to shed any light on how to attach them, other than that they should all be attached perpendicularly on the underside of the tabletop. What is the probability that picking any three points uniformly at random at which to attach the legs will result in a table that will not fall over?
Solution:
Question: Suppose you toss a fair coin 32 times independently. Let \(X\) be the number of times the coin comes up heads and \(Y\) the number of times it comes up tails. What is the value of \(\mathbb{E}[XY]\)?
Solution: Let’s start with a small example. Let \(n\) denote the number of times we flip the same coin, and let \(X\) and \(Y\) instead denote the number of heads and tails respectively that show up after these \(n\) flips. If we denote a flip coming up heads as \(0\) and a flip coming up tails as \(1\), then for \(n=3\) all possible outcomes of our experiment are the following:
\[\begin{gather*} 000 \\ 001 \\ 010 \\ 011 \\ 100 \\ 101 \\ 110 \\ 111 \\ \end{gather*}\]Since the coin is fair then each outcome has the same probability of \(1/8 = 1/2^n\) of occurring. Now the probability of us seeing \(k\) heads is simply the number of outcomes that contain exactly \(x\) zeroes. In the above example, only one outcome (the top one) contains three zeroes so \(\Pr[X=3] = 1/8\), while there are four outcomes that contain exactly \(2\) zeroes thus \(\Pr[X=2] = 4/8 = 1/2\).
Let’s generalise the above argument to find an expression for \(\Pr[X=x]\) for arbitrary \(n\). Suppose we have a string of \(n\) bits (as in the example above). To compute the probability \(\Pr[X=x]\) all we have to do is count the number of outcomes in which there are exactly \(k\) zeroes. This is simple: the number of ways to assign \(x\) zeroes to a string with \(n\) places is simply \(n \choose x\). Thus to compute the expected value we simply sum the product \(x \cdot \Pr[X=x]\) over all possible values of \(k\) in from \(0\) to \(n\). In symbols, the expected value is therefore:
\[\begin{align*} \mathbb{E}[X] & = \sum_{x=0}^{n} x \cdot \Pr[X=x] \\ & = \frac{1}{2^n} \sum_{x=0}^n { n \choose x } x \end{align*}\]Now note that \(Y = n - X\), thus we get \(\mathbb{E}[XY] = \mathbb{E}[X(n-X)] = \mathbb{E}[nX - X^2]\). Now by linearity of expectation the previous expression is equal to \(n \cdot \mathbb{E}[X] - \mathbb{E}[X^2]\), and from here we may simply expand the expression to get:
\[\begin{align*} \mathbb{E}[XY] & = n \cdot \mathbb{E}[X] - \mathbb{E}[X^2] \\ & = \frac{n}{2^n} \sum_x {n \choose x} x - \frac{1}{2^n} \sum_x {n \choose x} x^2 \\ & = \frac{1}{2^n} \sum_x {n \choose x} x (n - x) \end{align*}\]Now we can plug in \(n = 32\) and get \(\mathbb{E}[XY] = 248\).
Question: What is the value of \(2^{40}\) (no computer allowed!).
Solution: By laws of indices we know \(2^{40} = (2^{10})^4 = 1024^4\). How can we estimate \(1024^4\). Being a human with ten fingers between two hands I have been brought up in the base ten number system, so I know that \(1000^4 = 10^{12}\), or \(1\) followed by \(12\) zeroes, so we can say that \(2^{40} \approx 10^{12}\). Now \(1000\) is less than \(1024\) so this is an underestimate, but the question is how much?
The binomial theorem says that for two numbers \(x\) and \(y\) and some number \(n\) we have:
\[(x+y)^n = \sum_{k=0}^n {n \choose k} x^k y^{n-k}\]Now we can take \(x = 1000\) and \(y = 24\) and we can express \(2^{40}\) by the following binomial expansion:
\[\begin{align*} (1000+24)^4 & = { 4 \choose 0 } \cdot 1000^0 \cdot 24^4 + { 4 \choose 1 } \cdot 1000^1 \cdot 24^3 + { 4 \choose 2 } \cdot 1000^2 \cdot 24^2 + { 4 \choose 3 } \cdot 1000^3 \cdot 24^1 + { 4 \choose 4 } \cdot 1000^4 \cdot 24^0 \\ & = 24^4 + 4 \cdot 24^3 \cdot 1000 + 6 \cdot 24^2 \cdot 1000^2 + 4 \cdot 24 \cdot 1000^3 + 1000^4 \end{align*}\]With this expansion it is clear to see that our \(2^{40}\) is indeed \(1000^4\) (the final term in the above sum) plus some change. Now we want to find out how much our estimate that \(2^{40} \approx 1000^4\) underestimates the true value of \(2^{40}\).
Question: What is the expected number of times you must flip a fair coin before you see three heads in a row?
Solution: Let \(x_n\) denote the expected number of times you flip the coin before you see \(n\) heads in a row. Now, in order to see \(n\) heads in a row you must first see \(n-1\) heads, which takes \(x_{n-1}\) flips of the coin. However, if you fail on the final flip (where you would see the \(n\)th head) you have to repeat the entire process of getting \(n-1\) heads again, which takes (unintuitively) \(x_{n-1} + x_n\) flips. Since the coin is fair, meaning each outcome occurs with probability \(1/2\), hence we can state \(x_n\) as the following recurrence relation:
\[x_n = \frac{1}{2}(1 + x_n) + \frac{1}{2}(1 + x_{n-1} + x_n)\]Simplifying the above gives us \(x_n = 2 x_{n-1} + 2\). Now clearly we will have \(x_0 = 0\) since it takes zero flips of the coin to see zero heads in a row. Seeing a single head come up corresponds to \(x_1\) and it should not be difficult to see that this should simply be \(2\). We can then compute \(x_2 = 2(2) + 2 = 6\) and finally \(x_3 = 2(6) + 2= 14\), which gives us our answer.
Now, we may want a more convenient way to compute \(x_n\) without having to compute all the previous terms. The recurrence above should be simple enough for us to guess at a closed form expression. The \(n\)th term is double the previous term, hence our expression will look like \(x_n = a \cdot 2^n + b\), and plugging in the terms we know gives us
\[\begin{align*} x_1 & = 2 = 2 a + b \\ x_2 & = 6 = 4 a + b \end{align*}\]Thus we can solve the above system of equations to get \(a = 2\) and \(b = -2\), so our closed form solution is \(x_n = 2^{n+1} - 2\).