PUMaC 2009 · 组合（B 组） · 第 6 题

PUMaC 2009 — Combinatorics (Division B) — Problem 6

There are n players in a round-robin ping-pong tournament (i.e. every two persons will play exactly one game). After some matches have been played, it is known that the total number k of matches that have been played among any n − 2 people is equal to 3 (where k is a fixed integer). Find the sum of all possible values of n .

解析

There are n players in a round-robin ping-pong tournament (i.e. every two persons will play exactly one game). After some matches have been played, it is known that the total number k of matches that have been played among any n − 2 people is equal to 3 (where k is a fixed integer). Find the sum of all possible values of n . Solution. 9. We make a graph with the verticies as the players, and the edges are the matches. n k k × 3 ( ) n − 2 12 ∗ 3 The total number of edges is = . Since this number must be larger than n ( n − 2)( n − 3) ( ) n − 4 k 12 3 , we have is an integer greater than 1. Furthermore, n ≥ 4. So only possibilities ( n − 2)( n − 3) for n are 4 and 5. Easy to check that n = 4, k = 0 and n = 5; k = 1 are two complete graphs satisfying the condition. So n = 4 or 5, and 9 is the answer.