25th CanMO 1993 Problem 4 Several schools took part in a tournament. Each player played one match against each player from a different school and did not play anyone from the same school. The total number of boys taking part differed from the total number of girls by 1. The total number of matches with both players of the same sex differed by at most one from the total number of matches with players of opposite sex. What is the largest number of schools that could have sent an odd number of players to the tournament? Solution
: 3. Let there be n schools. Suppose the ith school sends B i boys and G i girls. Let B = ∑ B i and G = ∑ G i . We are given that |B - G| = 1. The number of same sex matches is 1/2 ∑ B i (B - B i ) + 1/2 ∑ G i (G - G i ) = (B 2 - ∑ B i 2 + G 2 - ∑ G i 2 ). The number of opposite sex matches is ∑ B i (G - G i ) = BG - ∑ B i G i . Thus we are given that B 2 - ∑ B i 2 + G 2 - ∑ G i 2 - 2BG + 2 ∑ B i G i = 0 or ±2. Hence (B - G) 2 - ∑(B i - G i ) 2 = 0 or ±2. But (B - G) 2 = 1, so ∑(B i - G i ) 2 = -1, 1 or 3. It cannot be negative, so it must be 1 or 3. Hence B i = G i except for 1 or 3 values of i, where |B i - G i | = 1. Thus the largest number of schools that can have B i + G i odd is 3. 25th CanMO 1993 © John Scholes jscholes@kalva.demon.co.uk 18 Aug 2002