求ｋ的最小值

192557 · 发表于 2022-7-30 18:31:32

在正 2009边形的每个顶点处各放置了一个不超过 100的非负整数．给某两个相邻顶点处的数分别加 1称做对这两个相邻顶点的一次操作．对任意给定的两个相邻顶点至多可进行ｋ次操作．求ｋ的最小值使得一定可以将所有顶点处的数变成彼此全相等．
[1]李伟固.第35届俄罗斯数学奥林匹克(十年级)[J].中等数学,2009,No.192(12):30-32.

22568 · 发表于 2022-9-25 22:20:38

对于奇数边形,显然是有解的,且若将所有边次数同时增减固定数认为是同个解法,可以认为每个初态都有唯一解.
于是最优解必有至少一条边不操作.
记剩下的依次操作次数是A[1]...A[n-1](补充A0=An=0),计算所有相邻两数之和 (记为数列B[1...n]).
只须在这些和最大最小值不超过m的前提下令所有Ai和最大化.
将B按奇偶分两堆,两堆和都是所有Ai之和(记为S),但项数差1((n-1)/2和(n+1)/2).
两堆均值分别为2S/(n-1)和2S/(n+1),显然二者之差不能超过m,即S<=m(n-1)(n+1)/4.
显然能取到,对应Ai为 km,m, (k-1)m,2m, (k-2)m,3m, ..., 2m,(k-1)m, m,km, 其中k=(n-1)/2.
也就是说,原题中取两个相邻点为m,剩下的为0,就是最坏情况,至少需要m(n-1)(n+1)/4次.

191584 · 发表于 2022-7-30 19:03:07

百度了一下这题的解答我都没看明白，说实话奥赛数学题一般人是做不出来的，数学这玩意几乎是最吃天赋的学科了

*发表于 2022-7-30 19:09:38* | 来自小霸王手机 · 发表于 2022-7-30 19:09:38

如果有2007个数是70，其中有对相邻的数是69，刚好去对这个加一，。然后就成了？
补充:哦，是至多！至多的最小值
补充:忽然想到可以，99，1，99，1，99，1

84805 · 发表于 2022-7-30 19:13:35

话说每个顶点的非负整数是任意的吗？

*发表于 2022-7-30 19:15:27* | 来自小霸王手机 · 发表于 2022-7-30 19:15:27

98+98，等于196？？

[数学趣题] 求ｋ的最小值