Question

【题目】奥运会排球预选赛有支球队参加，其中每两队比赛一场，每场比赛必决出胜负。如果其中有支球队满足：胜，胜，胜，胜，则称这支球队组成一个“阶连环套”。证明：若全部支球队组成一个 阶连环套，则对于每个及每支球队，必与另外某些球队组成一个阶连环套。

Answer 1

【答案】见解析

【解析】

以为顶点.如球队胜，则在两点间连一有向边：，如此得阶竞赛图.据条件，的个顶点可以排成一个阶有向圈，设为.则的任两点可沿箭头方向相互到达.

首先证明：任一球队必在某个三阶连环套中.

用分别表示被击败了的球队集合和击败了的所有球队集合.由于双向连通，必有，使得.于是，组成三阶连环套.

假若已证得，对于，图中存在以为一顶点的阶连环套，圈之外的点的集合为.

若中有一点，它所表示的球队既击败了圈中的某个队，又被圈中的另一个队 所击败，点把圈分成两条有向路，其中一条，例如它与有向路组成有向圈.

依次考虑路上各点与点间的邻接情况，必有相邻的两点满足，而.现去掉边，而将路插入其间，便得到一个含有顶点的阶连环套.

若中的任一点，它所表示的球队要么击败了圈中的每个队，要么被圈中的每个队所击败，则集合可分为两个不交的子集，其中，中的任一队战胜了圈中所有的队，而中的任一队负于圈中所有的队.由于图双向连通，故在集合中必有点 ，集合中有点，使得.在圈中任意去掉一个点，而用路代替，便得到一个含有顶点的阶连环套，故结论对于成立.

由归纳法，结论成立.