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()

Uniquely Non-Genius Queen Bees

Let’s put the rank of “Genius” aside. Here are some other ranks you can attain in Spelling Bee:

• Amazing (if you get 50 percent of the maximum, rounded to the nearest whole number)
• Great (40 percent)
• Nice (25 percent)
• Solid (15 percent)
• Good (8 percent)
• Moving Up (5 percent)
• Good Start (2 percent)

Suppose a given round of Spelling Bee has some very large, randomly chosen point total. What is the probability that this total can be precisely determined from these cutoffs (i.e., from “Good Start” through “Amazing,” inclusive)?

The first thing that we see is that there are many, many, many levels that start with $G$, so let's forego the step of naming each function of $Q$ and instead have a mapping $F: \mathbb{N} \to \mathbb{N}^7$ with $$Q \mapsto F(Q) = \begin{pmatrix} [0.5Q], [0.4Q], [0.25Q], [0.15Q], [0.08Q], [0.05Q], [0.02Q] \end{pmatrix} \in \mathbb{N}^7.$$ Firstly, we see that we have the recursion formula $$F(100d+k) = (50d, 40d, 25d, 15d, 8d, 5d, 2d) + F(k),$$ for all $d, k \in \mathbb{N},$ so we need only really calculate the ratio for any sufficiently chosen $100$ values of $Q$ in order to determine how many of those are

Let's start with $Q=101$ and start enumerating:

q	F(q)	q	F(q)
101	(50,40,25,15,8,5,2)	151	(75,60,38,23,12,8,3)
102	(51,41,25,15,8,5,2)	152	(76,61,38,23,12,8,3)
103	(51,41,26,15,8,5,2)	153	(76,61,38,23,12,8,3)
104	(52,42,26,16,8,5,2)	154	(77,62,38,23,12,8,3)
105	(52,42,26,16,8,5,2)	155	(77,62,39,23,12,8,3)
106	(53,42,26,16,8,5,2)	156	(78,62,39,23,12,8,3)
107	(53,43,27,16,9,5,2)	157	(78,63,39,24,13,8,3)
108	(54,43,27,16,9,5,2)	158	(79,63,39,24,13,8,3)
109	(54,44,27,16,9,5,2)	159	(79,64,40,24,13,8,3)
110	(55,44,27,16,9,5,2)	160	(80,64,40,24,13,8,3)
111	(55,44,28,17,9,6,2)	161	(80,64,40,24,13,8,3)
112	(56,45,28,17,9,6,2)	162	(81,65,40,24,13,8,3)
113	(56,45,28,17,9,6,2)	163	(81,65,41,24,13,8,3)
114	(57,46,28,17,9,6,2)	164	(82,66,41,25,13,8,3)
115	(57,46,29,17,9,6,2)	165	(82,66,41,25,13,8,3)
116	(58,46,29,17,9,6,2)	166	(83,66,41,25,13,8,3)
117	(58,47,29,18,9,6,2)	167	(83,67,42,25,13,8,3)
118	(59,47,29,18,9,6,2)	168	(84,67,42,25,13,8,3)
119	(59,48,30,18,10,6,2)	169	(84,68,42,25,14,8,3)
120	(60,48,30,18,10,6,2)	170	(85,68,42,25,14,8,3)
121	(60,48,30,18,10,6,2)	171	(85,68,43,26,14,9,3)
122	(61,49,30,18,10,6,2)	172	(86,69,43,26,14,9,3)
123	(61,49,31,18,10,6,2)	173	(86,69,43,26,14,9,3)
124	(62,50,31,19,10,6,2)	174	(87,70,43,26,14,9,3)
125	(62,50,31,19,10,6,2)	175	(87,70,44,26,14,9,3)
126	(63,50,31,19,10,6,3)	176	(88,70,44,26,14,9,4)
127	(63,51,32,19,10,6,3)	177	(88,71,44,27,14,9,4)
128	(64,51,32,19,10,6,3)	178	(89,71,44,27,14,9,4)
129	(64,52,32,19,10,6,3)	179	(89,72,45,27,14,9,4)
130	(65,52,32,19,10,6,3)	180	(90,72,45,27,14,9,4)
131	(65,52,33,20,10,7,3)	181	(90,72,45,27,14,9,4)
132	(66,53,33,20,11,7,3)	182	(91,73,45,27,15,9,4)
133	(66,53,33,20,11,7,3)	183	(91,73,46,27,15,9,4)
134	(67,54,33,20,11,7,3)	184	(92,74,46,28,15,9,4)
135	(67,54,34,20,11,7,3)	185	(92,74,46,28,15,9,4)
136	(68,54,34,20,11,7,3)	186	(93,74,46,28,15,9,4)
137	(68,55,34,21,11,7,3)	187	(93,75,47,28,15,9,4)
138	(69,55,34,21,11,7,3)	188	(94,75,47,28,15,9,4)
139	(69,56,35,21,11,7,3)	189	(94,76,47,28,15,9,4)
140	(70,56,35,21,11,7,3)	190	(95,76,47,28,15,9,4)
141	(70,56,35,21,11,7,3)	191	(95,76,48,29,15,10,4)
142	(71,57,35,21,11,7,3)	192	(96,77,48,29,15,10,4)
143	(71,57,36,21,11,7,3)	193	(96,77,48,29,15,10,4)
144	(72,58,36,22,12,7,3)	194	(97,78,48,29,16,10,4)
145	(72,58,36,22,12,7,3)	195	(97,78,49,29,16,10,4)
146	(73,58,36,22,12,7,3)	196	(98,78,49,29,16,10,4)
147	(73,59,37,22,12,7,3)	197	(98,79,49,30,16,10,4)
148	(74,59,37,22,12,7,3)	198	(99,79,49,30,16,10,4)
149	(74,60,37,22,12,7,3)	199	(99,80,50,30,16,10,4)
150	(75,60,37,22,12,7,3)	200	(100,80,50,30,16,10,4)

