Given 8 distinct integers from the set 1 2 16 prove that

Given 8 distinct integers from the set {1, 2, . . . , 16}, prove that there exists k such that ai aj = k has at least 3 distinct solutions (ai , aj ) ?

Solution

For any k (unless the K is zero), at least 3 distinct solutions need not be existing.

Let\'s look at the next most favourable case

If k= 2;
We have to consider the case where the number of solutions of ai-aj=2 are minimum since we have to show that at least 3 distinct solutions exist (which means even in the most unfavourable case for a chosen k there will be 3 distinct solutions satisfying the equation ai-aj=2)

If k = 2; we start by taking numbers that are not at all 2 units apart from each other;
So we start with 1 and move 3 units successively ahead

1, 4, 7, 10,13, 16; Now we notice that these 6 numbers are of 3k+1 form; remaining numbers can be any 2 ranomdly selected say 2 and 11; we get 4-2 = 2 and 13-11=2; Hence only 2 distinct solutions are possible.