2012 AIME I 第 15 题

先试着解答 2012 AIME I 第 15 题,然后核对你的答案与精心整理的解答,解答来自 LIVE by Po-Shen Loh。你也可以参加完整限时模拟考试、查看全部 2012 AIME I 解答,或核对答案

所有题目均经美国数学协会(MAA)官方合法授权使用。

15.

nn 位数学家围坐在一张有 nn 个座位的圆桌旁,座位按顺时针编号为 112233\ldotsnn。休息之后,他们再次围坐在桌旁。数学家们注意到存在一个正整数 aa,使得:

第一,对每个 kk,休息前坐在座位 kk 的数学家,休息后坐在座位 kaka 上(其中座位 i+ni + n 就是座位 ii);

第二,对任意一对数学家,休息后沿顺时针和逆时针两个方向数他们之间相隔的数学家人数,都不同于休息前这两个方向中的任一相隔人数。

求满足 1<n<10001 \lt n \lt 1000nn 可能取值的个数。

There are nn mathematicians seated around a circular table with nn seats numbered 1,1, 2,2, 3,3, ,\ldots, nn in clockwise order. After a break they again sit around the table. The mathematicians note that there is a positive integer aa such that

(1) for each k,k, the mathematician who was seated in seat kk before the break is seated in seat kaka after the break (where seat i+ni + n is seat ii);

(2) for every pair of mathematicians, the number of mathematicians sitting between them after the break, counting in both the clockwise and the counterclockwise directions, is different from either of the number of mathematicians sitting between them before the break.

Find the number of possible values of nn with 1<n<1000.1 \lt n \lt 1000.

答案:332
知识点:模运算最大公约数
难度评级:3370
解答:

第一条条件要求座位 a,2a,,naa, 2a, \ldots, na 在模 nn 下两两不同,这当且仅当 gcd(a,n)=1\gcd(a, n) = 1。对于第二条条件,休息前来自座位 iijj 的两位数学家的间隔数由 ±(ij)modn\pm(i - j) \bmod n 决定,休息后由 ±a(ij)modn\pm a(i - j) \bmod n 决定。因此要求对所有 iji \ne j 都有 a(ij)≢±(ij)(modn)a(i - j) \not\equiv \pm(i - j) \pmod{n}。等价地,对每个非零剩余 iji - j 都有 (a1)(ij)≢0(a - 1)(i - j) \not\equiv 0(a+1)(ij)≢0(modn)(a + 1)(i - j) \not\equiv 0 \pmod{n};这正好要求 a1a - 1a+1a + 1 也都与 nn 互质。

所以 nn 可行,当且仅当存在某个 aa 满足 gcd((a1)a(a+1),n)=1\gcd\big((a - 1)\,a\,(a + 1),\, n\big) = 1。任意三个连续整数都包含一个 22 的倍数和一个 33 的倍数,所以当 gcd(n,6)>1\gcd(n, 6) \gt 1 时,没有 aa 可行。反过来,若 gcd(n,6)=1\gcd(n, 6) = 1,则 a=3a = 3 可行,因为 234=242 \cdot 3 \cdot 4 = 24 只有素因子 2233

满足 1<n<10001 \lt n \lt 1000 的有效 nn 正是同余于 ±1(mod6)\pm 1 \pmod 6 的数,即 6k±16k \pm 1,其中 1k1661 \le k \le 166,共有 2166=3322 \cdot 166 = 332 个。

Condition (1) requires the seats a,2a,,naa, 2a, \ldots, na to be pairwise distinct modulo n,n, which happens if and only if gcd(a,n)=1.\gcd(a, n) = 1. For condition (2), the two mathematicians from seats ii and jj have gap counts before the break determined by ±(ij)modn\pm(i - j) \bmod n and after the break by ±a(ij)modn,\pm a(i - j) \bmod n, so the requirement is a(ij)≢±(ij)(modn)a(i - j) \not\equiv \pm(i - j) \pmod{n} for all ij.i \ne j. Equivalently, (a1)(ij)≢0(a - 1)(i - j) \not\equiv 0 and (a+1)(ij)≢0(modn)(a + 1)(i - j) \not\equiv 0 \pmod{n} for every nonzero residue ij,i - j, which holds exactly when a1a - 1 and a+1a + 1 are also relatively prime to n.n.

So nn is possible if and only if some aa satisfies gcd((a1)a(a+1),n)=1.\gcd\big((a - 1)\,a\,(a + 1),\, n\big) = 1. Any three consecutive integers include a multiple of 22 and a multiple of 3,3, so no aa works when gcd(n,6)>1.\gcd(n, 6) \gt 1. Conversely, if gcd(n,6)=1,\gcd(n, 6) = 1, then a=3a = 3 works, since 234=242 \cdot 3 \cdot 4 = 24 has only the prime factors 22 and 3.3.

The valid nn with 1<n<10001 \lt n \lt 1000 are those congruent to ±1(mod6),\pm 1 \pmod 6, namely 6k±16k \pm 1 for 1k166,1 \le k \le 166, and there are 2166=3322 \cdot 166 = 332 of them.

← 第 14 题#14
完整试卷

其他年份的第 15 题