T0D0

Chicken McNugget theorem 鸡块定理 Frobenius Coin Problem弗罗贝尼乌斯硬币问题[C Done]

作者：

radmin

在

chicken mcnugget theorem

弗罗贝尼乌斯数基础定义

给定若干正整数硬币面值，能精确凑出的金额 = 面值的非负整数线性组合；

满足两个前提：

  1. 若所有面值的最大公约数 \(\gcd>1\)：有无穷多金额无法凑出，不存在 “最大不能凑出的数”；
  2. 若 \(\gcd=1\)：仅有有限个金额无法凑出，其中最大的那个数字叫做弗罗贝尼乌斯数

仅 2 个互质面值：有通用公式。设两数 \(a,b\) 互质，最大不可表示数为 \(ab-a-b\)；

3 个及以上互质面值：没有通用代数计算公式，只能用「同余分类法」或「筛法动态规划」枚举寻找答案。

Q1 2023 AMC 12B Problems/Problem 16

In the state of Coinland, coins have values $6,10,$ and $15$ cents. Suppose $x$ is the value in cents of the most expensive item in Coinland that cannot be purchased using these coins with exact change. What is the sum of the digits of $x?$

$\textbf{(A) }8\qquad\textbf{(B) }10\qquad\textbf{(C) }7\qquad\textbf{(D) }11\qquad\textbf{(E) }9$

Q2 2015 AMC 10B Problems/Problem 15

The town of Hamlet has $3$ people for each horse, $4$ sheep for each cow, and $3$ ducks for each person. Which of the following could not possibly be the total number of people, horses, sheep, cows, and ducks in Hamlet?

$\textbf{(A) }41\qquad\textbf{(B) }47\qquad\textbf{(C) }59\qquad\textbf{(D) }61\qquad\textbf{(E) }66$

Q3 2019 AIME II Problems/Problem 14

Find the sum of all positive integers $n$ such that, given an unlimited supply of stamps of denominations $5,n,$ and $n+1$ cents, $91$ cents is the greatest postage that cannot be formed.

Q4 1994 AIME Problems/Problem 11

Ninety-four bricks, each measuring $4''\times10''\times19'',$ are to be stacked one on top of another to form a tower 94 bricks tall. Each brick can be oriented so it contributes $4''\,$ or $10''\,$ or $19''\,$ to the total height of the tower. How many different tower heights can be achieved using all of the ninety-four bricks?

Q5 1995 AIME Problems/Problem 10

What is the largest positive integer that is not the sum of a positive integral multiple of $42$ and a positive composite integer?

Q6 1984 AIME Problems/Problem 14

What is the largest even integer that cannot be written as the sum of two odd composite numbers?

Q7 2022 AIME II Problems/Problem 14

For positive integers $a$, $b$, and $c$ with $a < b < c$, consider collections of postage stamps in denominations $a$, $b$, and $c$ cents that contain at least one stamp of each denomination. If there exists such a collection that contains sub-collections worth every whole number of cents up to $1000$ cents, let $f(a, b, c)$ be the minimum number of stamps in such a collection. Find the sum of the three least values of $c$ such that $f(a, b, c) = 97$ for some choice of $a$ and $b$.

Q1

一、整体定性：这份解答就是三元硬币问题标准解法 ——模最小面值剩余分类法

这是处理 3 个及以上面值弗罗贝尼乌斯数的通用套路，完全契合这道 6、10、15 分硬币题，下面分层拆解每一处逻辑、表格、计算原理。

核心底层原理（先读懂这个，全程通透）

硬币面值：6（最小）、10、15。

任意金额 k 除以 6 只会产生 6 种余数：\(0,1,2,3,4,5\)。

关键性质：

如果某个金额 M 能被凑出，那么 \(M+6、M+12、M+18……\) 全部都能凑出，只需要额外增加对应数量的 6 分硬币。

推论：

对任意一个余数 r（比如余 5），找到能凑出的最小数字 \(m_r\) 满足 \(m_r \equiv r \pmod6\)；

那么所有大于 \(m_r\)、同余 r 的数都能凑，这个余数类别里最大凑不出的数 = \(m_r – 6\)。

我们把 6 个余数类别各自最大凑不出的数字全部算出来，其中数值最大的那个，就是全局最大无法凑出的金额 x。

二、解析文中的模 6 对照表

先计算每个面值模 6 的余数： \(\begin{align*} 6 \pmod6 &= 0 \\ 10 \pmod6 &= 4 \\ 15 \pmod6 &= 3 \end{align*}\)

