Problem 86: Cuboid Route

Mathematical Foundation

Shortest Surface Path via Unfolding

Theorem 1 (Shortest surface path). For a cuboid with ordered dimensions $a \le b \le c$, the shortest surface path from one corner to the diagonally opposite corner has squared length

Proof. Unfolding the cuboid onto a plane produces three distinct planar configurations, each yielding a straight-line path connecting the two corners. The squared distances are:

We claim $d_1^2 \le d_2^2 \le d_3^2$ whenever $a \le b \le c$.

Proof of $d_1^2 \le d_2^2$:

Define $g(x) = x(2a + x) = 2ax + x^2$. Since $g'(x) = 2a + 2x > 0$ for $x > 0$, $g$ is strictly increasing on $(0, \infty)$. As $b \le c$, we have $g(b) \le g(c)$.

Proof of $d_2^2 \le d_3^2$:

Since $a \le b$, we have $a - b \le 0$, so the left side is $2c(a-b) \le 0$ and the right side is $(a-b)(a+b) \le 0$. Dividing by $a - b < 0$ (when $a < b$) reverses the inequality to $2c \ge a + b$, which holds since $c \ge b \ge a$ implies $2c \ge a + b$. When $a = b$, both sides equal zero. $\square$

Reduction to Pythagorean Triples

Lemma 1 (Integer path criterion). The shortest surface path has integer length if and only if there exists a positive integer $d$ such that $(a+b)^2 + c^2 = d^2$, i.e., $(a+b, c, d)$ forms a Pythagorean triple.

Proof. By Theorem 1, the squared path length is $(a+b)^2 + c^2$. This is a perfect square if and only if the path length $d = \sqrt{(a+b)^2 + c^2}$ is a positive integer. $\square$

Counting Valid Cuboids

Lemma 2 (Valid pair count). For a Pythagorean triple with legs $s$ and $c$ (where $s = a + b$), the number of ordered pairs $(a, b)$ satisfying $1 \le a \le b \le c$ and $a + b = s$ is

Proof. We require simultaneously:

• $a + b = s$ and $a \le b$, which gives $a \le s/2$, hence $a \le \lfloor s/2 \rfloor$.
• $b \le c$, i.e., $s - a \le c$, hence $a \ge s - c$.
• $a \ge 1$.

Therefore $a$ ranges over the integer interval $[\max(1, s-c),\; \lfloor s/2 \rfloor]$. The number of integers in this interval is $\lfloor s/2 \rfloor - \max(1, s-c) + 1$ when the interval is non-empty (i.e., when this expression is positive), and zero otherwise. $\square$

Theorem 2 (Cumulative count). The total number of cuboids with $1 \le a \le b \le c \le M$ having integer shortest surface path is

Proof. For each largest dimension $c \in \{1, \ldots, M\}$, the sum $s = a + b$ ranges over $\{2, \ldots, 2c\}$ (since $1 \le a \le b \le c$ implies $2 \le s \le 2c$). We include only those $s$ for which $s^2 + c^2$ is a perfect square (Lemma 1). For each qualifying $(s, c)$, Lemma 2 gives the count of valid $(a, b)$ decompositions. Summing over all $c$ yields the total. $\square$

Editorial

Once the cuboid is ordered as $a \le b \le c$, the shortest surface route depends only on $c$ and on the sum $s = a + b$. That collapses the geometric problem into a number-theoretic one: we only need to know when $s^2 + c^2$ is a perfect square.

The implementation grows the largest side $c$ one value at a time. For that fixed $c$, it generates every possible sum $s$ with $2 \le s \le 2c$, keeps only the values for which the shortest path length is integral, and then counts how many pairs $(a,b)$ produce that same sum while respecting $a \le b \le c$. Those decompositions are the real candidates; the perfect-square test filters which sums contribute. The first $c$ for which the cumulative total exceeds one million is the answer.

Pseudocode

Set the running total of valid cuboids to 0.
Set the current maximum side length to 0.

While the running total does not yet exceed one million:
    Increase the maximum side length c by 1

    For each possible sum s from 2 to 2c:
        Compute s^2 + c^2
        If this is not a perfect square, continue

        Count how many pairs a <= b <= c satisfy a + b = s
        Add that number of pairs to the running total

Return the first value of c that makes the total exceed one million.

Complexity Analysis

Time: $O(M^2)$ for the direct approach (checking $O(c)$ values of $s$ for each $c \le M$). This can be improved to $O(M\sqrt{M})$ by generating Pythagorean triples via the parametrization $s = k(m^2 - n^2)$, $c = 2kmn$ (and the symmetric role), for coprime $m > n \ge 1$ with $m - n$ odd.

Space: $O(1)$ auxiliary.

Answer

#include <bits/stdc++.h>
using namespace std;

int main() {
    // Problem 86: Cuboid Route
    // Shortest path for a <= b <= c: sqrt((a+b)^2 + c^2)
    // Let s = a+b; need s^2 + c^2 = perfect square.
    // Count of valid (a,b): floor(s/2) - max(1, s-c) + 1.
    // Answer: 1818

    int total = 0;
    int M = 0;

    while (total <= 1000000) {
        M++;
        int c = M;
        for (int s = 2; s <= 2 * c; s++) {
            long long dsq = (long long)s * s + (long long)c * c;
            long long d = (long long)sqrt((double)dsq);
            while (d * d < dsq) d++;
            while (d * d > dsq) d--;
            if (d * d == dsq) {
                int lo = max(1, s - c);
                int hi = s / 2;
                if (hi >= lo) {
                    total += hi - lo + 1;
                }
            }
        }
    }

    cout << M << endl;
    return 0;
}

"""
Problem 86: Cuboid Route

Find least M such that the number of cuboids a <= b <= c <= M
with integer shortest surface path exceeds 1,000,000.

Shortest path for a <= b <= c: sqrt((a+b)^2 + c^2)
Let s = a+b; need s^2 + c^2 = perfect square.
Count of valid (a,b) for given (s,c): floor(s/2) - max(1, s-c) + 1.

Answer: 1818
"""

import math


def solve():
    total = 0
    M = 0

    while total <= 1_000_000:
        M += 1
        c = M
        for s in range(2, 2 * c + 1):
            dsq = s * s + c * c
            d = math.isqrt(dsq)
            if d * d == dsq:
                lo = max(1, s - c)
                hi = s // 2
                if hi >= lo:
                    total += hi - lo + 1

    print(M)


if __name__ == "__main__":
    solve()