How do we solve the following problem from ZIO 2016
Uncle Shiva has given Nikhil yet another toy. It consists of a bag containing a collection of wooden tiles. Each tile has a number written on it and no two tiles in the bag have the same number written on them.
Uncle Shiva will then call out a number K. Nikhil should pick out a subset of the tiles from the bag so that if tile numbered i and j are in his subset then i − j is not K. That is, for any two tiles in his bag the difference between the numbers written on them should NOT be K.
Of course, Nikhil could just pick the empty subset or say a subset with only one tile and claim to have solved the game. Uncle Shiva expects him to pick a subset with maximum size to win the game.
Suppose the bag contains tiles with the numbers 1, 2, 3, 4, 5, 9 and K = 3. Then Nikhil can pick {1, 2, 3, 9}. But he cannot pick {1, 2, 4, 9} because 1 and 4 differ by 3. (There are many subsets of size 4 which satisfy the requirement: {1, 2, 3, 9}, {1, 3, 5, 9}, {2, 3, 4, 9} , {2, 3, 5, 9}). You can check that there is no subset of size more than 4 satisfying the requirement.
Your task is only to report the size of the largest set such that no pair differs by K.
For this instance, the answer is 4.
Report the answer for 3 sets of tiles and K:
(a) S = {2,3,7,8,9,10,13,14,15,16,19,20,21,22,25,26,27,28,31,32,33,34,38} K = 6
(b) S = {2,5,9,11,12,16,18,19,23,25,26,30,32,33,37,40,44,51,58} K = 7
(c) S = {2,3,4,6,7,8,9,10,11,12,13,14,15,16,18,19,20,22,25,26,29} K = 7