有n支球队进行比赛,每两个队都赛一场,胜队得3分,负队得0分.平局各得1分.问一个队至少要得多少分,才能保证得分不少于该队(该队除外)的至多有k-1支球队,其中n,k都是给定的整数,且2≤k≤
来源:学生作业帮助网 编辑:作业帮 时间:2024/07/03 07:25:52
![有n支球队进行比赛,每两个队都赛一场,胜队得3分,负队得0分.平局各得1分.问一个队至少要得多少分,才能保证得分不少于该队(该队除外)的至多有k-1支球队,其中n,k都是给定的整数,且2≤k≤](/uploads/image/z/12414427-43-7.jpg?t=%E6%9C%89n%E6%94%AF%E7%90%83%E9%98%9F%E8%BF%9B%E8%A1%8C%E6%AF%94%E8%B5%9B%2C%E6%AF%8F%E4%B8%A4%E4%B8%AA%E9%98%9F%E9%83%BD%E8%B5%9B%E4%B8%80%E5%9C%BA%2C%E8%83%9C%E9%98%9F%E5%BE%973%E5%88%86%2C%E8%B4%9F%E9%98%9F%E5%BE%970%E5%88%86.%E5%B9%B3%E5%B1%80%E5%90%84%E5%BE%971%E5%88%86.%E9%97%AE%E4%B8%80%E4%B8%AA%E9%98%9F%E8%87%B3%E5%B0%91%E8%A6%81%E5%BE%97%E5%A4%9A%E5%B0%91%E5%88%86%2C%E6%89%8D%E8%83%BD%E4%BF%9D%E8%AF%81%E5%BE%97%E5%88%86%E4%B8%8D%E5%B0%91%E4%BA%8E%E8%AF%A5%E9%98%9F%EF%BC%88%E8%AF%A5%E9%98%9F%E9%99%A4%E5%A4%96%EF%BC%89%E7%9A%84%E8%87%B3%E5%A4%9A%E6%9C%89k%EF%BC%8D1%E6%94%AF%E7%90%83%E9%98%9F%2C%E5%85%B6%E4%B8%ADn%2Ck%E9%83%BD%E6%98%AF%E7%BB%99%E5%AE%9A%E7%9A%84%E6%95%B4%E6%95%B0%2C%E4%B8%942%E2%89%A4k%E2%89%A4)
有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中证明似有不妥)