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.
2010年1月25日 星期一
訂閱:
張貼留言 (Atom)
沒有留言:
張貼留言