From our recurrence formula we see that $F(100) = F(200) - (50,40,25,15,8,5,2) = (50,40,25,15,8,5,2) = F(101)$ and similarly that $F(201) = F(200).$ Therefore, we see that if $U \subset \mathbb{N}$ such that the values of $Q$ can be uniquely recovered from the mapping $F,$ then the only integers in \begin{align*}\{ 101, \dots, 200 \} \setminus U &= \{ 101, 104, 105, 112, 113, 120, \\ & \quad\quad 121, 124, 125, 132, 133, 140, \\ & \quad\quad 141, 144, 145, 152, 153, 160,\\ &\quad\quad 161, 164, 165, 172, 173, 180, \\ &\quad\quad 181, 184, 185, 192, 193, 200 \},\end{align*} which means that we are left with $$\left|U \cap \{101, \dots, 200\}\right| = 100 - 30 = 70.$$ Therefore, availing ourselves of the squeeze theorem and some of the other argumentation that we went through for the classic problem, we have that the probability that this total can be precisely determined from these cutoffs is $$\mathbb{P}(U) = 70\%.$$

Uniquely Genius Queen Bees

In Spelling Bee, a word game from The New York Times, you must create words using seven letters arranged in a honeycomb grid. Letters can be used more than once per word, but each word must be at least four letters long and include the central letter. You may recall a previous puzzle (RIP, FiveThirtyEight) based on Spelling Bee.

Each day, your goal is to score as many points as possible. Four-letter words are worth 1 point, longer words are worth the number of letters they contain, and “pangrams” (words containing every letter) provide 7 bonus points. But these specific details don’t matter for this week’s puzzle.

If you find all the words in a given day and therefore accrue the maximum number of points, you earn the “Queen Bee” ranking. Meanwhile, accruing smaller point totals earns you other rankings. In particular, the point cutoff for “Genius” is 70 percent of the maximum number of points, rounded to the nearest whole number. While the cutoff for “Genius” is clearly displayed in the puzzle, the “Queen Bee” point total is not readily shown.

Of course, this maximum total can be approximated by dividing the “Genius” cutoff by 0.7. Even so, the total may be ambiguous, since multiple “Queen Bee” values can result in the same “Genius” cutoff.

Suppose a given round of Spelling Bee has some very large, randomly chosen point total. What is the probability that this total can be precisely determined (i.e., without any ambiguity) from its point cutoff for “Genius”?

