IMO 1981 SL 8

Origin: FRG

Problem

Let f(n, r) be the arithmetic mean of the minima of all r- subsets of the set {1, 2, . . ., n}. Prove that f(n, r) = n+1 r+1 .

Solution

Since the number k, k = 1, 2, . . ., n −r + 1, is the minimum in exactly
n−k r−1  r-element subsets of {1, 2, . . ., n}, it follows that

f(n, r) =
n r  n−r+1  k=1 k n −k r −1  . To calculate the sum in the above expression, using the equality
r+j j 

j i=0
r+i−1 r−1  , we note that n−r+1  k=1 k n −k r −1 

n−r  j=0

j  i=0 r + i −1 r −1 

n−r  j=0 r + j r 

n + 1 r + 1  = n + 1 r + 1 n r  . Therefore f(n, r) = (n + 1)/(r + 1).