Question

【題目】一次循環(huán)賽中有2n+1支參賽隊(duì)，其中每隊(duì)與其他隊(duì)均只進(jìn)行一場(chǎng)比賽，且比賽結(jié)果中沒(méi)有平局。若三支參賽隊(duì)A、B、C滿(mǎn)足：A擊敗B，B擊敗C，C擊敗A，則稱(chēng)它們形成一個(gè)“環(huán)形三元組”。求：

（1）環(huán)形三元組的最小可能數(shù)目；

（2）環(huán)形三元組的最大可能數(shù)目。

Answer 1

【答案】（1）0；（2）

【解析】

（1）最小值為0.

對(duì)于比賽中的兩支參賽隊(duì)，當(dāng)且僅當(dāng)i>j時(shí)，有擊敗，此時(shí)環(huán)形三元組數(shù)最小.

（2）任何三支參賽隊(duì)要么組成一個(gè)環(huán)形三元組，要么組成一個(gè)“支配型”三元組(即某隊(duì)擊敗了其余兩隊(duì)).設(shè)前者有c組，后者有d組.則

.

假設(shè)某隊(duì)擊敗支其他隊(duì).則獲勝組必在個(gè)支配型三元組中.

注意到，所有的比賽場(chǎng)次為

.

因此，.

由柯西不等式得

.

故

.

將所有參賽隊(duì)排列在一個(gè)圓周上，對(duì)每支參賽隊(duì)而言，在其順時(shí)針?lè)较虻膎支隊(duì)被它擊敗，在其逆時(shí)方向的n支隊(duì)均擊敗它時(shí)取到最大值.