一道 6-7 年级奥数题

[zungmou]

小智在镇上四处抓宝可梦。每天，他可以向他的收藏中添加 3 只、4 只或 5 只宝可梦，但他不能在连续的两天内添加相同数量的宝可梦。要让他恰好收集到 100 只宝可梦，最少需要多少天？

[intoext]

54545454…… 这样不行么？

[intoext]

到 90 的时候还有 10 ，那就……343

[Sawyerhou]

72+24+4
23 天？

[sweetcola]

5, 4, 3 两两组合得出 9, 8, 7
9 * 10 + 7 + 3 = 100 得出 23 天
5 和 4 循环刚好超出 100 也是最少也要 23 天（这能算证明吗- -）

[DeWjjj]

54 肯定会是最快的，54 超过 100 是 23 天。
那么 345 组合最好也就是 23 天。因为本质是 54 方式通过减少某次加法变成 3 。

[cxwave]

上面回复全是错的，我是数学爱好者。注意审题，“恰好收集到 100 只宝可梦”，回复不能贴公式，直接穷举序列 3+4+5 到=96 ，是 24 天，然后在加 4 ，就是 25 。这个序列排序方式是唯一“恰好 100 只的序列”，所以最少 25 天。

[Aaarnold]

@cxwave 54545454545454545454343 ，这个是几天呢

[cloudzhou]

@Aaarnold
@intoext
虽然看起来是对的，但是如怎么证明对的呢？如果不是 100 而是 101 呢？就是任意的 x y z 以及结果 N

[cloudzhou]

@sweetcola 你这个用两两组合非常有意思，思路新颖

[cxwave]

@Aaarnold 你说得对，两种答案不能同时都是正确的，因为它们给出的天数不同。我们需要仔细核查和澄清哪种方法是正确的。

1. **数字序列 `54545454545454545454343`**：
- 这个序列包含 23 天。
- 每天添加的宝可梦数量是 5 、4 、5 、4 、5 、4 、5 、4 、5 、4 、5 、4 、5 、4 、5 、4 、5 、4 、5 、4 、3 、4 、3 。
- 总数是 100 只宝可梦。
- 符合每天添加的数量为 3 、4 或 5 只宝可梦且不连续两天相同。

2. **动态规划解法**：
- 动态规划计算的结果是最少需要 25 天。

显然，23 天和 25 天不能同时是最少天数。因此，我们需要验证哪种方法给出的答案是正确的。

### 验证数字序列方法

我们可以简单地通过手工计算验证数字序列是否满足条件：

- 序列：`54545454545454545454343`
- 长度：23 天
- 每天添加的数量均为 3 、4 或 5 。
- 没有连续两天添加相同的数量。
- 总数：5 + 4 + 5 + 4 + 5 + 4 + 5 + 4 + 5 + 4 + 5 + 4 + 5 + 4 + 5 + 4 + 5 + 4 + 5 + 4 + 3 + 4 + 3 = 100 。

### 验证动态规划解法

重新审视动态规划解法的代码和逻辑：

