- #1
srfriggen
- 306
- 5
Homework Statement
Can you partition the positive integers in such a way that if x, y are member of A, then x+y is not a member of A. x and y have to be distinct. That is, {1, 2, 3} cannot be in the same set, since 1+2 = 3, but 1 and 2 can be, since 1+1=2, but 1 and 1 are not distinct.
Homework Equations
The Attempt at a Solution
It is pretty straightforward to show that this cannot be done with two sets. There are only four cases to test, since eventually you have to decide where 1 and 2 go, and things fall into place from there.
A = {1, 2, 7, 8}
B = {3, 4, 5 6}
And we see that it fails at 9.
For three sets it's just a bit longer, but I can get it to fail at 19.
My professor assured us it can be done in 4 sets. He also suggested looking at the sets when they fail, specifically when they fail at the lowest number (So for A, B above, that is 9) and drawing some conclusions from there.
I have been scribbling out dozens of pages since Thursday on this and can't make any sense of it.
I don't know how to "prove" it would work. The only strategy that seems to make any sense is looking at the specific partitioning of individual numbers. For example, 5 = 2+3, so they can't all be in the same set. But that seems too obvious.
I'd love to get this one on my own so please if you have a strategy I'd love to hear it, but I really want to do the legwork. But at this point it's just frustrating that I'm not going anywhere and a push in the right direction would be very generous. Thank you for reading this.