Track / Stage 5 / 336 of 400 #936 of 1964

Problem 936

AIME late

Combinatorics Difficulty 5.8 Prove it

18th USAMO 1989 Problem 2 In a tournament between 20 players, there are 14 games (each between two players). Each player is in at least one game. Show that we can find 6 games involving 12 different players.

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official solution

Call a game a repeat if it is not the first game for both players. There are 28 playing positions available (2 per game) and each of the 20 players takes at least one. So there are at most 8 repeat games. So there are at least 6 games which are not repeats. These must involve 12 different players. 18th USAMO 1989 © John Scholes jscholes@kalva.demon.co.uk 11 May 2002

Source: NuminaMath-1.5, licensed Apache-2.0. Statement reproduced verbatim; metadata (topic, difficulty, ordering) added by this project.