## Riddler Express

Max the Mathemagician is calling for volunteers. He has a magic wand of length $10$ that can be broken anywhere along its length (fractional and decimal lengths are allowed). After the volunteer chooses these breakpoints, Max will multiply the lengths of the resulting pieces. For example, if they break the wand near its midpoint and nowhere else, the resulting product is $5×5$, or $25$. If the product is the largest possible, they will win a free backstage pass to his next show. (Amazing, right?)

You raise your hand to volunteer, and you and Max briefly make eye contact. As he calls you up to the stage, you know you have this in the bag. What is the maximum product you can achieve?

Extra credit: Zax the Mathemagician (no relation to Max) has the same routine in his show, only the wand has a length of $100$. What is the maximum product now?

## Solution

Let $L$ be the length of the wand and let $x_1,x_2,\dots,x_n$ be the lengths of the $n$ resulting pieces after the volunteer chooses the breakpoints. Using the famous Arithmetic-Geometric mean inequality $AM \geq GM$, we have

\begin{aligned} \frac{x_1+\dots+x_n}{n} &\geq (x_1x_2 \cdots x_n)^{1/n} \\ \implies \left(\frac{L}{n}\right)^n &\geq x_1x_2 \cdots x_n \end{aligned}

The equality is achieved when all the pieces are equal.

The function $f(x) = \left(\frac{L}{x}\right)^x$ attains its maximum value at $x = \frac{L}{\mathrm{e}}$. This can be verified using basic calculus.

As the wand can only be broken into an integral number of pieces, the maximum product is obtained at $n^* = \left\lfloor \frac{L}{\mathrm{e}}\right\rfloor$ or $n^* = \left\lceil \frac{L}{\mathrm{e}} \right\rceil$.

The number of equal pieces required to achieve the maximum product when $L=10$ is $n^* = \left\lceil \frac{10}{\mathrm{e}} \right\rceil = 4$ and the maximum product that can be achieved is $(10/4)^4 = \bf{39.0625}$.

The number of equal pieces required to achieve the maximum product when $L=100$ is $n^* = \left\lceil \frac{100}{\mathrm{e}} \right\rceil = 37$ and the maximum product that can be achieved is $(100/37)^{37} \approx \bf{9474061716781824}$.

## Riddler Classic

This week’s Classic comes courtesy of Alexander Zhang of Lynbrook High School, California. Alexander won first place in the mathematics category at this year’s International Science and Engineering Fair for his work at the intersection of topology and medicine. He developed his own highly efficient algorithms to detect and remove defects (like “handles” or “tunnels”) from three-dimensional scans (e.g., MRI). Alexander has long had an interest in topology, which just might be related to his submitted puzzle.

Consider the following image showing a particular uppercase sans serif font:

Alexander thinks many of these letters are equivalent, but he leaves it to you to figure out how and why. He also has a message for you:

It may not look like much, but Alexander assures me that it is equivalent to exactly one word in the English language.

What is Alexander’s message?

## Solution

### Partitioning scheme 1

If alphabets are partitioned into equivalence classes such that two alphabets are in the same class when one can be continuously deformed into another, we have the following equivalence classes:

1 continous line - C,G,I,J,M,N,S,U,V,W,Z
1 hole with 1 dead end - P,Q
1 hole with 2 dead ends - A,R
2 holes - B
1 hole - D,O


### Partitioning scheme 2

If alphabets are partitioned into equivalence classes based on the number of non-overlapping continous strokes, we have the following three equivalence classes:

1 continuous stroke - C,D,G,I,J,L,M,N,O,P,Q,S,U,V,W,Z
2 non-overlapping continuous strokes - A,B,E,F,R,T,X,Y
3 non-overlapping continuous strokes - H,K


Using the code below, we see that YIRTHA can be decoded as EUREKA under partitioning scheme 1. Under paritioning scheme 2, YIRTHA can be decoded as APATHY, TWEAKY or EUREKA.

import urllib.request
DICT_URL = "https://norvig.com/ngrams/enable1.txt"

response = urllib.request.urlopen(url)
return [l.decode('utf-8').strip().upper() for l in response.readlines()]

target_word = "YIRTHA"
relevant_words = [w for w in ALL_WORDS if len(w)==len(target_word)]
scheme1 = ['AR','B','CGIJMNSUVWZ','DO','EFTY','HKX','PQ']
scheme2 = ['ABEFRTXY','CDGIJLMNOPQSUVWZ','HK']

def decode(grouping):
target_subgroups = []
for l in target_word:
for sg in grouping:
if l in sg:
target_subgroups.append(sg)
matches = set()
for word in relevant_words:
if all([c in sg for c, sg in zip(word, target_subgroups)]):