Problem 222: Sphere Packing

Mathematical Development

If two spheres of radii $r_i$ and $r_j$ touch opposite sides of a tube of radius $R$, the horizontal distance between their centres is

Since tangent spheres have centre distance $r_i + r_j$, the axial gap $\Delta(r_i,r_j)$ satisfies

so

For an ordering $r_{\sigma(1)},\dots,r_{\sigma(n)}$, the tube length is therefore

Now write

The function $g$ is increasing and concave. Hence for

we have the exchange inequality

This says that, with the same total adjacent sum, pairing large radii with small radii is never worse than pairing large with large and small with small.

Applying that exchange repeatedly forces an optimal arrangement into a pendulum order: one parity class is listed from large to small, then the other parity class is listed from small to large. For the radii $30,\dots,50$, this leaves only two genuinely different candidates:

and

Evaluating both gives the optimum.

Editorial

The geometry only contributes one formula, namely the gap

After that, the problem is purely about arranging the radii. Because this gap depends on the pair only through $r_i+r_j$, and because the square root is concave, any local pattern that puts two large radii next to each other can be improved by separating them and using the small radii as spacers. That is the observation that kills the $21!$ search.

Once the exchange argument is pushed all the way through, the surviving candidates are the two pendulum orders: one starts with the even radii from $50$ down to $30$ and then climbs through the odd radii, and the other does the same with the parities reversed. The program simply builds those two orders, evaluates the tube length formula, and keeps the smaller value.

Pseudocode

Define the gap formula for two consecutive spheres.

Build the first pendulum order:
    take 50, 48, 46, ..., 30
    then append 31, 33, 35, ..., 49

Build the second pendulum order:
    take 49, 47, 45, ..., 31
    then append 30, 32, 34, ..., 50

For each of the two orders:
    start with the two end-cap contributions
    add the gap between every consecutive pair

Convert the shorter length from millimetres to micrometres.
Round to the nearest integer and print it.

Complexity Analysis

• Time: $O(n)$ once the two candidate orders are written down.
• Space: $O(n)$ for the order itself.

Answer

#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <vector>

using namespace std;

double gap(int left, int right, double radius = 50.0) {
    return 2.0 * sqrt(radius * (left + right - radius));
}

double tubeLength(const vector<int>& order) {
    double total = order.front() + order.back();
    for (size_t i = 0; i + 1 < order.size(); i++) {
        total += gap(order[i], order[i + 1]);
    }
    return total;
}

vector<vector<int>> pendulumOrders(const vector<int>& radii) {
    vector<int> sorted = radii;
    sort(sorted.begin(), sorted.end());

    vector<vector<int>> orders;

    for (int parity = 0; parity < 2; parity++) {
        vector<int> first;
        vector<int> second;

        for (auto it = sorted.rbegin(); it != sorted.rend(); ++it) {
            if ((*it & 1) == parity) first.push_back(*it);
        }

        for (int value : sorted) {
            if ((value & 1) != parity) second.push_back(value);
        }

        orders.push_back(first);
        orders.back().insert(orders.back().end(), second.begin(), second.end());
    }

    return orders;
}

int main() {
    vector<int> radii;
    for (int value = 30; value <= 50; value++) {
        radii.push_back(value);
    }

    double best = 1e100;
    for (const auto& order : pendulumOrders(radii)) {
        best = min(best, tubeLength(order));
    }

    cout << llround(best * 1000.0) << '\n';
    return 0;
}

"""
Problem 222: Sphere Packing

The tube length for an ordering r_1, ..., r_n is

    r_1 + r_n + sum gap(r_i, r_{i+1}),

where gap(x, y) = 2 * sqrt(R * (x + y - R)) and R = 50.

Because gap depends only on x + y and is concave in that sum, an exchange
argument collapses the search to the two pendulum orders:

    50, 48, 46, ..., 30, 31, 33, ..., 49
    49, 47, 45, ..., 31, 30, 32, ..., 50

Evaluating both is enough.
"""

import math


def gap(left, right, radius=50.0):
    return 2.0 * math.sqrt(radius * (left + right - radius))


def tube_length(order):
    total = order[0] + order[-1]
    for index in range(len(order) - 1):
        total += gap(order[index], order[index + 1])
    return total


def pendulum_orders(radii):
    low_to_high = sorted(radii)
    high_parity = [value for value in reversed(low_to_high) if value % 2 == low_to_high[-1] % 2]
    low_parity = [value for value in low_to_high if value % 2 != low_to_high[-1] % 2]

    yield high_parity + low_parity

    high_parity = [value for value in reversed(low_to_high) if value % 2 != low_to_high[-1] % 2]
    low_parity = [value for value in low_to_high if value % 2 == low_to_high[-1] % 2]
    yield high_parity + low_parity


def solve():
    radii = list(range(30, 51))
    best = min(tube_length(order) for order in pendulum_orders(radii))
    print(round(best * 1000))


if __name__ == "__main__":
    solve()