Challenging one!
Let S = 1 , 2 , 3 , . . . . , 4 0 and let A be a subset of S such that no two elements in A have their sum divisible by 5. What is the maximum number of elements possible in A ?
The answer is 17.
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.
4 solutions
The numbers in set S can be divided in these categories : 5 n + 1 , 5 n + 2 , 5 n + 3 , 5 n + 4 , 5 n . All of these have 8 numbers each.Now,let us say that we take all numbers of the form: 5 n + 1 ,then we can't have any number of the form : 5 n + 4 but we can have all the numbers of the form : 5 n + 2 .Now that we have taken all the numbers of the form 5 n + 2 ,we can't have any number of the form 5 n + 3 .That is a total of 1 6 numbers.But we can have one number of the form 5 n . Thus,at most we can have 1 7 numbers.
How did you deduce that you have to select numbers of the form 5n+1 in the first place?
Log in to reply
Actually,it doesn't matter.Here is a brief generalisation:let us say that we choose the numbers of the form ( 5 n + k ) ⇒ y o u c a n ′ t c h o o s e a n y n u m b e r f r o m t h e s e t 5 n + ( 5 − k ) . T h a t m e a n s w e h a v e e x c l u d e d t w o s e t s . W e h a v e t w o s e t s r e m a i n i n g ( e x c l u d i n g 5 n ) . N o w , a g a i n w e c h o o s e n u m b e r s o f t h e f o r m ( 5 n + l ) ⇒ y o u c a n ′ t c h o o s e a n y n u m b e r f r o m t h e s e t 5 n + ( 5 − l ) . N o w , w e a r e l e f t w i t h j u s t o n e s e t . W e c a n h a v e o n l y o n e n u m b e r f r o m t h e s e t ( 5 n ) .
As you know we need those numbers in set A whose sum(any 2 no.) is not divisible by 5. so this can be done by eliminating the no. from 1 to 10. Choose any two no. from 1 to 10 whose sum is divisible by 5 i.e 1+4=5, 2+3=5, n so on. Now choose any one no. from each pair like 1,2,6 and 7( 4 no's). Now choose b/w 1 to 40 those no's who are having these no's on their unit place i.e 11,12,16,17,21 and so on. so their will be 16 no. in total now we can also include any no which is divisible by 5 because on adding with any of these no. it will no longer be divisible by 5. therefore, total no. in A= 16+1= 17
1 with 4 and 9 gives sum divisible by 5. All with unit 1 not in A.
2 with 3 and 8 gives sum divisible by 5. All with unit 2 not in A.
3 with 7 gives sum divisible by 5. All with unit 7 not in A.
4 with 6 gives sum divisible by 5. All with unit 6 not in A.
So all with units 3, 4, 8, 9= 4 * 4= 16. 5 or 10 alone with any of these would NOT be divisible by 5.
Total 16 + 1 = 17.
1 7
S ≡ { 1 , 2 , 3 , 4 , 5 , 1 , 2 , 3 … 4 , 5 } ( m o d 5 )
You can assign only one number from each of the sets { 1 , 4 } and { 2 , 3 } as the possible remainders a number of A will leave when divided by 5 . Since S has 8 numbers for each of the possible remainders in the division by 5 , we can easily choose 1 6 numbers for A .
But there is one last observation:
We can choose one multiple of 5 for A , since 0 + x ≡ 0 ( m o d 5 ) ∀ x ≡ 0 ( m o d 5 )
So the maximum number of elements possible in A is 1 6 + 1 = 1 7