Question

在一个有 $5$ 行 $N$ 列的长方形点阵中，点从最上面一行开始，按从左到右的顺序逐行连续编号。因此最上面一行编号为 $1$ 到 $N$ ，第二行编号为 $N + 1$ 到 $2N$ ，依此类推。选取五个点 $P_1$ 、 $P_2$ 、 $P_3$ 、 $P_4$ 、 $P_5$ ，使得每个 $P_i$ 位于第 $i$ 行。令 $x_i$ 为点 $P_i$ 对应的编号。现在改为从第一列开始，按从上到下的顺序逐列连续编号。令 $y_i$ 为重新编号后点 $P_i$ 对应的编号。

已知 $x_1 = y_2$ 、 $x_2 = y_1$ 、 $x_3 = y_4$ 、 $x_4 = y_5$ 、 $x_5 = y_3$ 求 $N$ 的最小可能值。

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.$

答案

答案：149

知识点：方程组模运算

难度评级：2990

解答：

设 $P_i$ 位于第 $c_i$ 列。则 $x_i = (i-1)N + c_i$ ，且 $y_i = 5(c_i - 1) + i$ 。五个条件变为 $\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}$

将 $c_1 = 5c_2 - 3$ 代入第二个方程，得 $N = 24c_2 - 19$ 。从后三个方程消去 $c_3$ 和 $c_4$ ，得到 $124 c_5 = 89N + 7$ 。再代入 $N = 24c_2 - 19$ 并化简，即 $31 \mid 534 c_2 - 421$ ，也就是 $7 c_2 \equiv 18 \pmod{31}$ 。其最小正整数解为 $c_2 = 7$ 。

于是 $N = 24 \cdot 7 - 19 = 149$ 。回代可得有效列号 $(c_1, \ldots, c_5)=$ 都不超过 $149$ 。所以 $N$ 的最小可能值为 $149$ 。 $(32, 7, 141, 88, 107)$ ， $(x_1,y_2)=(32,32)$ ， $(x_2,y_1)=(156,156)$ ， $(x_3,y_4)=(439,439)$ ， $(x_4,y_5)=(535,535)$ ， $(x_5,y_3)=(703,703)$ 。

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 第 11 题

答案：149

难度评级：2990

解答：

其他年份的第 11 题