Let and be a non empty subset of such that the sum of no two elements in is divisible by . Find the maximum possible number of elements in .
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
Let A i be a subset of X such that A i = 7 n + i n ∈ I
A 0 = { 7 , 1 4 , 2 1 , . . . . 9 8 }
A 1 = { 1 , 8 , 1 5 , . . . . . 9 9 }
A 2 = { 2 , 9 , 1 6 , . . . . 1 0 0 }
A 3 = { 3 , 1 0 , 1 7 , . . . . 9 4 }
A 4 = { 4 , 1 1 , 1 8 , . . . . 9 5 }
A 5 = { 5 , 1 2 , 1 9 , . . . . 9 6 }
A 6 = { 6 , 1 3 , 2 0 , . . . . 9 7 }
Number of elements in A 0 = 1 4
A 1 = 1 5
A 2 = 1 5
A 3 = 1 4
A 4 = 1 4
A 5 = 1 4
A 6 = 1 4
If we select an element from A 1 , no element from A 6 can be selected as the sum of the two elements would be divisible by 7.
So for maximum possible elements Y should have : 1 element from A 0 ,15 elements from A 1 , 15 elements from A 2 and 14 elements from either A 3 or A 4 .
So the maximum possible number of elements = 1 + 1 5 + 1 5 + 1 4 = 4 5