IOAI Training: Learn AI by solving problems

The problem in brief

You are given a vector $v = (1, -2, 3)$ and told that a principal component $\hat e$ of unit length points in the same direction. For the data point $x = (-1, -4, 6)$ you must compute three things: the unit vector $\hat e$ , the coordinate of $x$ along $\hat e$ (the inner product, which is what PCA keeps when it reduces dimension), and the residual, the part of $x$ that this one component cannot explain. Each answer is asked in a normalised integer form and turned into a multiple-choice sum, so an arithmetic slip lands on a wrong letter.

How you are scored

Three multiple-choice parts worth 5 points each. Our answers, checked with exact fractions and with NumPy in solution.py:

part	quantity	exact value	requested sum	choice
2.1	$\hat e$	$\frac{1}{\sqrt{14}}(1,-2,3)$	$14 + 1 - 2 + 3 = 16$	D
2.2	$x \cdot \hat e$	$\frac{25}{\sqrt{14}}$	$14 + 25 = 39$	E
2.3	$r$	$\frac{1}{14}(-39,-6,9)$	$14 - 39 - 6 + 9 = -22$	B

Question by question

2.1 The unit direction

To turn $v$ into a unit vector with the same direction, divide by its length:

\|v\|_2 = \sqrt{1^2 + (-2)^2 + 3^2} = \sqrt{14}, \qquad \hat e = \frac{v}{\|v\|_2} = \frac{1}{\sqrt{14}}\begin{pmatrix}1\\-2\\3\end{pmatrix}.

So $a = 14$ , $(b, c, d) = (1, -2, 3)$ . The condition $\gcd(a, b^2, c^2, d^2) = \gcd(14, 1, 4, 9) = 1$ is there to make the form unique: without it, $\frac{1}{\sqrt{56}}(2,-4,6)$ would describe the same vector. "Same direction" also fixes the sign; $-\hat e$ is a unit principal component too, but it points the other way.

$a + b + c + d = 16$ : answer D.

2.2 The projection (the PCA coordinate)

x \cdot \hat e = \frac{1}{\sqrt{14}}\big((-1)(1) + (-4)(-2) + (6)(3)\big) = \frac{-1 + 8 + 18}{\sqrt{14}} = \frac{25}{\sqrt{14}} \approx 6.68 .

Here $a = 14$ , $b = 25$ , and $\gcd(14, 625) = 1$ since $625 = 5^4$ . A tempting mistake is to rationalise the denominator, $\frac{25\sqrt{14}}{14}$ , which is not of the requested shape; another is to use $v$ instead of $\hat e$ and report $x \cdot v = 25$ .

$a + b = 39$ : answer E.

2.3 The residual

The residual is what remains of $x$ after removing its component along $\hat e$ :

r = x - (x\cdot\hat e)\,\hat e = x - \frac{x \cdot v}{v \cdot v}\, v = \begin{pmatrix}-1\\-4\\6\end{pmatrix} - \frac{25}{14}\begin{pmatrix}1\\-2\\3\end{pmatrix} = \frac{1}{14}\begin{pmatrix}-14 - 25\\ -56 + 50\\ 84 - 75\end{pmatrix} = \frac{1}{14}\begin{pmatrix}-39\\-6\\9\end{pmatrix}.

Note the shortcut in the middle: $(x\cdot\hat e)\hat e = \frac{x\cdot v}{\|v\|^2}v$ , so the square roots cancel and everything stays rational. Check $\gcd(14, 39, 6, 9) = 1$ (39 and 9 are odd, and 14 shares no factor 3 with them).

Two independent checks that catch almost any slip:

Orthogonality: $r \cdot v = \frac{1}{14}(-39 + 12 + 27) = 0$ . The residual must be perpendicular to the direction we projected on.
Pythagoras: $\|x\|^2 = 1 + 16 + 36 = 53$ must equal $(x\cdot\hat e)^2 + \|r\|^2 = \frac{625}{14} + \frac{1521 + 36 + 81}{196} = \frac{625}{14} + \frac{117}{14} = \frac{742}{14} = 53$ . It does.

$a + b + c + d = 14 - 39 - 6 + 9 = -22$ : answer B.

The key idea

Projection splits a vector into two perpendicular pieces, one along a chosen direction and one orthogonal to it:

x = \underbrace{(x\cdot\hat e)\,\hat e}_{\text{kept by PCA}} + \underbrace{r}_{\text{reconstruction error}}, \qquad r \perp \hat e .

The plane containing e-hat and x, drawn to scale. x is the hypotenuse of a right triangle whose legs are the projection along e-hat (length 6.68) and the residual (length 2.89).

Because the two pieces are perpendicular, lengths add in squares: $\|x\|^2 = (x\cdot\hat e)^2 + \|r\|^2$ . Summed over a whole dataset (of centred points), this says "total variance = variance kept + reconstruction error". PCA chooses $\hat e$ to maximise the kept part, which is the same as minimising the residuals: the first principal component is the direction with the largest variance and simultaneously the line closest to the data in the least-squares sense. Here, one direction keeps $44.64/53 \approx 84\%$ of $\|x\|^2$ for this point; the residual holds the other 16 %.

The full solution

solution.py computes everything with exact fractions (normalising the gcd as the statement requires) and cross-checks with floating point:

