Question

【題目】奧運(yùn)會(huì)排球預(yù)選賽有支球隊(duì)參加，其中每兩隊(duì)比賽一場，每場比賽必決出勝負(fù)。如果其中有支球隊(duì)滿足：勝，勝，勝，勝，則稱這支球隊(duì)組成一個(gè)“階連環(huán)套”。證明：若全部支球隊(duì)組成一個(gè) 階連環(huán)套，則對于每個(gè)及每支球隊(duì)，必與另外某些球隊(duì)組成一個(gè)階連環(huán)套。

Answer 1

【答案】見解析

【解析】

以為頂點(diǎn).如球隊(duì)勝，則在兩點(diǎn)間連一有向邊：，如此得階競賽圖.據(jù)條件，的個(gè)頂點(diǎn)可以排成一個(gè)階有向圈，設(shè)為.則的任兩點(diǎn)可沿箭頭方向相互到達(dá).

首先證明：任一球隊(duì)必在某個(gè)三階連環(huán)套中.

用分別表示被擊敗了的球隊(duì)集合和擊敗了的所有球隊(duì)集合.由于雙向連通，必有，使得.于是，組成三階連環(huán)套.

假若已證得，對于，圖中存在以為一頂點(diǎn)的階連環(huán)套，圈之外的點(diǎn)的集合為.

若中有一點(diǎn)，它所表示的球隊(duì)既擊敗了圈中的某個(gè)隊(duì)，又被圈中的另一個(gè)隊(duì) 所擊敗，點(diǎn)把圈分成兩條有向路，其中一條，例如它與有向路組成有向圈.

依次考慮路上各點(diǎn)與點(diǎn)間的鄰接情況，必有相鄰的兩點(diǎn)滿足，而.現(xiàn)去掉邊，而將路插入其間，便得到一個(gè)含有頂點(diǎn)的階連環(huán)套.

若中的任一點(diǎn)，它所表示的球隊(duì)要么擊敗了圈中的每個(gè)隊(duì)，要么被圈中的每個(gè)隊(duì)所擊敗，則集合可分為兩個(gè)不交的子集，其中，中的任一隊(duì)?wèi)?zhàn)勝了圈中所有的隊(duì)，而中的任一隊(duì)負(fù)于圈中所有的隊(duì).由于圖雙向連通，故在集合中必有點(diǎn) ，集合中有點(diǎn)，使得.在圈中任意去掉一個(gè)點(diǎn)，而用路代替，便得到一個(gè)含有頂點(diǎn)的階連環(huán)套，故結(jié)論對于成立.

由歸納法，結(jié)論成立.