Partition the integers under "anti-closure" of addition

[srfriggen]

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.

 

[WWGD]

Any constraint on number of sets in partition? Try {n,n+1} , and stop when you get a sum in the set. Can you find a pattern?

 

[Mark44]

What about a partition of odd integers versus even integers?

 

[srfriggen]

Any constraint on number of sets in partition? Try {n,n+1} , and stop when you get a sum in the set. Can you find a pattern?

Yes. My prof says to do it with 4 sets.

I'm seeing a pattern of double the starting number, plus one. So my sets are, {1, 2}, {3, 4, 5, 6}, {7, 8, ...14}, {15, 16, ...29, 30}.

From there I can place different numbers in different sets to get pretty high but I'm not seeing any underlying structure to make sense of the problem.

 

[WWGD]

Yes. My prof says to do it with 4 sets.

I'm seeing a pattern of double the starting number, plus one. So my sets are, {1, 2}, {3, 4, 5, 6}, {7, 8, ...14}, {15, 16, ...29, 30}.

From there I can place different numbers in different sets to get pretty high but I'm not seeing any underlying structure to make sense of the problem.

Seems like some Graph Theory /Combinatorics could help here: "Draw" a graph with vertices the Integers and draw a triangle between a,b,c if a+b =c . Then you want a triangle-free graph, maybe a collection of trees that span all the Integers? Just an idea, I have not fully thought it through.

 

[fresh_42]

I would follow @Mark44 's hint with my contribution: apply the same method again on the rest. At last there will remain a set, which can be taken to start with and then rearrange the formerly defined. I think, this could work, but I'm not sure.

 

[Mark44]

In the problem statement, there was no mention of how many sets the integers should be partitioned into, so I assumed that "partition" meant dividing the integers into two subsets. A more well-written problem should have made that clear. The plan I described divides numbers into one of two possible congruence classes: [0] (the evens}, and [1] (the odds). If you take any two odd numbers and add them, you get an even number, thus not in the set of odd numbers. The set with the even numbers is closed under addition, so doesn't satisfy the non-closure condition of the problem.

If you divide the numbers into three congruence classes modulo 3, then any two numbers that are congruent to 1 (modulo) 3, their sum is congruent to 2 (modulo 3). If you take any two numbers that are congruent to 2 (mod 3), their sum is congruent to 1 (mod 3). So out of this partition, two of the three subsets satisfy the problem condition.

If you divide the integers into four congruence classes modulo 4, two of the equivalence classes, [1] and [3], work. The problem statement isn't clear on whether nonclosure has to apply to all subsets, or just some of them.

 

[Dick]

In the problem statement, there was no mention of how many sets the integers should be partitioned into, so I assumed that "partition" meant dividing the integers into two subsets. A more well-written problem should have made that clear. The plan I described divides numbers into one of two possible congruence classes: [0] (the evens}, and [1] (the odds). If you take any two odd numbers and add them, you get an even number, thus not in the set of odd numbers. The set with the even numbers is closed under addition, so doesn't satisfy the non-closure condition of the problem.

If you divide the numbers into three congruence classes modulo 3, then any two numbers that are congruent to 1 (modulo) 3, their sum is congruent to 2 (modulo 3). If you take any two numbers that are congruent to 2 (mod 3), their sum is congruent to 1 (mod 3). So out of this partition, two of the three subsets satisfy the problem condition.

If you divide the integers into four congruence classes modulo 4, two of the equivalence classes, [1] and [3], work. The problem statement isn't clear on whether nonclosure has to apply to all subsets, or just some of them.

Along those same lines if you define $P_n=\{2^n (2k+1):k \ge 0\}$, then the $P_n$ form a partition of the integers into an infinite number of arithmetic sequences which have the 'anti-additive' property. $P_0$ is just the odd numbers. But infinite is a lot bigger than 4. On the other hand there is a clever proof using generating functions that you can't partition the integers into a finite number of arithmetic sequences. So if this is going to work you need some sort of partition sets other than arithmetic sequences.

 

[srfriggen]

Along those same lines if you define $P_n=\{2^n (2k+1):k \ge 0\}$, then the $P_n$ form a partition of the integers into an infinite number of arithmetic sequences which have the 'anti-additive' property. $P_0$ is just the odd numbers. But infinite is a lot bigger than 4. On the other hand there is a clever proof using generating functions that you can't partition the integers into a finite number of arithmetic sequences. So if this is going to work you need some sort of partition sets other than arithmetic sequences.

We are starting to learn about generating functions so I have a feeling they will be relevant to this problem. Interestingly my professor never said it could be done. He simply asked, "Can you do [this]?" So the answer may be, "no." The generating function proof may shed light on why not. I won't bother the community to school me on generating functions. I still need to do the work on my own.

Once again, I appreciate all of the responses. Mark44 I am sorry that the problem, as I stated it, was unclear. Thank you for your insight.

 

[fresh_42]

I found a partition $2\mathbb{Z}+1\; , \;4\mathbb{Z}+2\, , \,8\mathbb{Z}+4$ with $8\mathbb{Z}$ left. Now I started with $8\mathbb{Z}$ and sorted it into four different sets and I think that the others can be added without breaching the requirements, but it's a bit messy.