Problem 9: Special Pythagorean Triplet

Mathematical Development

Parametric Reduction

Theorem 1 (Reduction to a single variable). Suppose positive integers $a, b, c$ satisfy

for a given $s > 0$. Then

Proof. From the sum constraint, $c = s - a - b$. Substituting into the Pythagorean condition:

Cancelling $a^2 + b^2$ from both sides:

Solving for $b$:

hence $b = \frac{s(s - 2a)}{2(s - a)}$. $\square$

Corollary 1. Setting $s = 1000$:

Theorem 2 (Integrality condition). With $s = 1000$, the value $b$ is a positive integer if and only if $(1000 - a) \mid 500000$.

Proof. Perform polynomial long division on the numerator:

Equivalently, write $500000 - 1000a = 1000(1000 - a) - 500000$, so

For $b \in \mathbb{Z}^+$, we need $(1000 - a) \mid 500000$ and $500000/(1000 - a) < 1000$, i.e., $1000 - a > 500$, i.e., $a < 500$. $\square$

Enumeration of Solutions

Theorem 3 (Existence and uniqueness). The unique Pythagorean triplet $(a, b, c)$ with $a < b < c$ and $a + b + c = 1000$ is $(200, 375, 425)$.

Proof. We require:

1. $(1000 - a) \mid 500000$,
2. $a < b < c$ with $a, b, c > 0$.

The prime factorization $500000 = 2^5 \cdot 5^6$ has $(5+1)(6+1) = 42$ positive divisors. Setting $d = 1000 - a$, we need $d \mid 500000$ and $a = 1000 - d > 0$, so $d < 1000$. Also $d > 500$ by Theorem 2.

The divisors of $500000$ in the range $(500, 1000)$ are:

• $d = 625$: $a = 375$, $b = 1000 - 500000/625 = 1000 - 800 = 200$, $c = 425$. Here $b < a$, so reorder: $(a, b, c) = (200, 375, 425)$.
• $d = 800$: $a = 200$, $b = 1000 - 500000/800 = 1000 - 625 = 375$, $c = 425$. This gives $(200, 375, 425)$.

Both cases yield the same triplet. No other divisor of $500000$ lies in $(500, 1000)$.

Verification. $200^2 + 375^2 = 40000 + 140625 = 180625 = 425^2$. Also $200 + 375 + 425 = 1000$. The ordering $200 < 375 < 425$ holds. $\square$

Remark. The triplet $(200, 375, 425) = 25 \cdot (8, 15, 17)$, where $(8, 15, 17)$ is a primitive Pythagorean triple generated by the classical parametrization with $m = 4, n = 1$: $a = 2mn = 8$, $b = m^2 - n^2 = 15$, $c = m^2 + n^2 = 17$.

Editorial

We iterate over the possible first leg $a$ and use the linear relation derived from $a+b+c=s$ and $a^2+b^2=c^2$ to solve for $b$. For each $a$, we compute the candidate numerator and denominator, check whether the division is exact, recover $b$ and $c = s-a-b$, and return the product once the ordering $a < b < c$ holds. This is sufficient because every Pythagorean triple with sum $s$ must satisfy the derived formula for $b$.

Pseudocode

Algorithm: Special Pythagorean Triple for a Fixed Perimeter
Require: A target perimeter s.
Ensure: The product abc for the unique Pythagorean triple with a + b + c = s.
1: For each admissible value of a in increasing order do:
2:     Compute nu ← s(s - 2a) and delta ← 2(s - a).
3:     If delta divides nu, set b ← nu / delta and c ← s - a - b.
4:     If a < b < c and a^2 + b^2 = c^2, return a · b · c.
5: Return failure if no such triple exists.

Complexity Analysis

Theorem 4. The algorithm finds the triplet in $O(s)$ time and $O(1)$ space, where $s = a + b + c$.

Proof. The outer loop iterates $a$ from 1 to at most $s/3$ (since $a < b < c$ and $a + b + c = s$ imply $a < s/3$). Each iteration performs $O(1)$ arithmetic: one division and a divisibility check. No auxiliary data structures are needed. $\square$

Remark. An $O(\sqrt{s})$ algorithm is possible by directly iterating over divisors of $s^2/4$, but the linear approach suffices for $s = 1000$.

Answer

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

int main() {
    const int s = 1000;
    for (int a = 1; a < s / 3; a++) {
        int num = s * s / 2 - s * a;
        int den = s - a;
        if (num % den == 0) {
            int b = num / den;
            int c = s - a - b;
            if (a < b && b < c) {
                cout << (long long)a * b * c << endl;
                return 0;
            }
        }
    }
    return 0;
}

s = 1000
for a in range(1, s // 3):
    num = s * s // 2 - s * a
    den = s - a
    if num % den == 0:
        b = num // den
        c = s - a - b
        if a < b < c:
            print(a * b * c)
            break