Question

Show that for any k ≥ 2, if n + 1 distinct integers are chosen from the set [kn] = {1, 2, . . . , kn}, then there will be two integers which differ by at most k − 1. Please demonstrate the steps so that I can learn from it and solve other problems by following the reasoning!

Answer 1

We first suppose that the given result is not true and will later see that this assumption leads us to a contradiction.

So, suppose we can choose n+1 distinct integers from the set [kn] = {1,2, . . . , kn} such that the difference between any two of them is at least k, Where .

Let these chosen integers are arranged in a increasing order and denote them as   

So,

   [ Since the difference between   and is at least k]

  

  

  

  

  

  

This is a contradiction because cannot be larger than the largest element kn of the set [kn].

Hence our assumption leads us to a contradiction. So our assumption was wrong. Hence, for any , if n+1 distinct integers are chosen from the set [kn] = {1,2, . . . , kn} , then there will be two integers which differ by at most k-1.

(Proved)