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,&4016\\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}$.

See Also

2008 iTest (Problems)
Preceded by:
Problem 50
Followed by:
Problem 52
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100