# 2008 iTest Problems/Problem 51

## Problem

Alexis imagines a $2008 \times 2008$ grid of integers arranged sequentially in the following way: $$\begin{array}{r@{\hspace{20pt}}r@{\hspace{20pt}}r@{\hspace{20pt}}r@{\hspace{20pt}}r}1,&2,&3,&\ldots,&2008\\2009,&2010,&2011,&\ldots,&4026\\4017,&4018,&4019,&\ldots,&6024\\\vdots&&&&\vdots\\2008^2-2008+1,&2008^2-2008+2,&2008^2-2008+3,&\ldots,&2008^2\end{array}$$

She picks one number from each row so that no two numbers she picks are in the same column. She them proceeds to add them together and finds that $S$ is the sum. Next, she picks $2008$ of the numbers that are distinct from the $2008$ she picked the first time. Again she picks exactly one number from each row and column, and again the sum of all $2008$ numbers is $S$. Find the remainder when $S$ is divided by $2008$.

## Solution

Notice that all the numbers of the first column are congruent to $1$ modulo $2008$, all of the numbers in the second column are congruent to $2$ modulo $2008$, and so on. That means the sum of Alexis's numbers is congruent to $0+1+2+3+ \cdots 2007$ modulo $2008$. After calculating the sum and dividing by $2008$, we find that $S \equiv 1004 \pmod{2008}$, so the remainder when $S$ is divided by $2008$ is $\boxed{1004}$.