What Five Numbers Create Proper Subsets with Non-Divisible Sums by 5?

  • Context: Undergrad 
  • Thread starter Thread starter kant
  • Start date Start date
  • Tags Tags
    Numbers
Join the discussion
Registration is free. Ask a follow-up in this thread, or start your own.
Sign up Log in
7 replies · 4K views
kant
Messages
388
Reaction score
0
1) imagine 5 numbers
2) imagine the subsets of those 5 numbers.
3) imagine the sum total of the elements in each subsets in 2).
4) It is required that none of the sum of each subset are divisible by 5.
5) What is the five numbers?
 
Last edited:

Discussion

Mathematics news on Phys.org
What do you mean by number? Do you mean integers or any real number? I don't think this is possible with the integers if I am interpreting subset as I should be.
 
Good question! It is integers
 
kant said:
Good question! It is integers

But if the sum of the numbers in any subset of the 5 numbers can't be divisibe by 5, that means that no number in the original set can be divisible by 5, but then I'm pretty sure that no matter what you will end up with at least one subset that adds up to a number that is divisible by 5.
 
I can see how it's possible with 4 numbers but not 5. I don't think it can be done, but hey, I also have to assume kant actually has a correct solution (OK, I hope he does!) The reason I don't think it can be done is because in Z5 (the field of integers modulo 5) there are only 4 equivalence classes that are non-zero.
 
daveb said:
I can see how it's possible with 4 numbers but not 5. I don't think it can be done, but hey, I also have to assume kant actually has a correct solution (OK, I hope he does!) The reason I don't think it can be done is because in Z5 (the field of integers modulo 5) there are only 4 equivalence classes that are non-zero.

Yea that's what I've been thinking, every integer has to be able to be expressed as one of

5n
5n + 1
5n + 2
5n + 3
5n + 4

for some integer n.

5n is immediately out for any of the 5 numbers because the set of subsets includes just the single numbers so none of them can be divisible by 5. But then I can't think of any possibility using any of the others that will not give you some subset whose sum is divisible by 5.
 
Clearly, as d_leet points out, none of the numbers can be divisible by 5. In fact, it is only necessary to consider the numbers modulo 5 since we only care about divisibility. Here are all the possible sets of 5 numbers modulo 5 and leaving out 0. The first 5 digits are the set (where the elements are arrayed in non-decreasing order), and the second set of digits is the subset whose sum is divisible by 5. It shows that the problem has no solution. x represents any digit.

1. 11111 - 11111
2. 11112 - 1112
3. 11113 - 113
4. 11114 - 14
5. 1112x - 1112
6. 1113x - 113
7. 1114x - 14
8. 1122x - 122
9. 1123x - 23
10. 1124x - 14
11. 113xx - 113
12. 114xx - 14
13. 122xx - 122
14. 123xx - 23
15. 124xx - 14
16. 1333x - 1333
17. 1334x - 334
18. 13444 - 3444
19. 14xxx - 14
20. 22222 - 22222
21. 22223 - 23
22. 22224 - 2224
23. 2223x - 23
24. 22244 - 244
25. 223xx - 23
26. 22444 - 244
27. 23xxx - 23
28. 244xx - 244
29. 33333 - 33333
30. 33334 - 334
31. 1334x - 334
32. 334xx - 334
33. 3444x - 3444
34. 44444 - 44444

I wonder if kant means 'proper' subset in item 2. in that case, you can use {1, 1, 1, 1, 1}, {2, 2, 2, 2, 2}, {3, 3, 3, 3, 3} or {4, 4, 4, 4, 4}. If distinct integers are required, then use the fact that we only care about modulo 5. For example {3, 8, 13, 18, 23}.
 
Last edited:
It would work if you could only use proper subsets of the 5 numbers. Then you could choose {n, n+5, n+10, n+15, n+20} as your set (assume n mod 5 not equal 0), and since 4n mod 5 is not zero, that works (which is how I got 4 numbers).