54th Kürschák 1953

A and B are any two subsets of {1, 2, ... , n-1} such that |A| + |B| > n-1. Prove that one can find a in A and b in B such that a + b = n.

Solution

Let A be {a₁, a₂, ... , a_h}, B be {b₁, b₂, ... , b_k}. Now consider the numbers a₁, a₂, ... , a_h, n-b₁, n-b₂, ... , n-b_k. There are more than n-1 of them, all belonging to {1, 2, ... , n-1}, so there must be two the same. We cannot have a_i = a_j or n-b_i = n-b_j (for i ≠ j), because the elements of A are distinct and the elements of B are distinct. So we must have a_i = n-b_j for some i, j.

54th Kürschák 1953

© John Scholes
jscholes@kalva.demon.co.uk
29 Oct 2003
Last corrected/updated 29 Oct 03