v, x = np.array([1, -2, 3]), np.array([-1, -4, 6])
a, xv = v @ v, x @ v                      # 14, 25
coef = Fraction(xv, a)                    # x.v / v.v = 25/14
r = [Fraction(int(xi)) - coef * int(vi) for xi, vi in zip(x, v)]   # (-39, -6, 9)/14

Results

part	our value	sum	choice	independent check
2.1	$\frac{1}{\sqrt{14}}(1,-2,3)$	16	D	$\\|\hat e\\| = 1$
2.2	$25/\sqrt{14}$	39	E	NumPy dot product
2.3	$\frac{1}{14}(-39,-6,9)$	$-22$	B	$r\cdot v = 0$ and $53 = \frac{625}{14} + \frac{117}{14}$

What to remember

Normalise by the length: $\hat e = v/\|v\|$ , and the PCA coordinate of $x$ is simply $x \cdot \hat e$ .
Project with $\frac{x\cdot v}{v\cdot v}v$ to avoid square roots: the projection does not depend on the length of $v$ .
Residual $\perp$ direction and Pythagoras are two free checks that catch nearly every arithmetic error in projection problems.
PCA is two equivalent optimisations: maximise the variance of the projections, or minimise the squared residuals; the right angle is what makes them the same problem.

"""USAAIO 2026 Round 1, Problem 2: projection onto a principal component.

Exact computation with sympy-free rational arithmetic (fractions + integer
square roots), numeric cross-check with NumPy, and the 3-D figure.
Run:  python solution.py
"""
from fractions import Fraction
from math import gcd, isqrt
import numpy as np
import matplotlib
matplotlib.use("Agg")
import matplotlib.pyplot as plt

v = np.array([1, -2, 3])
x = np.array([-1, -4, 6])

# ---- 2.1  e = v / ||v|| = (1/sqrt(a)) (b, c, d)
a = int(v @ v)                                   # ||v||^2 = 14
b, c, d = v
assert gcd(gcd(a, b * b), gcd(c * c, d * d)) == 1
print("2.1: a, b, c, d =", a, b, c, d, " sum =", a + b + c + d)      # 16 -> D

# ---- 2.2  x . e = (x . v) / sqrt(14) = b / sqrt(a)
xv = int(x @ v)                                  # 25
assert gcd(a, xv * xv) == 1
print("2.2: projection = %d/sqrt(%d), a + b = %d" % (xv, a, a + xv))   # 39 -> E

# ---- 2.3  r = x - (x . e) e = x - (x.v / v.v) v, exact fractions
coef = Fraction(xv, a)                           # 25/14
r = [Fraction(int(xi)) - coef * int(vi) for xi, vi in zip(x, v)]
den = 1
for ri in r:
    den = den * ri.denominator // gcd(den, ri.denominator)
num = [int(ri * den) for ri in r]
g = gcd(gcd(den, num[0]), gcd(num[1], num[2]))
den, num = den // g, [n // g for n in num]
print("2.3: r = (1/%d) %s, sum = %d" % (den, num, den + sum(num)))     # -22 -> B
assert sum(ni * vi for ni, vi in zip(num, v)) == 0                    # r is orthogonal to v

# ---- numeric cross-check and Pythagoras
e = v / np.linalg.norm(v)
p = x @ e
res = x - p * e
assert np.isclose(p, 25 / np.sqrt(14)) and np.allclose(res, np.array([-39, -6, 9]) / 14)
assert np.isclose(x @ x, p**2 + res @ res)       # 53 = 625/14 + 117/14
print("||x||^2 = %.4f = %.4f + %.4f" % (x @ x, p**2, res @ res))

# ---- figure: the plane spanned by e and x, drawn in true proportions
# coordinates in the orthonormal basis (e, r/||r||) of that plane
rn = np.linalg.norm(res)
plt.rcParams.update({"font.size": 12})
fig, ax = plt.subplots(figsize=(9, 4.8))
ax.plot([-0.8, 8.2], [0, 0], color="grey", ls="--", lw=1)
ax.text(8.0, -0.35, "principal direction $\\hat e$", ha="right", color="grey")
kw = dict(angles="xy", scale_units="xy", scale=1, width=0.006)
ax.quiver(0, 0, p, rn, color="#1f77b4", **kw)
ax.quiver(0, 0, p, 0, color="#2ca02c", **kw)
ax.quiver(p, 0, 0, rn, color="#d62728", **kw)
ax.quiver(0, 0, 1, 0, color="black", width=0.009, angles="xy", scale_units="xy", scale=1)
ax.plot([p - 0.25, p - 0.25, p], [0, 0.25, 0.25], color="black", lw=1)   # right angle
ax.text(p / 2 - 1.2, rn / 2 + 0.5, "$x$, $\\|x\\|^2 = 53$", color="#1f77b4")
ax.text(p / 2, -0.45, "$(x\\cdot\\hat e)\\,\\hat e$, length $25/\\sqrt{14}\\approx 6.68$",
        color="#2ca02c", ha="center")
ax.text(p + 0.15, rn / 2, "residual $r$\nlength $\\sqrt{117}/\\sqrt{14}\\approx 2.89$", color="#d62728")
ax.text(0.5, 0.15, "$\\hat e$", fontsize=13)
ax.set_aspect("equal"); ax.set_xlim(-0.8, 10.2); ax.set_ylim(-1, 3.5); ax.axis("off")
ax.set_title("In the plane of $\\hat e$ and $x$: projection and residual meet at a right angle")
fig.tight_layout()
fig.savefig("figures/projection.png", dpi=150)

Projection onto a Principal Component