(G, *) is a finite group with n elements. K is a subset of G with more than n/2 elements. Prove that for every g ∈ G, we can find h, k ∈ K such that g = h * k.
Take any g in G. Let H be the set of elements of the form h-1*g where h is in K. Since G is a group, H has the same number of elements as K. Hence it must overlap K (since between them they have more than n elements). So for some h, k in K we have k = h-1*g, or g = h*k.
29th Putnam 1968
© John Scholes
14 Jan 2002