2000 AIME I 第 15 题

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

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

15.

一叠 20002000 张卡片分别标有 1120002000,每张卡片标号不同,原始顺序不是数字顺序。 先取走顶端卡片放到桌上,再把下一张卡片移到底部。然后再取走新的顶端卡片,放在桌上已有卡片的右侧, 再把下一张卡片移到底部。这个过程一直重复,直到所有卡片都放到桌上。结果从左到右读出卡片标号恰为升序 1,2,3,,1999,20001, 2, 3, \ldots, 1999, 2000。在原始卡堆中,标号为 19991999 的卡片上方有多少张卡片?

A stack of 20002000 cards is labelled with the integers from 11 to 2000,2000, with different integers on different cards. The cards in the stack are not in numerical order. The top card is removed from the stack and placed on the table, and the next card is moved to the bottom of the stack. The new top card is removed from the stack and placed on the table, to the right of the card already there, and the next card in the stack is moved to the bottom of the stack. The process — placing the top card to the right of the cards already on the table and moving the next card in the stack to the bottom of the stack — is repeated until all cards are on the table. It is found that, reading from left to right, the labels on the cards are now in ascending order: 1,2,3,,1999,2000.1, 2, 3, \ldots, 1999, 2000. In the original stack of cards, how many cards were above the card labelled 1999?1999?

答案:927
知识点:排列过程模拟找规律
难度评级:3060
解答:

将原始位置编号为 11(顶端)到 20002000(底端),并把它们放入队列。每步取走队首位置 (得到下一个标号 1,2,3,1, 2, 3, \ldots),再把新的队首移到队尾。因此标号 19991999 的卡片是倒数第二张被取走的卡片, 我们要找其原始位置。

第一轮取走奇数位置 1,3,,19991, 3, \ldots, 1999,它们获得标号 1110001000。这一轮结束时将 20002000 移到队尾,所以下一轮仍从队列 2,4,,20002, 4, \ldots, 2000 的队首开始。后续各轮依次取走 2,6,,19982, 6, \ldots, 1998(即满足 2mod4\equiv 2 \bmod 4 的位置)、4,12,,19964, 12, \ldots, 19968,24,,19928, 24, \ldots, 1992,再取走 16,48,,1968,200016, 48, \ldots, 1968, 2000(共 6363 个满足 16mod32\equiv 16 \bmod 32 的位置)。该轮从奇数个 125125 张牌中交替取牌,所以队列的交替方向发生偏移;剩下的 62623232 的倍数在队列中按 64,96,,1984,3264, 96, \ldots, 1984, 32 排列。

继续同样的过程,接下来各轮依次取走 64,128,,198464, 128, \ldots, 198496,224,,1888,3296, 224, \ldots, 1888, 32288,544,,1824288, 544, \ldots, 1824160,672,1184,1696160, 672, 1184, 1696416,1440416, 1440。最后两张被取走的是 92892819521952。所以标号 19991999 位于原始位置 928928,其上方有 927927 张卡片。

Number the original positions 11 (top) through 20002000 (bottom) and put them in a queue. Each step removes the front position (which receives the next label 1,2,3,1, 2, 3, \ldots) and sends the new front to the back. So the card labelled 19991999 is the next-to-last card removed, and we must find which original position survives that long.

The first pass removes the odd positions 1,3,,19991, 3, \ldots, 1999 (labels 11 through 10001000) and, since it ends by sending 20002000 to the back, the next pass again starts by removing the front of the queue 2,4,,2000.2, 4, \ldots, 2000. Successive passes therefore remove 2,6,,19982, 6, \ldots, 1998 (the positions 2mod4\equiv 2 \bmod 4), then 4,12,,1996,4, 12, \ldots, 1996, then 8,24,,1992,8, 24, \ldots, 1992, then 16,48,,1968,200016, 48, \ldots, 1968, 2000 (the 6363 positions 16mod32\equiv 16 \bmod 32). That last pass ran through an odd number (125125) of cards, so the alternation shifts: the 6262 surviving multiples of 3232 now sit in the queue as 64,96,,1984,32.64, 96, \ldots, 1984, 32.

Continuing the same removal pattern from that queue, the next rounds remove 64,128,,1984;64, 128, \ldots, 1984; then 96,224,,1888,32;96, 224, \ldots, 1888, 32; then 288,544,,1824;288, 544, \ldots, 1824; then 160,672,1184,1696;160, 672, 1184, 1696; then 416,1440;416, 1440; and the final two cards removed are 928928 and 1952.1952. So label 19991999 goes to the card at original position 928,928, which had 927927 cards above it.

← 第 14 题#14
完整试卷

其他年份的第 15 题