Checklist USA-NA-AIO 2025 Round 1 · Task 1
Linear Recurrences and Spectral Decomposition
Solve a Fibonacci-type recurrence through the spectral decomposition of its matrix and implement it in NumPy.
The task
Problem 1 (100 points, 10 parts) studies F_n = F_{n−1} + F_{n−2}. The contestant computes early terms for F_0 = 3, F_1 = 1, writes the recurrence with a 2×2 matrix A, explains its symmetry, proves that eigenvectors of distinct eigenvalues of a real symmetric matrix are orthogonal, computes the eigenvalues and spectral decomposition of A, derives a closed form for F_n and the limit of F_n/F_{n−1}, and implements a class My_Fib that computes and plots the sequence.
Abridged by SOTA from the official materials. The official statement has the exact rules, and it wins wherever this summary differs.
At a glance
- You submit
- Written answers and code in a notebook.
- Rules
- Only numpy and matplotlib; no other imports, even temporarily.
- All coding tasks run on CPU.
- Format
- 2025 USA-NA-AIO Round 1, 24 March 2025 (date from IOAI news article). Statements and official solutions were posted part by part on the USAAIO forum on 28 March 2025.