Let's assume that $Q$ is the Queen Bee point total and that $G$ is the Genius cutoff, and we have the functional definition $G: \mathbb{N} \to \mathbb{N}$ with $Q \mapsto G(Q) = [ 0.7 Q ],$ where $[\cdot]$ denotes the closest integer function, that is $[t] = \min \arg\!\min \{ |n - t | \mid n \in \mathbb{N} \},$ where we are rounding halves downward towards $0$. While the concept of uniform distribution on the natural numbers is untenable, let us assume that here we mean by some very large, randomly chosen point total of $Q$ that we have the following probabilistic definition. For any subset $A \subseteq \mathbb{N}$, let us define its probability as $$\mathbb{P} (A) = \lim_{n \to \infty} \frac{ \left| A \cap \{1, 2, \dots, n \} \right| }{n}.$$ This is loosely a limit of the sequence of uniform distributions on the sets $\{1, 2, \dots, n \}$ as $n \to \infty,$ but again I don't really want to get into the formal definitions of how that limit should be defined, let's just kinda run with it.

Anywhoozle, in this case, let's define $U = \{ n \in \mathbb{N} \mid |G^{-1}(n)| = 1 \}$ to be the desired set of all values of $Q$ that can be precisely and unambiguously determiend by the corresponding value of the $G$ function. It would probably be good to have some idea of what $U$ looks like before plowing ahead and getting to the calculation of the desired answer, that is, $\mathbb{P}(U).$ Let's start super simple and just give the first few values of the $G$ function:

q	0.7q	G(q)
1	0.7	1
2	1.4	1
3	2.1	2
4	2.8	3
5	3.5	3
6	4.2	4
7	4.9	5
8	5.6	6
9	6.3	6
10	7.0	7
11	7.7	8

Using these first 10 integers, we see that $3, 6, 7, 10 \in U.$ We also can see that for any $d \in \mathbb{N}$ that $$G(10d+k) = \left[0.7 \left(10d+k\right)\right] = 7d+G(k).$$ So we can surmise that in face for any $Q \in \mathbb{N}$ if $Q\! \mod\! 10 \in \{0, 3, 6, 7 \}$ then $Q \in U,$ then $$U = \left(10 \mathbb{N} \cup (3 + 10 \mathbb{N}) \cup (6 + 10\mathbb{N}) \cup (7 + 10\mathbb{N}) \right).$$ We see that $$\left| U \cap \{ 1,2, \dots, n\} \right| = \begin{cases} 4 \lfloor \frac{n}{10} \rfloor, &\text{if $n \!\mod\! 10 \in \{0,1,2\};$}\\ 4\lfloor \frac{n}{10} \rfloor+1, &\text{if $n \!\mod\!10 \in \{3,4,5\};$}\\ 4\lfloor \frac{n}{10} \rfloor+2, &\text{if $n \!\mod\!10 \equiv 6;$}\\ 4\lfloor \frac{n}{10} \rfloor+3, &\text{if $n \!\mod\!10 \in \{7,8,9\}.$}\end{cases}$$ Using the squeeze theorem and the fact that $$\lim_{n\to \infty} \frac{4 \lfloor \frac{n}{10} \rfloor}{n} \leq \mathbb{P} (U) \leq \lim_{n\to \infty} \frac{4 \lfloor \frac{n}{10} \rfloor + 3}{n},$$ we have the probability of getting a value of $Q$ that is precisely, unambiguously determined from its value of $G$ is $$\mathbb{P} (U) = \lim_{n \to \infty} \frac{1}{n} \left| U \cap \{1, 2, \dots, n \} \right| = \frac{2}{5} = 40\%.$$

Frederica's Trochoidal Film

For her next show, Frederica wants to mix things up. Instead of placing the light on the circumference of the wheel, she will pick a random point inside the circle. (Before you ask, let me clarify what “random” means here: Any two regions with the same area are equally likely to contain the point.)

As before, she will roll the wheel for one revolution along the ground and capture the motion with a single long exposure on her camera. On average, what can she expect the length of the path to be?

As before we will compute for any given starting point $$(x_0, y_0) \in \{ (x,y) \mid \sqrt{x^2 + (y-1)^2} \leq 1 \}$$ and calculate the path that it traces out as the wheel makes a full rotation. If the point $(x_0,y_0)$ is on the circumference of the circle, the path is known as a cycloid; however, if $(x_0,y_0)$ is in the interior of the wheel it is known as a curtate trochoid. Anywhoozle, let's again define our parametric equations ...

