组合与概率 2025-09-04 含解答

2025年MEMO团体赛第1题及解答

程国根 · 微信公众号「恩次方根」

正文文字 274 字公式 53 处

上午刚看到的题，感谢赵力博士的翻译。第1题比较简单，很快就做出来了，顺手写一下。

题目：（2025年MEMO团体赛第1题）

Bob 有n枚硬币，其面值分别为正整数

c_(1)≥c_(2)≥⋯≥c_(n)>0.

他站在一台自动售货机前，售货机提供几种糖果，其价格分别为正整数b_(1),b_(2),⋯,b_(n)．Bob 注意到对于每个i∈{1,⋯,n}，都有

b_(1)+b_(2)+⋯+b_(i)≥c_(1)+c_(2)+⋯+c_(i).

此外，Bob的硬币总价值等于所有糖果成本的总和．糖果可以以任意顺序购买．为了购买第i种糖果，Bob必须插入总价值至少为b_(i)的硬币．然而，售货机不会找零．证明：Bob可以购买至少一半的糖果．

展开解答收起解答

解答：

将b_(1),b_(2),⋯,b_(n)排列为

a_(1)≥a_(2)≥⋯≥a_(n).

则∀1≤k≤n，

∑_(i=1)^(k)a_(k)≥∑_(i=1)^(k)b_(i)≥∑_(i=1)^(k)c_(i)

结合∑_(i=1)^(n)a_(i)=∑_(i=1)^(n)c_(i)知：∀1≤k≤n，∑_(i=k)^(n)c_(i)≥∑_(i=k)^(n)a_(i)．

取k=n得，c_(n)≥a_(n)．

若存在1≤j≤[(n)/(2)]，使得c_(n−2j)+c_(n−2j+1)<a_(n−j)，则

c_(n)≤c_(n−1)+c_(n−2)≤⋯≤c_(n−2j)+c_(n−2j+1);< a_(n−j)≤a_(n−j−1)≤⋯≤a_(n−2j);

于是

∑_(i=n−2j)^(n)c_(i)<∑_(i=n−2j)^(n−j)a_(i)<∑_(i=n−2j)^(n)a_(i)

矛盾！于是∀1≤j≤[(n)/(2)]，都有

c_(n−2j)+c_(n−2j+1)≥a_(n−j).

于是用面值为c_(n)的硬币可以买价格为a_(n)的糖果，用面值为c_(n−2j)和c_(n−2j+1)的硬币可以买价格为a_(n−j)的糖果（1≤j≤[(n)/(2)]）．

这样，用不同的硬币共可以买到价格为a_(n),a_(n−1),⋯,a_(n−[(n)/(2)])的糖果，总数为[(n)/(2)]+1>(n)/(2)．

在公众号查看原文 ↗ 反馈点公式可复制源码

留言

正常留言提交后可直接显示，无需人工审核；仍会经过防刷与垃圾内容过滤。请不要留下手机号等私人信息。解法、疑问都可以说；公式用 LaTeX：行内 $…$ ，整行 $$…$$。