题目内容

【题目】一次循环赛中有2n+1支参赛队,其中每队与其他队均只进行一场比赛,且比赛结果中没有平局。若三支参赛队A、B、C满足:A击败B,B击败C,C击败A,则称它们形成一个“环形三元组”。求:

(1)环形三元组的最小可能数目;

(2)环形三元组的最大可能数目。

【答案】(1)0;(2)

【解析】

(1)最小值为0.

对于比赛中的两支参赛队,当且仅当i>j时,有击败此时环形三元组数最小.

(2)任何三支参赛队要么组成一个环形三元组,要么组成一个“支配型”三元组(即某队击败了其余两队).设前者有c组,后者有d组.则

.

假设某队击败支其他队.则获胜组必在个支配型三元组中.

注意到,所有的比赛场次为

.

因此,.

由柯西不等式得

.

.

将所有参赛队排列在一个圆周上,对每支参赛队而言,在其顺时针方向的n支队被它击败,在其逆时方向的n支队均击败它时取到最大值.

练习册系列答案
相关题目

违法和不良信息举报电话:027-86699610 举报邮箱:58377363@163.com

精英家教网