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

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 $c_1 = 5c_2 - 3, \quad N + c_2 = 5c_1 - 4, \quad 2N + c_3 = 5c_4 - 1,$ $3N + c_4 = 5c_5, \quad 4N + c_5 = 5c_3 - 2.$

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, 107, 45, 86),$ all at most $149.$ So the smallest possible $N$ is $149.$

2001 AIME I Problem 11

Solution:

Problem 11 in Other Years