表格含义：只用 1 枚硬币、2 枚 10 分硬币时的模 6 余数

  • 1 枚硬币：6 余 0，10 余 4，15 余 3
  • 2 枚 10 分：\(10\times2=20,\ 20\pmod6=2\)

这张表是快速拼凑目标余数的工具：只用 10、15 组合，搭配出余数 0~5。

三、逐类拆解 6 个剩余类的完整推理

1. 余数 \(0 \pmod6\)

数字：6,12,18,24……

直接只用 6 分硬币即可凑出，这个余数类不存在凑不出的数字，无需记录。

2. 余数 \(1 \pmod6\)

目标：用若干 10、15 凑出一个数，除以 6 余 1。

试 \(b=1\)（1 个 10 分），\(c=1\)（1 个 15 分）：

总和 \(10+15=25\)，\(25\div6=4\cdots\cdots1\)，满足 \(25\equiv1\pmod6\)。

25 是这个余数下最小可凑数。

该余数类最大无法凑出数：\(25-6=19\)。

含义：所有大于 19、除以 6 余 1 的数（31,37,43…）都能凑；1,7,13,19 无法凑。

3. 余数 \(2 \pmod6\)

目标：凑出除以 6 余 2 的最小数。

2 枚 10 分：\(10\times2=20\)，\(20\equiv2\pmod6\)。

最小可凑数 \(m_r=20\)。

该余数类最大无法凑出数：\(20-6=14\)。

4. 余数 \(3 \pmod6\)

目标：凑出除以 6 余 3 的最小数。

1 枚 15 分：\(15\equiv3\pmod6\)。

最小可凑数 \(m_r=15\)。

该余数类最大无法凑出数：\(15-6=9\)。

5. 余数 \(4 \pmod6\)

目标：凑出除以 6 余 4 的最小数。

1 枚 10 分：\(10\equiv4\pmod6\)。

最小可凑数 \(m_r=10\)。

该余数类最大无法凑出数：\(10-6=4\)。

6. 余数 \(5 \pmod6\)

目标：凑出除以 6 余 5 的最小数。

2 枚 10 分 + 1 枚 15 分：\(10\times2+15=35\)，\(35\div6=5\cdots\cdots5\)，\(35\equiv5\pmod6\)。

最小可凑数 \(m_r=35\)。

该余数类最大无法凑出数：\(35-6=29\)。

四、汇总所有余数类的 “最大不可凑数”

余 1：19；余 2：14；余 3：9；余 4：4；余 5：29

这一组数字里最大值是 \(\boldsymbol{29}\)，也就是题目所求 \(x=29\)。

五、最后一步：求数字之和

\(2+9=11\)

对应选项 \(\textbf{D}\)。

六、补充验证（检验解法正确性）

  1. 证明 29 确实无法凑出：方程 \(6a+10b+15c=29\)
  • \(c=0\)：\(6a+10b=29\)，左边偶数，右边奇数，无解；
  • \(c=1\)：\(6a+10b=14 \Rightarrow 3a+5b=7\)，无自然数解；
  • \(c\ge2\)：\(15\times2=30>29\)，不用讨论；因此 29 完全无法凑出。
  1. 证明 30 及以上全部可以凑出：30 (余 0)、31 (余 1)、32 (余 2)、33 (余 3)、34 (余 4)、35 (余 5)，6 个连续整数全部可凑。根据核心性质，每个数字加 6 依然可凑，因此所有≥30 的金额都能精确兑换，29 是最大无法兑换的金额。

七、方法总结

  1. 适用场景：3 种及以上互质面值硬币（无通用代数公式）；
  2. 操作步骤：① 选取最小面值作为模数，划分全部余数类别；② 对每个余数，找到仅用其他面值组合出的最小同余数；③ 每个余数类最大不可凑数 = 最小同余数 − 模数；④ 取所有余数类结果的最大值，就是弗罗贝尼乌斯数；
  3. 考察知识点：不定方程、模运算、弗罗贝尼乌斯硬币问题。

Q2 B47

Q3 71

Q4 465

Q5 215

Q6 038

Q7 188

Q8

评论

One response to “Chicken McNugget theorem 鸡块定理 Frobenius Coin Problem弗罗贝尼乌斯硬币问题[C Done]”

  1. radmin Avatar
    radmin

    Q7做了一个小时，很慢，但好歹算出来了😄

Leave a Reply

更多文章