Question

In a rectangular array of points, with $5$ rows and $N$ columns, the points are numbered consecutively from left to right beginning with the top row. Thus the top row is numbered $1$ through $N,$ the second row is numbered $N + 1$ through $2N,$ and so forth. Five points, $P_1,$ $P_2,$ $P_3,$ $P_4,$ and $P_5,$ are selected so that each $P_i$ is in row $i.$ Let $x_i$ be the number associated with $P_i.$ Now renumber the array consecutively from top to bottom, beginning with the first column. Let $y_i$ be the number associated with $P_i$ after renumbering.

It is found that $x_1 = y_2,$ $x_2 = y_1,$ $x_3 = y_4,$ $x_4 = y_5,$ and $x_5 = y_3.$ Find the smallest possible value of $N.$

Answer

Answer: 149

Concepts:system of equations modular arithmetic

Difficulty rating: 2990

Solution:

Let $P_i$ sit in column $c_i.$ Then $x_i = (i-1)N + c_i$ and $y_i = 5(c_i - 1) + i.$ The five conditions become $\begin{aligned} c_1 &= 5c_2 - 3, \\ N + c_2 &= 5c_1 - 4, \\ 2N + c_3 &= 5c_4 - 1, \end{aligned}$ $\begin{aligned} 3N + c_4 &= 5c_5, \\ 4N + c_5 &= 5c_3 - 2. \end{aligned}$

Substituting $c_1 = 5c_2 - 3$ into the second equation gives $N = 24c_2 - 19.$ Eliminating $c_3$ and $c_4$ from the last three equations yields $124 c_5 = 89N + 7.$ Substituting $N = 24c_2 - 19$ and reducing, $31 \mid 534 c_2 - 421,$ i.e. $7 c_2 \equiv 18 \pmod{31},$ whose smallest positive solution is $c_2 = 7.$

Then $N = 24 \cdot 7 - 19 = 149,$ and back-substituting gives valid columns $(c_1, \ldots, c_5)=$ $(32, 7, 141, 88, 107),$ all at most $149.$ Indeed the corresponding pairs are $(x_1,y_2)=(32,32),$ $(x_2,y_1)=(156,156),$ $(x_3,y_4)=(439,439),$ $(x_4,y_5)=(535,535),$ and $(x_5,y_3)=(703,703).$ So the smallest possible $N$ is $149.$

2001 AIME I Problem 11

Answer: 149

Difficulty rating: 2990

Solution:

Problem 11 in Other Years