2024 AMC 10A 第 6 题

Question

将字符串 ABCDEF 变成 FEDCBA，最少需要多少次连续交换相邻字母？

例如，将 ABC 变成 CBA 需要

3

次交换；一种交换序列是 ABC

\to

BAC

\to

BCA

\to

CBA。

What is the minimum number of successive swaps of adjacent letters in the string ABCDEF that are needed to change the string to FEDCBA?

(For example,

3

swaps are required to change ABC to CBA; one such sequence of swaps is ABC

\to

BAC

\to

BCA

\to

CBA.)

6

10

12

15

24

每次相邻交换只改变一对字母的相对顺序。

Each adjacent swap changes the relative order of exactly one pair of letters

完全反转后，每一对字母的相对顺序都颠倒；数一数

\binom{6}{2}

对。

In the fully reversed string every pair of letters is out of order; count the pairs with

\binom{6}{2}

反转六个字母会颠倒每一对字母的相对顺序，所以共有

\binom{6}{2} = 15

对字母变成逆序。每次相邻交换只改变一个逆序对数，所以至少需要

15

次。逐个把字母冒泡到正确位置可以正好用

15

次完成，因此这个下界可以达到，正确答案是 D。

Reversing all six letters flips the relative order of every pair, so all

\binom{6}{2} = 15

pairs end up inverted. Each adjacent swap fixes exactly one inversion. So we need at least

15

swaps, and bubbling each letter into place hits

15

exactly. Therefore, the answer is D.

其他年份的第 6 题