Triangular Frame Job

Congratulations—you just won your school’s tabletop football championship! You flicked your lucky paper football to victory countless times, and would now like to frame it for posterity. The football is an equilateral triangle with a side length of 1 inch. What is the side length of the smallest square frame that will contain the football?

For this week's Fiddler, let's just skip to the Extra Credit problem where we answer the general question and from which we can infer the answer to the Classic problem, so ...

To add a little excitement to the framing process, your new plan is to spin the triangular football by a random angle, and then frame it with a square that is not rotated. That is, the square consists of two perfectly horizontal sides and two perfectly vertical sides. On average, what can you expect the side length of the smallest resulting square frame to be?

Let's choose how to parameterize everything. Let's assume that one of the corners of our paper football is fixed at the origin, and that for any $\theta \in [0, 2\pi/3],$ that the other two corners are at $$p_1(\theta) = (\cos \theta, \sin \theta)$$ and $$p_2(\theta) = \left(\cos \left(\theta + \frac{\pi}{3}\right), \sin \left(\theta + \frac{\pi}{3} \right) \right).$$

In order to choose the smallest possible square with two sides parallel to the $x$-axis and two sides parallel to the $y$-axis, we need only determine the maximum horizontal and vertical distances between the three corners. Since \begin{align*}\cos \theta - \cos \left( \theta + \frac{\pi}{3} \right) & = \cos \theta - \left( \frac{1}{2} \cos \theta - \frac{\sqrt{3}}{2} \sin \theta \right) \\ & = \frac{1}{2} \cos \theta + \frac{\sqrt{3}}{2} \sin \theta \\ & = \sin \left( \theta + \frac{\pi}{6} \right),\end{align*} we see that the maximum horizontal distance between the corners is \begin{align*}h(\theta) &= \max \left\{ \left|\cos \theta\right|, \left| \cos \left(\theta + \frac{\pi}{3} \right)\right|, \left| \cos \theta - \cos \left( \theta + \frac{\pi}{3} \right) \right| \right\}\\ & = \begin{cases} \cos \theta, &\text{for $0 \leq \theta \leq \pi/6;$}\\ \sin \left( \theta + \frac{\pi}{6} \right), &\text{for $\pi/6 \leq \theta \leq \pi/2$;}\\ -\cos \left( \theta + \frac{\pi}{3} \right), &\text{for $\pi/2 \leq \theta \leq 2\pi/3.$}\end{cases}\end{align*} Meanwhile, since \begin{align*}sin(\theta) - \sin\left(\theta + \frac{\pi}{3} \right) & = \sin \theta - \left( \frac{1}{2} \sin \theta + \frac{\sqrt{3}}{2} \cos \theta \right) \\ &= -\frac{\sqrt{3}}{2} \cos \theta + \frac{1}{2} \sin \theta \\ &= \sin \left( \theta - \frac{\pi}{3} \right)\end{align*} and because $$\left| \sin \left( \theta - \frac{\pi}{3} \right) \right| \leq \max \left\{ \sin \left( \theta + \frac{\pi}{3} \right), \sin \theta \right\},$$ for all $\theta \in [0, 2\pi/3],$ the maximum vertical distance between the corners is \begin{align*} v(\theta) &= \max \left\{ \left|\sin \theta\right|, \left| \sin \left( \theta + \frac{\pi}{3} \right)\right|, \left| \sin \theta - \sin \left( \theta + \frac{\pi}{3} \right) \right| \right\} \\ &= \begin{cases} \sin \left( \theta + \frac{\pi}{3} \right), &\text{ for $0 \leq \theta \leq \pi/3;$} \\ \sin \theta, &\text{ for $\pi/3 \leq \theta \leq 2\pi/3.$}\end{cases}\end{align*} Since the side length should be the maximum of the vertical and horizontal distances we have $$s(\theta) = \max \{ h(\theta), v(\theta) \} = \begin{cases} \cos \theta, &\text{for $0 \leq \theta \leq \pi/12;$} \\ \sin \left(\theta + \frac{\pi}{3} \right), &\text{for $\pi/12 \leq \theta \leq \pi/4;$}\\ \sin \left( \theta + \frac{\pi}{6} \right), &\text{for $\pi/4 \leq \theta \leq 5\pi/12;$} \\ \sin \theta, &\text{for $5\pi/12 \leq \theta \leq 7\pi/12;$} \\ -\cos \left( \theta + \frac{\pi}{3} \right), &\text{for $7\pi/12 \leq \theta \leq 2\pi/3.$}\end{cases}$$

Therefore, we see that for the Classic problem we want the minimal sidelength under any orientation, which is $$s^* = \min_{\theta \in [0, 2\pi/3]} s(\theta) = \cos \frac{\pi}{12} = \frac{\sqrt{2 + \sqrt{3}}}{2} \approx 0.965925826289\dots$$ Furthermore, we notice that, by symmetry, the average sidelength over any possible orientation is \begin{align*}\bar{s} &= \frac{3}{2\pi} \int_0^{2\pi/3} s(\theta) \,d\theta\\ &= \frac{12}{\pi} \int_0^{\pi/12} \cos \theta \,d\theta\\ &= \frac{12}{\pi} \sin \frac{\pi}{12} = \frac{6}{\pi} \sqrt{ 2 - \sqrt{3} } \approx 0.988615929465\dots.\end{align*}

