2010年1月25日 星期一

Nice Example on Schutte Problem

Some background first. A tournament of N players mean a competition that every pair of players play against each other exactly once. In our case, no draw is allowed; either one wins or the other wins.

A tournament is with Schutte property of order k if every set of k players are all defeated by one of the other players.

Using probabilistic method, it is easy to show that for any k, there exists sufficiently large N such that a tournament with Schutte property of order k is possible.

My focus here is a cute example of tournament with Schutte property of order 2: when N=7, name the players by 0,1,2,...,6, then a tournament with Schutte property of order 2 is given by:

i defeats j if and only if (i-j) is a quadratic residue of 7.

沒有留言: