11th Chinese 1996 Problem B1 Eight singers sing songs at a festival. Each song is sung once by a group of four singers. Every pair of singers sing the same number of songs together. Find the smallest possible number of songs. Solution
: 14. Suppose there are n songs and that each pair of singers sing k songs together. Count the number of triples of two singers and a song, where the singers sing the song together. Each performance of n songs has 4 singers and hence 6 pairs of singers, so the number is 6n. There are 8·7/2 = 28 pairs of singers, each singing k songs, so 6n = 28k or 3n = 14k. So 14 divides n and hence n is at least 14. So we start by trying to find a sequence of 14 subsets of four elements of {1, 2, 3, 4, 5, 6, 7, 8} such that each pair i, j is in three subsets. There is nothing in the question to stop us having the same subset several times (so that the same group of 4 singers sing several songs together), but a little experimentation suggests that no two subsets have even 3 elements in common. A little further experimentation gives: 1 2 3 4 1 3 5 7 1 4 5 8 1 2 5 6 1 3 6 8 1 4 6 7 1 2 7 8 2 3 5 8 2 4 5 7 2 3 6 7 2 4 6 8 3 4 5 6 3 4 7 8 5 6 7 8 which works, so the smallest possible n is 14. 11th Chinese 1996 © John Scholes jscholes@kalva.demon.co.uk 22 June 2002