Cup Swap

My friend has three cups, labeled “A,” “B,” and “C” in a row. She picks two random cups and swaps their position. Then she does this again and again, picking a random pair each time, until all three cups are back in their original order. For example, here is one such sequence of swaps:

• A, B, C (original)
• C, B, A (first and third were swapped)
• B, C, A (first and second were swapped)
• B, A, C (second and third were swapped)
• A, B, C (first and second were swapped)

In this example, the cups returned to their original order after four swaps. On average, how many swaps would you expect until the cups return to their original order?

There are six possible states for the cups: ABC, ACB, BAC, BCA, CAB, and CBA. If we initially set up a Markov chain, with the assumption that each choice of two cups to switch are equally likely, we get the transition matrix $$M = \begin{pmatrix} 0 & 1/3 & 1/3 & 0 & 0 & 1/3 \\ 1/3 & 0 & 0 & 1/3 & 1/3 & 0 \\ 1/3 & 0 & 0 & 1/3 & 1/3 & 0 \\ 0 & 1/3 & 1/3 & 0 & 0 & 1/3 \\ 0 & 1/3 & 1/3 & 0 & 0 & 1/3 \\ 1/3 & 0 & 0 & 1/3 & 1/3 & 0 \end{pmatrix}.$$ Playing around on with the transition matrix, we see that if we start at ABC, then after an even number of swaps the state can be any one of ABC, BCA or CAB, while after an odd number of swaps the state can be any one of ACB, BAC or CBA. In order to solve this particular problem, let's separate ABC from the other states BCA and CAB. Let's say that we have new states $ABC,$ $X = \{ BCA, CAB \}$ and $Y = \{ACB, BAC, CBA\}.$ In this reduced Markov chain state we see that if you are at $ABC$ then almost surely you end up at $Y$ after a swap; if you are at $X$ then almost surely you end up at $Y$ after a swap; and if you are at $Y$ then with probability 1/3 you end up at $ABC$ and with probability 2/3 you end up at $X$.

Therefore, we see that if $2n$ is the first number of swaps that return you to ABC, then since there needs to be at least one swap from $Y$ to $ABC$, then we must have $(n-1)$ loops from $Y$ to $X.$ Therefore, $$p_n = \mathbb{P} \{ 2n \text{ swaps to first return to ABC } \} = \frac{1}{3} \left( \frac{2}{3} \right)^{n-1},$$ so the expected number of swaps needed to return to ABC is $$E = \sum_{n=1}^\infty 2n p_n = \frac{2}{3} \sum_{n=1}^\infty n \left(\frac{2}{3} \right)^{n-1} = \frac{2}{3} \left( \frac{1}{1-2/3} \right)^2 = 6.$$

Asymmetric Bingo

In a game of “asymmetric bingo,” you and your opponent have two differently sized boards: You play on a 5×5 board, while your opponent has an 8×8 board. The 8×8 board has 64 squares, collectively marked with the numbers 1 through 64 in some random arrangement. Meanwhile, the 5×5 board is populated with 25 numbers chosen and arranged randomly (without replacement) from 1 through 64. There are no “free” squares like there are in traditional bingo.

Here’s how the game works: One at a time, a number from 1 to 64 is drawn randomly, without replacement. If that number appears on your 5×5 board, you place a marker on the corresponding square. Otherwise, your opponent (who is guaranteed to have that number somewhere on their board) places the marker on their corresponding square.

The game ends when one of you has “bingo,” meaning five markers in a row going across, down, or diagonally somewhere on the board. Who is more likely to win this game: you (with the 5×5 board) or your opponent (with the 8×8 board)?

At first, I didn't see that "Otherwise" where I added the emphasis, and said to myself, "Self, this is clearly a losing proposition, the 8x8 board has so many possible winning bingo configurations, $96,$ to be precise, while I and my 5x5 board only have the standard 12." I even offered this version of puzzle in the car while driving to my in-laws house on Sunday morning, and the entire cadre of kids ages 7 through 13 answered that they'd prefer the 8x8 board (though some of their logical reasoning had some gaps). However, then the old adage "Reading comprehension is the silent killer" came back with a vengeance, since then the ``otherwise'' and the blurb at the top saying "you get priority" turned thought process upside-down.

In this case, despite the random arrangement, let's assume that the numbers on the 8x8 board are in lexicographical order, so that the squares along the top row are numbered $1, 2, \dots, 8$ from left to right, then the second row is $9, 10, \dots, 16,$ and so on. Since I am the only player that can mark down any of the numbers on my board, we can effectively remove any of the 25 random numbers on my board from the 8x8 board. For instance, if my board is the numbers say 1 through 25, then we see that my opponent would have a board with 26 through 64 remaining, which would have a total of 22 available bingos in it. On the other hand if my board has the following values $$B = \{1,4,7,10,13,14,16,19,22,24,25,28,29,34,39,40,44,45,48,50,53,54,59,62,64\}, $$ then there is no possible way for your son to win because there are 0 available bingos left on the big board.