Let's assume that the point of light is at $x(0) = x_0, y(0) = y_0$, where without loss of generality let's assume that $x_0 \gt 0,$ and of course $r = \sqrt{x_0^2 + (y_0-1)^2} \leq 1.$ Then we see that we can write $x(0) = r \sin \theta, y(0) = 1 + r \cos \theta,$ for $\theta = \tan^{-1} \frac{x_0}{y_0 - 1} \in [0, \pi].$ Since after a rotation of $t \in [0,2\pi)$ we will have the wheel centered at $(t,1),$ while the angle that the point of light now makes as measured with respect to the positive $y$-axis, will now be $\theta + t.$ So at time $t$ the point of light would be at \begin{align*} x(t) &= t + r \sin (\theta + t) \\ y(t) &= 1 + r \cos (\theta + t).\end{align*} Differentiating with respect to time we get \begin{align*} \frac{dx}{dt} &= 1 + r \cos (\theta + t) \\ \frac{dy}{dt} &= -r \sin (\theta + t), \end{align*} so we see that the arclength of the path the light takes is \begin{align*}\ell &= \int_0^{2\pi} \sqrt{ \left( \frac{dx}{dt} \right)^2 + \left( \frac{dy}{dt} \right)^2 }\,dt \\ &= \int_0^{2\pi} \sqrt{ \left( 1 + r \cos (\theta + t)\right)^2 + \left( - r \sin (\theta + t) \right)^2 } \,dt \\ &= \int_0^{2\pi} \sqrt{ 1 + r^2 + 2r \cos (\theta + t) } \,dt.\end{align*} We can easily set $u = \theta + t$ and then through periodicity recognize that we have \begin{align*}\ell = \ell(r) &= \int_0^{2\pi} \sqrt{ 1 + r^2 + 2r \cos(\theta+t) } \,dt\\ &= \int_\theta^{\theta + 2\pi} \sqrt{ 1 + r^2 + 2r \cos u} \,du\\& = \int_0^{2\pi} \sqrt{ 1 + r^2 + 2r \cos u } \,du,\end{align*} regardless of the the value of $\theta.$ Now at this point, if we wanted to we could do some more algebra and appeal to the complete elliptic integrals of the second kind to find that $$\ell(r) = 4(1+r)E\left(\frac{2 \sqrt{r}}{1+r}\right),$$ where $$E(k) = \int_0^{\pi/2} \sqrt{1-k^2\sin^2t}\,dt;$$ however, since we would still need to plug this into another integral, this doesn't really do us any good.

However, we can us the integral definition of $\ell(r)$ and the definition of the randomly chosen starting point to get an expression for the expected length of the path. If we want to get the probability that some starting point $(x_0,y_0)$ is in the annulus centered at $(0,1)$ between radii $r$ and $r + dr,$ we get that the area of the annulus is $2\pi r \,dr,$ while the total probability of the unit disk centered at $(0,1)$ is $\pi,$ then we see that the conditional probability of the starting point being in the annulus between radii $r$ and $r + dr$ is $2r\, dr.$ Therefore, we get from the law of total expectation that $$\mathcal{L} = \mathbb{E} \left[ \ell \right] = \int_0^1 \ell(r) 2r \,dr.$$ Plugging back in the integral form of $\ell(r),$ we get $$\mathcal{L} = \int_0^1 \ell(r) 2r\,dr = \int_0^1 \int_0^{2\pi} 2r \sqrt{ 1 + r^2 + 2r \cos u } \,du \,dr,$$ which we can also recognize as the polar area integral of the function $$f(x,y) = 2\sqrt{ (1-x)^2 + y^2 }$$ over the unit disk. That is, $$\mathcal{L} = \int_{-1}^1 \int_{-\sqrt{1-x^2}}^{\sqrt{1-x^2}} 2\sqrt{(1-x)^2 + y^2} \,dy \,dx.$$

