Number Of Elements In A Subset
A subsets of the set has the property that no pair of distinct numbers in has a sum divisible by 7.
What is the largest number of elements that could have?
The answer is 45.
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.
1 solution
Moderator note:
This solution is incomplete. It shows that we can pick 45 elements that satisfy the condition.
It doesn't yet explain why we cannot pick 46 elements that satisfy the condition.
Let A1 be a subset of A having the numbers with a remainder of 1 when divided by 7. A1=(1,8,15,...99) :15 elements
Let A2 be a subset of A having a remainder with a remainder of 2 when divided by 7. A2=(2,9,...100): 15 elements
Let A3.........A3=(3,10,...94) : 14 elements
Let A4.........A4=(4,11,...95): 14 elements
Let A5.........A5=(5,12,...96): 14 elements
Let A6.........A6=(6,13,...97): 14 elements
let A7...........A7=(7,14,...98): 14 elements
Pick all the elements of A1, A2 A3 and one element of A7 for a total of 15+15+14+1=45
Having chosen all the elements in A1 one can't choose any elements from A6.
Having chosen all the elements of A2 one can't choose any elements from A5.
Having chosen all the elements of A3 one can't choose any elements from A4.
One can choose one and only one element of A7.