Vamshi Jandhyala - Can You Climb Your Way To Victory?

Riddler Express

While watching batter spread out on my waffle iron, and thinking back to a recent conversation I had with Friend-of-The-Riddler™ Benjamin Dickman, I noticed the following sequence of numbers:

\[1, 4, 4, 0, 4, 8, 0, 0, 4, 4, 8, …\]

Before you ask — yes, you can find this sequence on the On-Line Encyclopedia of Integer Sequences. However, for the full Riddler experience, I urge you to not look it up. See if you can find the next few terms in the sequence, as well as the pattern.

Now, for the actual riddle: Once you’ve determined the pattern, can you figure out the average value of the entire sequence?

Solution

Let the sequence be denoted by $s(n)$. You can find more about the sequence here 😊. Then $s(n)$ represents the number of ways an integer $n$ can be expressed as a sum of two squares (positive, negative, or zero). That is, $s(n)$ denotes the number of solutions in integers $(x,y$ to the equation $x^2 +y^2 = n$. For example, $s(5)=8$ since the solutions to $x^2 + y^2 = 5$ are $(1,2)$, $(2,1)$, $(-1,2)$, $(2,-1)$, $(1,-2)$, $(-2,1)$, $(-1,-2)$, and $(-2,-1)$. Because $s(n) = 0$ whenever $n$ has the form $4k - 1$, $s(n)$ is a very erratic function.Thankfully, the problem is about the average value of $s(n)$ as $n \rightarrow \infty$. If we define $t(n)$ to be the number of solutions in integers to $x^2 + y^2 \leq n$, then the average of $s(k)$ for $0 \leq k \leq n$ is

\[ \frac{s(0) + s(1) + \dots + s(n)}{n+1} = \frac{t(n)}{n+1} \]

The code (using brute force) for calculating $t(n)$ and $t(n)/(n+1)$ is given below:

from math import sqrt, ceil

def t(n):
    t, l = 0, ceil(sqrt(n))+1
    for i in range(0, n+1):
        for j in range(-l, l):
            for k in range(-l, l):
                if j**2 + k**2 == i:
                    t += 1
    return t, t/(n+1)

print(list(map(t, [1,2,3,4,5,10,20,50,100])))

Here is a table of $t(n)$ and $t(n)/(n+1)$ for a few values of $n$:

$n$	1	2	3	4	5	10	20	50	100
$t(n)$	5	9	9	13	21	37	69	161	317
$\frac{t(n)}{n+1}$	2.5	3	2.25	2.6	3.5	3.36	3.29	3.16	3.15

$\textbf{Theorem:}$ $ _{n } = $.

$\textbf{Proof}.$ The proof from the reference below is based on a geometric interpretation of $t(n)$, and is due to Carl Friedrich Gauss $(1777–1855)$: $t(n)$ is the number of points in or on a circle $x^2 + y^2 = n$ with integer coordinates. For example, $t(10) = 37$ since the circle centered at the origin of radius $\sqrt{10}$ contains $37$ lattice points as illustrated in the figure below:

If we draw a square with area $1$ centered at each of the $37$ points, then the total area (in grey) of the squares is also $t(n)$. Thus we would expect the area of the squares to be approximately the area of the circle, or in general, $t(n)$ to be approximately $\pi(\sqrt{n})^2 = \pi n$. If we expand the circle of radius $\sqrt{n}$ by half the length of the diagonal $\sqrt{2}/2$ of a square of area $1$, then the expanded circle contains all the squares. If we contract the circle by the same amount, then the contracted circle would be contained in the union of all the squares as seen in the figure below:

Thus,

\[ \pi(\sqrt{n} - \sqrt{2}/2)^2 \leq t(n) \leq \pi(\sqrt{n} + \sqrt{2}/2)^2 \]

Dividing each term by $n+1$ and applying the squeeze theorem for limits yields the desired result.

References

Charming Proofs: A Journey into Elegant Mathematics

Riddler Classic

The finals of the sport climbing competition has eight climbers, each of whom compete in three different events: speed climbing, bouldering and lead climbing. Based on their time and performance, each of the eight climbers is given a ranking (first through eighth, with no ties allowed) in each event, as well as a corresponding score ($1$ through $8$, respectively).

The three scores each climber earns are then multiplied together to give a final score. For example, a climber who placed second in speed climbing, fifth in bouldering and sixth in lead climbing would receive a score of $2 × 5 × 6$, or $60$ points. The gold medalist is whoever achieves the lowest final score among the eight finalists.

What is the highest (i.e., worst) score one could achieve in this event and still have a chance of winning (or at least tying for first place overall)?

Computational Solution

From the $\textbf{Monte-Carlo simulation}$ below, we see that the worst score one could achieve and still have a chance of winning is $\textbf{48}$.

from random import shuffle
from operator import mul
from functools import reduce

def max_min_score(np, ne, runs = 1000000):
    max_min_score = 0
    for _ in range(runs):
        ranks = [list(range(1,np+1)) for i in range(ne)]
        for i in range(ne):
            shuffle(ranks[i])
        scores = [reduce(mul, [ranks[j][i] for j in range(ne)]) for i in range(np)]
        min_score = min(scores)
        if min_score > max_min_score:
            max_min_score = min_score
    return max_min_score

print(max_min_score(8,3))