Since $$\int \sqrt{a^2 + t^2} \,dt = \frac{t}{2} \sqrt{a^2 + t^2} + \frac{a^2}{2} \ln \left| t + \sqrt{a^2 + t^2} \right| + C,$$ we can do this integration directly. We first get that \begin{align*}g(x) &= \int_{-\sqrt{1-x^2}}^{\sqrt{1-x^2}} 2 \sqrt{ (1-x)^2 + y^2} \,dy \\ &= 4 \int_0^{\sqrt{1-x^2}} \sqrt{ (1-x)^2 + y^2} \,dy \\ &= 4 \left[ \frac{y}{2} \sqrt{ (1-x)^2 + y^2 } + \frac{(1-x)^2}{2} \ln \left| y + \sqrt{ (1-x)^2 + y^2 } \right| \right]_0^{\sqrt{1-x^2}} \\ &= 4 \left[ \frac{\sqrt{1-x^2} \sqrt{2 - 2x}}{2} + \frac{(1-x)^2}{2} \ln \left| \sqrt{1-x^2} + \sqrt{2-2x} \right| - \frac{(1-x)^2}{2} \ln |1-x| \right] \\ &= 2\sqrt{2} (1-x) \sqrt{1+x} + 2(1-x)^2 \ln \left( \frac{\sqrt{1+x} + \sqrt{2}}{\sqrt{1-x}} \right).\end{align*} So we now have \begin{align*}\mathcal{L} &= \int_{-1}^1 g(x) \,dx \\ &= \int_{-1}^1 2\sqrt{2} (1-x)\sqrt{1+x} \,dx + \int_{-1}^1 2(1-x)^2 \ln \left( \frac{\sqrt{1+x} + \sqrt{2}}{\sqrt{1-x}} \right) \,dx.\end{align*} Using integration by parts, we have first integral is \begin{align*}I_1 &= \int_{-1}^1 2\sqrt{2}(1-x) \sqrt{1+x} \,dx \\ &= 2 \sqrt{2} \left( \left[ \frac{2}{3} (1-x) (1+x)^{3/2} \right]_{-1}^1 + \frac{2}{3} \int_{-1}^1 (1+x)^{3/2} \,dx \right) \\ &= 2 \sqrt{2} \left.\frac{4}{15} (1+x)^{5/2} \right|_{-1}^1 = 2\sqrt{2} \frac{4}{15} 2^{5/2} = \frac{64}{15}.\end{align*} We can break the second integral further into two integrals, namely $$I_2 = \int_{-1}^1 2(1-x)^2\ln \left( \sqrt{1+x} + \sqrt{2} \right) \,dx$$ and $$I_3 = \int_{-1}^1 2(1-x)^2 \ln \sqrt{1-x} \,dx = \int_{-1}^1 (1-x)^2 \ln (1-x) \,dx.$$

If we set $u = \ln \left( \sqrt{1+x} + \sqrt{2} \right)$ then we see that $$du = \frac{dx}{2 \sqrt{1+ x} ( \sqrt{1+x} + \sqrt{2} )} = \frac{ \sqrt{2} - \sqrt{1+x} }{2 \sqrt{1+x} (1-x)} dx,$$ so then if we pursue integration by parts we get to obtain \begin{align*}I_2 &= \int_{-1}^1 2(1-x)^2 \ln \left(\sqrt{1+x} + \sqrt{2}\right) \,dx \\ &= 2 \left( \left[ -\frac{(1-x)^3}{3} \ln \left( \sqrt{1+x} + \sqrt{2} \right) \right]_{-1}^1 + \int_{-1}^1 \frac{(1-x)^3}{3} \frac{\sqrt{2} - \sqrt{1+x}}{2 \sqrt{1+x} (1-x) } \,dx \right) \\ &= 2 \left( -\frac{4}{3} \ln 2 + \int_{-1}^1 \frac{\sqrt{2}}{6} \frac{(1-x)^2}{\sqrt{1+x}} \,dx - \int_{-1}^1 \frac{(1-x)^2}{6} \,dx \right) \\ &= 2 \left( -\frac{4}{3} \ln 2 + \left[ \frac{\sqrt{2}}{3} (1-x)^2 \sqrt{1+x} \right]_{-1}^1 + \frac{2\sqrt{2}}{3} \int_{-1}^1 (1-x) \sqrt{1+x} \,dx + \left[ \frac{(1-x)^3}{18} \right]_{-1}^1 \right) \\ &= 2 \left( -\frac{4}{3} \ln 2 + \frac{4}{9} + \frac{1}{3} \left( \frac{64}{15} \right) \right) = \frac{56}{15} -\frac{8}{3} \ln 2, \end{align*} where we are using our precalculated knowledge of $I_1$ in the second to last step.

