Riddler Express
Earlier this year, Dakota Jones used a crystal key to gain access to a hidden temple, deep in the Riddlerian Jungle. According to an ancient text, the crystal had exactly six edges, five of which were \(1\) inch long. Also, the key was the largest such polyhedron (by volume) with these edge lengths.
However, after consulting an expert, Jones realized she had the wrong translation. Instead of definitively having five edges that were \(1\) inch long, the crystal only needed to have four edges that were \(1\) inch long. In other words, five edges could have been \(1\) inch (or all six for that matter), but the crystal definitely had at least four edges that were \(1\) inch long.
The translator confirmed that the key was indeed the largest such polyhedron (by volume) with these edge lengths.
Once again, Jones needs your help. Now what is the volume of the crystal key?
Solution 1
Given the distances between the vertices of a tetrahedron the volume can be computed using the \(\textbf{Cayley–Menger determinant}\):
\[ 288\cdot V^{2}= \begin{vmatrix} 0&1&1&1&1\\\\ 1&0&d_{12}^{2}&d_{13}^{2}&d_{14}^{2}\\\\ 1&d_{12}^{2}&0&d_{23}^{2}&d_{24}^{2}\\\\ 1&d_{13}^{2}&d_{23}^{2}&0&d_{34}^{2}\\\\ 1&d_{14}^{2}&d_{24}^{2}&d_{34}^{2}&0 \end{vmatrix} \]
where the subscripts \(i, j \in \\{1, 2, 3, 4\\}\) represent the vertices and \(d_{ij}\) is the pairwise distance between them – i.e., the length of the edge connecting the two vertices.
If \(a\), \(b\), \(c\) be the three edges that meet at a point, and \(x,y,z\) the opposite edges. The volume \(V\) of the tetrahedron is given by
\[ V = \frac{\sqrt{4a^2b^2c^2-a^2X^2-b^2Y^2-c^2Z^2+XYZ}}{12} \]
where
\[ \begin{aligned} X = b^2 + c^2 - x^2 \\\\ Y = a^2 + c^2 - y^2 \\\\ Z = a^2 + b^2 - z^2 \end{aligned} \]
In our case, let \(a=b=c=y=1\), we have
\[ \begin{aligned} X = 2 - x^2 \\\\ Y = 1 \\\\ Z = 2 - z^2 \end{aligned} \]
We need to find the value of \(x\) and \(z\) that maximizes
\[ V = \frac{\sqrt{4- (2-x^2)^2-1- (2-z^2)^2+(2-x^2)(2-z^2)}}{12} \]
Setting the partial derivates \(\frac{\partial V}{\partial x}\) and \(\frac{\partial V}{\partial z}\) to zero, we get the equations
\[ \begin{aligned} 2 - 2x^2 + z^2 = 0 \\\\ 2 - 2z^2 + x^2 = 0 \\\\ \end{aligned} \]
Therefore, \(V\) attains the maximum value of \(\frac{1}{4\sqrt{3}}\) when \(x = z = \sqrt{2}\).
References
https://en.wikipedia.org/wiki/Tetrahedron
Solution 2
A polyhedron with \(6\) edges has to be a tetrahedron. In this particular case, we have a tetrahedron where one face is an equilateral triangle of side length \(1\). The volume of tetrahedron (which is a triangular pyramid where the base is an equilateral triangle) is given by
\[ \begin{aligned} Vol &= \frac{1}{3} \times base \times height \\\\ &= \frac{1}{3} \times \frac{\sqrt{3}}{4} \times height \end{aligned} \]
The volume is maximized when the height is maximized i.e. when another edge of length \(1\) is perpendicular to the base. Therefore the volume of the crystal key is
\[ Vol_{max} = \frac{1}{3}\times \frac{\sqrt{3}}{4} \times 1 = \frac{1}{4\sqrt{3}}. \]
Riddler Classic
One morning, Phil was playing with my daughter, who loves to cut paper with her safety scissors. She especially likes cutting paper into “strips,” which are rectangular pieces of paper whose shorter sides are at most \(1\) inch long.
Whenever Phil gives her a piece of standard printer paper (\(8.5\) inches by \(11\) inches), she picks one of the four sides at random and then cuts a \(1\)-inch wide strip parallel to that side. Next, she discards the strip and repeats the process, picking another side at random and cutting the strip. Eventually, she is left with nothing but strips.
On average, how many cuts will she make before she is left only with strips?
Extra credit: Instead of \(8.5\) by \(11\)-inch paper, what if the paper measures \(m\) by \(n\) inches? (And for a special case of this, what if the paper is square?)
Computational Solution 1
From the \(\textbf{Monte-Carlo}\) simulation below, we see that the expected number of cuts before we are left only with strips is \(\textbf{14.29}\).
from random import random
def avg_num_cuts_mc(m, n, runs= 1000000):
sum_num_cuts = 0
for _ in range(runs):
num_cuts, cm, cn = 0, m, n
while cm > 1 and cn > 1:
r = random()
if r < 0.5:
cm -= 1
else:
cn -= 1
num_cuts += 1
sum_num_cuts += num_cuts
return sum_num_cuts/runs
print(f"Expected number of cuts is {avg_num_cuts_mc(11, 9)}")Computational Solution 2
We have the following recurrence relation for the expected number of cuts
\[ C(m,n) = 1 + \frac{1}{2}C(m-1,n) + \frac{1}{2}C(n-1,m) \]
with initial conditions \(C(m,0)=C(0,n)=0\).
Solving the recurrence relation using \(\textbf{memoization}\) we see that the expected number of cuts is indeed \(\textbf{14.29}\).
def avg_num_cuts_rr(m, n):
C = [[0 for _ in range(n)] for _ in range(m)]
for i in range(1, m):
for j in range(1, n):
C[i][j] = 1 + 0.5*(C[i][j-1] + C[i-1][j])
return C[m-1][n-1]
print(f"Expected number of cuts is {avg_num_cuts_rr(11, 9)}")