14th Chinese 1999 Problem A3 A space station has 99 pods. Every pair of pods is connected by a tube. 99 tubes are two-way, the others are all one-way. What is the largest number of sets of 4 pods that can be fully communicating (so that one can go between any two pods of the set without going outside the four pods and their six tubes)? Solution
: 2052072 = 99C4 - 99 48C3, where nCm denotes the binomial coefficient n!/( (n-m)! m!). It is easy to check that a set of 4 pods is fully communicating iff there is no pod A in the set such that the three tubes from it to the other members of the set are all towards A or all away from A. Let the pods A 1 , A 2 , A 3 , ... , A 99 be arranged in a circle. If 198 >= n > 99, take A n to mean A n-99 . Connect A n and A n+1 by a two-way tube. Connect A n to A n+3 , A n+5 , A n+7 , ... , A n+97 by a tube leading from A n . Then A n is connected to A n+2 , A n+4 , ... , A n+96 by tubes leading towards A n . A 1 is in 48C3 sets of 4 such that all tubes involving A 1 lead towards A (the other pods are any three from A 3 , A 5 , ... , A 97 ) and A 1 is in 48C3 sets of 4 such that all tubes involving A 1 lead away from A 1 (the other pods are any three from A 4 , A 6 , ... , A 98 ). But A 1 , A 1+2i , A 1+2j , A 1+2k with 0  y, then (x - 1)(x - 2) ≥ y(y - 1), so x(x - 1)(x - 2) + y(y - 1)(y - 2) ≥ (x - 1)(x - 2)(x - 3) + (y + 1)y(y - 1), so xC3 + yC3 ≥ (x-1)C3 + (y+1)C3. 14th Chinese 1999 © John Scholes jscholes@kalva.demon.co.uk 19 June 2002