Using integration by parts gives $$\int t^2 \ln t \,dt = \frac{t^3}{3} \ln t - \int \frac{t^2}{3} \,dt = \frac{t^3}{3} \ln t - \frac{t^3}{9} + C.$$ With the u = 1-x substituion we get $$I_3 = \int_{-1}^1 (1-x)^2 \ln (1-x) \,dx = \int_{0}^2 u^2 \ln u \,du = \left[\frac{u^3}{3} \ln u - \frac{u^3}{9} \right]_{0}^2 = \frac{8}{3} \ln 2 - \frac{8}{9}.$$ So putting it altogether we get the expected length of the uniformly random point of light to be \begin{align*}\mathcal{L} &= I_1 + I_2 + I_3 \\ &= \frac{64}{15} + \left( \frac{56}{15} - \frac{8}{3} \ln 2 \right) + \left( \frac{8}{3} \ln 2 - \frac{8}{9} \right) \\ &= 8 - \frac{8}{9} = \frac{64}{9} = 7.111111\dots.\end{align*}

Frederica's Cycloidal Film

For her photography show, Frederica Fiddleria attaches a light to a point on the circumference of a circular wheel with a radius of 1 meter. She points a camera at the wheel and, during a single long exposure, rolls the wheel for one revolution along the ground.

When she develops the film, she is curious about the path the light took as the wheel rolled. What is the length of this path?

Lo, and behold! Frederica's light source is traveling along a cycloidal path, which has some fairly well defined properties, but let's try to derive them from scratch. Let's assume that the center of the wheel starts at the point $(0,1).$ Since the circumference of the wheel is $2\pi,$ after one full revolution of the wheel, the center would end up at the point $(2\pi, 1).$ Without loss of generality, let's assume that the light was added to a point $P$ on the circumference of the circle such that the angle between $P$, the center of the circle and the positive $y$-axis is $\theta \in [0,\pi].$ In this case, we see that the point of light is at $x(0) = \sin \theta,$ and $y(0) = \cos \theta.$ After rotating for some time $t \in [0,2\pi),$ the center of the circle will be at the point $(t,1),$ while the angle that the point of light now makes as measured with respect to the positive $y$-axis, will now be $\theta + t.$ So the point of light will be given by the parametric equations \begin{align*} x(t) &= t + \sin(\theta + t),\\ y(t) & = 1 + \cos (\theta + t).\end{align*} In particular, taking derivatives with respect to time, we get \begin{align*} \frac{dx}{dt} &= 1 + \cos (\theta + t) \\ \frac{dy}{dt} &= - \sin (\theta + t).\end{align*}

Therefore, integrating the arclength formula and appealing to the half-angle formula, we see that no matter what the value of $\theta$ is, the length of the path the light took is given by \begin{align*}\ell &= \int_0^{2\pi} \sqrt{ \left(\frac{dx}{dt}\right)^2 + \left(\frac{dy}{dt}\right)^2 } \,dt \\ &= \int_0^{2\pi} \sqrt{ \left(1 + \cos (\theta + t)\right)^2 + \left( - \sin (\theta + t) \right)^2 } \,dt \\ &= \int_0^{2\pi} \sqrt{ 2 + 2 \cos (\theta + t) } \,dt \\ &= 2 \int_0^{2\pi} \sqrt{ \frac{ 1 + \cos (\theta + t) }{2} } \,dt \\ &= 2 \int_0^{2\pi} \left|\cos \left( \frac{\theta + t}{2}\right)\right| \,dt \\ &= 2 \int_0^{\pi - \theta} \cos \left(\frac{\theta + t}{2}\right) \,dt + \int_{\pi-\theta}^{2\pi} - \cos \left(\frac{\theta + t}{2}\right) \,dt \\ &= 4 \left. \sin \left(\frac{\theta + t}{2}\right) \right|_0^{\pi - \theta} - 4 \left. \sin \left(\frac{\theta + t}{2}\right) \right|_{\pi - \theta}^{2\pi} \\ &= 4 \left( \sin \frac{\pi}{2} - \sin \frac{\theta}{2} \right) - 4 \left( \sin \left(\pi + \frac{\theta}{2}\right) - \sin \frac{\pi}{2} \right) \\ &= 4 + 4 \sin \frac{\theta}{2} + 4 - 4 \sin \frac{\theta}{2} = 8\end{align*}