```
### 结论

经过验证：

- 序列 `54545454545454545454343` 确实在 23 天内满足条件。
- 动态规划解法得出的 25 天也是正确的，但不是最优解。

因此，**正确的最少天数是 23 天**

[cxwave]

一开始我的直觉也想的 54 ，不过呢我的错误是复杂化了，我想出题人不可能把题目出的这么简单。结果他就是这么简单，gpt 看样子还是蠢的。

[geelaw]

证明：设 S=x(1)+…+x(n) 则
2S = x(1)+x(n) + (x(1)+x(2)) + (x(2)+x(3)) + … + (x(n-1)+x(n)) <= x(1)+x(n) + 9(n-1) <= 10+9(n-1)
于是 n >= (2*100-10)/9+1 = 22.(1) 于是 n >= 23 。

注意到 (5+4)*10+3+4+3 = 100 且正好是 23 个来自 {3,4,5} 的相邻不同的加数。

[geelaw]

@cxwave #10 我无法想象怎么动态规划能得到 25 天的答案，请不要相信 LLM 生成的胡言乱语。提示：令 f(n,m) 为和为 n 且最后一个加数是 m 时最少需要的加数个数。

[Tink]

@cxwave #6 请不要直接贴 gpt 的回复

[zapper]

@cxwave #10 https://v2ex.com/about 请不要把 AI 生成的内容发送到这里

[yuhr123]

Llama3 70B：

这是一个有趣的问题！😊

让我们分析一下小智每天可以添加的宝可梦数量：

* 3 只、4 只或 5 只

我们可以尝试找到一个模式，使小智恰好收集到 100 只宝可梦。

首先，我们可以找到一个循环模式，使小智每天添加的宝可梦数量不同：

Day 1: +3
Day 2: +4
Day 3: +5
Day 4: +3
Day 5: +4
...

这个循环模式可以重复，直到小智收集到 100 只宝可梦。

现在，让我们计算小智需要多少天来收集 100 只宝可梦：

3 + 4 + 5 = 12
12 × 8 = 96
还差 4 只，所以下一天小智需要添加 4 只宝可梦。

因此，小智至少需要 25 天来收集 100 只宝可梦。

Deepseek-v2 Q4:

首先，我们需要考虑小智每天捕捉宝可梦的可能性。由于他不能在连续的两天内捕捉相同数量的宝可梦，我们可以将这个问题分为几个部分来解决：

- **如果小智每天都捕捉 3 只宝可梦**，那么他需要的天数是 100/3=33.33 天（向上取整到最接近的整数）。这意味着他至少需要 34 天才能捕捉到 100 只宝可梦。

- **如果小智每天都捕捉 4 只宝可梦**，那么他需要的天数是 100/4=25 天。在这种情况下，他不需要 34 天。

- **如果小智每天都捕捉 5 只宝可梦**，由于这个数量超过了每天可能的捕捉上限（最多 4 只），因此这种情况不可行。

现在，我们需要计算哪种情况最少需要的天数。显然，每天捕捉 4 只宝可梦的情况所需的天数最少，因为它少于 34 天。所以：

- 小智至少需要 25 天才能捕捉到 100 只宝可梦。

[cxwave]

@geelaw 正确的

[Aaarnold]

@cxwave 倒是也不用吧 ai 生成的内容粘贴出来回复我，我需要我会自己去问 ai 的

[Aaarnold]

@cloudzhou 我没有在证明 23 是对的，我只是在回复我回复的楼主，对他的答案提出一个反例罢了，简而言之就是单纯杠一下😂

[workingpad2]

这能是奥数题？奥数里面送分的吧..

[itskingname]

这不就是算法里面经典的上楼梯问题吗？每步可以上 3 、4 或 5 级台阶，要上 100 级台阶最少要走几步。倒着算就好了。

[mpfeitech7416]

private static int minDaysToCollect100Pokemons() {
int[][] dp = new int[101][6];
for (int[] row : dp) {
Arrays.fill(row, INF);
}

// 初始化状态
dp[0][3] = dp[0][4] = dp[0][5] = 0;

// 填充 DP 表
for (int i = 0; i <= 100; i++) {
for (int last : new int[]{3, 4, 5}) {
if (dp[i][last] != INF) {
if (i + 3 <= 100 && last != 3) {
dp[i + 3][3] = Math.min(dp[i + 3][3], dp[i][last] + 1);
}
if (i + 4 <= 100 && last != 4) {
dp[i + 4][4] = Math.min(dp[i + 4][4], dp[i][last] + 1);
}
if (i + 5 <= 100 && last != 5) {
dp[i + 5][5] = Math.min(dp[i + 5][5], dp[i][last] + 1);
}
}
}
}
return Math.min(dp[100][3], Math.min(dp[100][4], dp[100][5]));
}

[BeforeTooLate]

@cxwave #6 哈哈，你得思路清奇，建议再想想。

[BeforeTooLate]

@workingpad2 小学奥数啊，你小学得时候看到题目不一定觉得简单

[yishengyongyi]

难道不是 23 么

[cloudzhou]

做了一个小尝试，贪心加回溯：

https://gist.github.com/cloudzhou/a839ba0943bb3e9c65997695a88ef865