Now unlucky for us there are $\binom{64}{25} = 4.01 \times 10^{17}$ different combinations of how to remove 25 squares from a total of 64, so simple enumeration is not going to cut it in this case. However, we can hope that numpy.random.permutation does a relatively good job and hope to simulate our way out of this mess. Using $N=1,000$ samples, first calculate our 5x5 board and then calculate the winning bingos in your 5x5 board and all those remaining bingos that do not contain any of the in the 8x8 board. get the following that the average number of remaining bingos available to your opponent on the 8x8 board is only about 7.3 compared to your guaranteed 12 possible bingos. Given that again we are going to rely on the intuitive sense that the player with more available winning combinations is more likely to win, then you are more likely to win on the 5x5 board than your opponent on the 8x8 board. Going further, though with much less confidence, let's hope that by running a bunch of additional numpy.ranom.permutations and checking whether the 5x5 or 8x8 board wins, we get a win probability that is roughly about $65.56\%$ using these $N=1,000$ samples.

import numpy as np

bingos = [

    [ 1, 2, 3, 4, 5], [ 2, 3, 4, 5, 6], [ 3, 4, 5, 6, 7], [ 4, 5, 6, 7, 8],

    [ 9,10,11,12,13], [10,11,12,13,14], [11,12,13,14,15], [12,13,14,15,16],

    [17,18,19,20,21], [18,19,20,21,22], [19,20,21,22,23], [20,21,22,23,24],

    [25,26,27,28,29], [26,27,28,29,30], [27,28,29,30,31], [28,29,30,31,32],

    [33,34,35,36,37], [34,35,36,37,38], [35,36,37,38,39], [36,37,38,39,40],

    [41,42,43,44,45], [42,43,44,45,46], [43,44,45,46,47], [44,45,46,47,48],

    [49,50,51,52,53], [50,51,52,53,54], [51,52,53,54,55], [52,53,54,55,56],

    [57,58,59,60,61], [58,59,60,61,62], [59,60,61,62,63], [60,61,62,63,64],

    [ 1, 9,17,25,33], [ 2,10,18,26,34], [ 3,11,19,27,35], [ 4,12,20,28,36],

    [ 5,13,21,29,37], [ 6,14,22,30,38], [ 7,15,23,31,39], [ 8,16,24,32,40],

    [ 9,17,25,33,41], [10,18,26,34,42], [11,19,27,35,43], [12,20,28,36,44],

    [13,21,29,37,45], [14,22,30,38,46], [15,23,31,39,47], [16,24,32,40,48],

    [17,25,33,41,49], [18,26,34,42,50], [19,27,35,43,51], [20,28,36,44,52],

    [21,29,37,45,53], [22,30,38,46,54], [23,31,39,47,55], [24,32,40,48,56],

    [25,33,41,49,57], [26,34,42,50,58], [27,35,43,51,59], [28,36,44,52,60],

    [29,37,45,53,61], [30,38,46,54,62], [31,39,47,55,63], [32,40,48,56,64],

    [ 1,10,19,28,37], [ 2,11,20,29,38], [ 3,12,21,30,39], [ 4,13,22,31,40],

    [ 9,18,27,36,45], [10,19,28,37,46], [11,20,29,38,47], [12,21,30,39,48],

    [17,26,35,44,53], [18,27,36,45,54], [19,28,37,46,55], [20,29,38,47,56],

    [25,34,43,52,61], [26,35,44,53,62], [27,36,45,54,63], [28,37,46,55,64],

    [ 5,12,19,26,33], [ 6,13,20,27,34], [ 7,14,21,28,35], [ 8,15,22,29,36],

    [13,20,27,34,41], [14,21,28,35,42], [15,22,29,36,43], [16,23,30,37,44],

    [21,28,35,42,49], [22,29,36,43,50], [23,30,37,44,51], [24,31,38,45,52],

    [29,36,43,50,57], [30,37,44,51,58], [31,38,45,52,59], [32,39,46,53,60],

]

​

def asymmetric_bingo(wins, losses, N=1000):

    hits = np.zeros(N)

    for r in range(N):

        perm = np.random.permutation(np.arange(64))

        end = False

        k = 5

        while (not end):

            test = set(perm[:k])

            for w in wins:

                if w <= test:

                    hits[r] = 1

                    end = True

            for l in losses:

                if l <= test:

                    end = True

            k += 1

    return hits.sum() / N

smpl = 1000

remaining = np.zeros(smpl)

winprob = np.zeros(smpl)

for i in range(smpl):

    board = (np.random.permutation(np.arange(64))[:25]+1)

    b_ = board.reshape(5,5)

    wins = [ set(b_[i,:]) for i in range(5)] + [ set(b_[:,i]) for i in range(5) ] + [{b_[i,i] for i in range(5)}, {b_[i,4-i] for i in range(5)}]

    losses = [set(b) for b in bingos if len(set(board).intersection(b)) == 0]

    remaining[i] = len(losses)

    winprob[i] = asymmetric_bingo(wins, losses)

remaining.mean(), winprob.mean()