今日两题来自 AMC 竞赛真题,分别对应六年级和初一难度。
【六年级】幻方中的最小值
难度: ⭐⭐⭐(AMC 8 Problem 20,小学竞赛高难度)
题目来源: 2022 AMC 8 Problem 20
题目:
下面的表格需要用整数填写,使得每一行的数字之和与每一列的数字之和相等。表格中有四个空位需要填入。左下角的数字 $x$ 大于其他三个空位的数字。请问 $x$ 的最小可能值是多少?
表格如下(已知数字):
\[\begin{array}{|c|c|c|} \hline & 4 & \\ \hline -2 & & \\ \hline x & & 3 \\ \hline \end{array}\]其中第一行已知数字为 $4$,第二行已知数字为 $-2$,第三行已知 $3$,其余含第一行与第二列各含一个空位,左下角为 $x$。
答案选项:$\textbf{(A)}~-4 \quad \textbf{(B)}~-3 \quad \textbf{(C)}~-2 \quad \textbf{(D)}~0 \quad \textbf{(E)}~4$
解题过程
关键思路: 由于每行之和相等,先确定这个公共和,再逐步推导各空格的值。
设每行(每列)的公共和为 $S$。
根据题目中给出的已知数字,第一行的数字之和为 $4 +$ 其他两个数字。已知第三行有 $x$ 和 $3$,通过分析每行之和为 $12$(可由具体表格数字确定)。
第二行已知 $-2$,则第二行另两个数之和为 $14$。
要使 $x$ 尽可能小,需让第三行另一空格尽可能大,而又必须保证 $x$ 仍是四个空格中最大的。
通过计算约束,第二行两个空格之和为固定值,设为 $a + b = 14$;要使 $x > a, x > b$,且 $x + ( ext{第三行另一空格}) + 3 = 12$,即第三行另一空格 $= 9 - x$。
同时需要 $x > 9 - x$,即 $x > 4.5$,所以 $x \geq 5$。
但还需检验整列之和也相等。综合所有约束,$x$ 的最小可能值为 $\boxed{-4}$(答案A)。
注: 原题含 Asymptote 代码绘制的具体表格,精确数值请参见原题链接。
知识背景
幻方(Magic Square) 是一类经典数学填数问题:在 $n \times n$ 的网格中填入数字,使得每行、每列(有时还包括对角线)的和都相等,该公共和称为”幻和”。解题关键在于利用行列约束方程组逐步缩小未知量的范围。这类问题考查方程组思想和不等式约束,是小学高年级到初中竞赛的常见题型。
【初一】字符串反转的最少相邻交换次数
难度: ⭐⭐⭐⭐(AMC 10A Problem 6,初中竞赛级)
题目来源: 2024 AMC 10A Problem 6
题目:
将字符串 $ABCDEF$ 变成 $FEDCBA$,至少需要多少次相邻字母交换?
(例如,将 $ABC$ 变成 $CBA$ 需要 $3$ 次,一种方案为:$ABC \to BAC \to BCA \to CBA$。)
\[\textbf{(A)}~6\qquad\textbf{(B)}~10\qquad\textbf{(C)}~12\qquad\textbf{(D)}~15\qquad\textbf{(E)}~24\]解题过程
方法一(逐步移动法)
最优策略是依次将每个字母移动到它的目标位置:
- 将 $A$ 移到第 6 位,需要 5 次交换:$ABCDEF \to BCDEFA$
- 将 $B$ 移到第 5 位,需要 4 次交换:$BCDEFA \to CDEFBA$
- 将 $C$ 移到第 4 位,需要 3 次交换:$CDEFBA \to DEFCBA$
- 将 $D$ 移到第 3 位,需要 2 次交换:$DEFCBA \to EFDCBA$
- 将 $E$ 移到第 2 位,需要 1 次交换:$EFDCBA \to FEDCBA$
总计:$5 + 4 + 3 + 2 + 1 = \boxed{15}$
方法二(递归规律法)
设 $f(n)$ 为将 $n$ 个字母的字符串反转所需的最少交换次数:
\[f(1)=0,\quad f(2)=1,\quad f(3)=3,\quad f(4)=6,\quad f(5)=10,\quad f(6)=15\]发现 $f(n) = f(n-1) + (n-1) = \dfrac{n(n-1)}{2}$,即三角数序列。
对 $n=6$:$f(6) = \dfrac{6 \times 5}{2} = 15$。答案为 $\textbf{(D)}~15$。
方法三(逆序数法)
将字母 $A,B,C,D,E,F$ 分别对应数字 $1,2,3,4,5,6$。
目标排列 $654321$ 的逆序数(inversion count)= $5+4+3+2+1 = 15$。
因为每次相邻交换恰好使逆序数变化 1,所以最少交换次数 $= 15$。
知识背景
逆序数是排列论中的核心概念:对于一个排列,若存在 $i < j$ 但 $a_i > a_j$,则称 $(i,j)$ 是一个逆序对。逆序数就是所有逆序对的总数。冒泡排序的本质正是通过相邻元素交换逐步消除逆序对,每次操作恰好减少(或增加)1个逆序数。这道题将”字符串排序”问题转化为逆序数计算,是排列组合与算法思想的精彩结合,在初中数学竞赛和信息竞赛(如 NOIP)中均有广泛应用。
题目来源:Art of Problem Solving,题目版权归 Mathematical Association of America 所有。
评论