作业帮有n支球队进行比赛,每两个队都赛一场,胜队得3分,负队得0分.平局各得1分.问一个队至少要得多少分,才能保证得分不少于该队（该队除外）的至多有k－1支球队,其中n,k都是给定的整数,且2≤k≤
来源：学生作业帮助网 编辑：作业帮 时间：2024/04/27 23:12:14
有n支球队进行比赛,每两个队都赛一场,胜队得3分,负队得0分.平局各得1分.问一个队至少要得多少分,才能保证得分不少于该队（该队除外）的至多有k－1支球队,其中n,k都是给定的整数,且2≤k≤
有n支球队进行比赛,每两个队都赛一场,胜队得3分,负队得0分.平局各得1分.问一个队至少要得多少分,才能保证得分不少于该队（该队除外）的至多有k－1支球队,其中n,k都是给定的整数,且2≤k≤n－1
有n支球队进行比赛,每两个队都赛一场,胜队得3分,负队得0分.平局各得1分.问一个队至少要得多少分,才能保证得分不少于该队（该队除外）的至多有k－1支球队,其中n,k都是给定的整数,且2≤k≤
我做出的答案是：
当k是偶数时,须得分：3n-3k/2-2；
当k是奇数时,须得分：3n-3k/2-5/2；
解法如下（构造性证明）：
1、问题等价于：求积分榜上,排第k+1位的队得分最多可以得多少.理由是：如果求出该值,那么某队得分超过它,即可保证任何情况下,都不会多于k-1个队超过该队.反之,若某队得分小于或者等于该值,那么刚刚的这种积分榜,即可否决之.
2、问题进一步等价于：积分榜上的前k+1队,得分最少者可以最多得多少分.
3、现在我们构造出一种情况,使得2成立,如图一所示.此时,计算得分即可得答案：k为偶数时,第k+1队,胜了（k+1-1）/2+(n-k-1)场,故得分为3n-3k/2-3,所以某队只要多平一场就可满足题意,于是答案：3n-3k/2-2.同理,k为奇数时,可得3[(k+1-2)/2+(n-k-1)]+1*1+1=3n-3k/2-5/2.
4、证明任何一种情况下,第k+1位得分都不会超过上述值.
前k+1队都虐了后面的n-k-1队,已达到最值.反之,若前k+1队中,有队输给后面的,那么第k+1位的得分将会小于我们的答案.
当k为偶数时,前k+1队中相互之间可以产生的胜场数最多是：(k+1)k/2,而构造中相互间的胜场数恰好达到(k+1)k/2,若其中某队多赢了一局,那么必有一队少赢一局,此时,第k+1位的得分将会小于我们的答案.
当k为奇数时,构造中相互间的胜场数(k+1)（k+1-2）/2,平场数为k+1,若将某一平局换成胜负局,那么输队得分减少,此时,第k+1位的得分将会小于我们的答案.
综上所述,命题成立.（由于不易书写,4中证明似有不妥）