2026 USAAIO Round 1 Sample problems, Problem 1

AI Olympiads
1

Problem 1

Consider a sample data point x\in\mathbb{R}^{d}. Let \hat{e}\in\mathbb{R}^{d} be a principal component with unit length.

Part 1.1

Let d=3. Consider vector

v=\begin{bmatrix}1\\ -2\\ 3\end{bmatrix}.

Let \hat{e} be in the same direction as v. We can write \hat{e} in the following form:

\hat{e}=\frac{1}{\sqrt{a}}\begin{bmatrix}b\\ c\\ d\end{bmatrix}.

where b, c, d are integers and a is not a perfect square. What is the value of a+b+c+d?

  • A. 0.
  • B. 12.
  • C. 14.
  • D. 16.
  • E. 20.

Part 1.2

Let
x=\begin{bmatrix}-1\\ -4\\ 6\end{bmatrix}.
Compute the projection of x onto \hat{e}. Your answer can be written as \frac{b}{\sqrt{a}}, where b is an integer and a is not a perfect square. What is the value of a+b?

  • A. 14.
  • B. -6.
  • C. -11.
  • D. 34.
  • E. 39.

Part 1.3

Let r be the residual after x is projected onto \hat{e}. We can write r in the following form:

r=\frac{1}{a}\begin{bmatrix}b\\ c\\ d\end{bmatrix}

where b, c, d are integers, a is a positive integer and \text{gcd}(a,b,c,d)=1. What is the value of a+b+c+d?

  • A. 14.
  • B. -22.
  • C. -36.
  • D. 50.
  • E. 64.
2

We want to normalize v, so we divide v by its magnitude |v|. |v| = \sqrt{1+4+9}, so \hat{e} = \frac{1}{\sqrt{14}} \begin{bmatrix} 1 \\ -2 \\ 3 \end{bmatrix}. This gives us 14+1-2+3 = \boxed{D. 16}.

The projection of x onto \hat{e} is the vector of length |x|\cos{\theta} in the direction of \hat{e}. Since x \cdot \hat{e} = |x||\hat{e}|\cos{\theta}, we wish to find \hat{e}|x|\cos{\theta} = \hat{e}(x\cdot \hat{e}). This evaluates to \frac{25}{14} \begin{bmatrix}1 \\ -2 \\ 3 \end{bmatrix}. Assuming the question meant scalar projection, we get \frac{25}{\sqrt{14}} which yields \boxed{E. 39}.

The residual r is simply x - proj_{\hat{e}}x. So we compute \begin{bmatrix}-1 \\ -4 \\ 6\end{bmatrix} - \frac{25}{14} \begin{bmatrix}1 \\ -2 \\ 3 \end{bmatrix}. We get \frac{1}{14} \begin{bmatrix}-39 \\ -6 \\ 9 \end{bmatrix}. This gives us \boxed{B. -22}.