Number problem
Moderators: gmalivuk, Moderators General, Prelates

 Posts: 22
 Joined: Sun Jun 22, 2008 1:13 pm UTC
Number problem
Hello everyone.
I have been working on a math problem for some time now, but I can not finish the proof. In other words, I'm stuck. I hope someone here can solve it for me, or perhaps we could make it into a joint effort. The problem is taken from a monthly math magazine, which features 3 math problems each month.
Here's the problem:

Consider a set [imath]S \subset\mathbb{Z}[/imath] with [imath]S = 15[/imath] and the following property:
[imath]\forall s \in S[/imath] : [imath]\exists a,b \in S[/imath] such that [imath]s = a + b[/imath].
Prove that for every such [imath]S[/imath], there exists a nonempty subset [imath]T \subset S[/imath] with [imath]T \leq 7[/imath] such that the sum of the elements of [imath]T[/imath] equals zero.

Good luck,
 NightBreeze
Edit: This is not a homework problem. It's just a math puzzle I came across somewhere and I want to know its solution. I figured you guys might also enjoy working on it.
I have been working on a math problem for some time now, but I can not finish the proof. In other words, I'm stuck. I hope someone here can solve it for me, or perhaps we could make it into a joint effort. The problem is taken from a monthly math magazine, which features 3 math problems each month.
Here's the problem:

Consider a set [imath]S \subset\mathbb{Z}[/imath] with [imath]S = 15[/imath] and the following property:
[imath]\forall s \in S[/imath] : [imath]\exists a,b \in S[/imath] such that [imath]s = a + b[/imath].
Prove that for every such [imath]S[/imath], there exists a nonempty subset [imath]T \subset S[/imath] with [imath]T \leq 7[/imath] such that the sum of the elements of [imath]T[/imath] equals zero.

Good luck,
 NightBreeze
Edit: This is not a homework problem. It's just a math puzzle I came across somewhere and I want to know its solution. I figured you guys might also enjoy working on it.
Last edited by Nightbreeze on Sun Jun 22, 2008 7:32 pm UTC, edited 7 times in total.
Re: Number problem
If this is homework help, you should make that clear.
This is a placeholder until I think of something more creative to put here.

 Posts: 22
 Joined: Sun Jun 22, 2008 1:13 pm UTC
Re: Number problem
It's not. I figured you might enjoy a puzzle as much as I do.
We could turn this thread into a joint effort to solve it, but I thought I'd wait to see what people come up with before posting what I have done so far.
We could turn this thread into a joint effort to solve it, but I thought I'd wait to see what people come up with before posting what I have done so far.
 DubioserKerl
 Posts: 71
 Joined: Sat Jun 07, 2008 8:23 am UTC
Re: Number problem
Nightbreeze wrote:I offer you the following problem, which I have not yet been able to solve. I have progressed towards a full proof, but am stuck at some point.
Consider a set A [imath]\subset\mathbb{Z}[/imath] with S = 15 and the following property:
[imath]\forall s \in S[/imath] : [imath]\exists a,b \in S[/imath] such that [imath]s = a + b[/imath].
Prove that for every such S, there exists a subset T[imath]\subset[/imath] S with T [imath]\leq[/imath] 7 such that the sum of the elements of T equals zero.
Do you mean a subset S? Ot what does your set A has to do with the set S?
DK

 Posts: 22
 Joined: Sun Jun 22, 2008 1:13 pm UTC
Re: Number problem
Whoops. No idea where that A came from, it's supposed to be an S.
Edited.
Edited.
 jestingrabbit
 Factoids are just Datas that haven't grown up yet
 Posts: 5967
 Joined: Tue Nov 28, 2006 9:50 pm UTC
 Location: Sydney
Re: Number problem
This looks wrong
Spoiler:
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

 Posts: 22
 Joined: Sun Jun 22, 2008 1:13 pm UTC
Re: Number problem
Take [imath]T = \{0\}[/imath].
 jestingrabbit
 Factoids are just Datas that haven't grown up yet
 Posts: 5967
 Joined: Tue Nov 28, 2006 9:50 pm UTC
 Location: Sydney
Re: Number problem
Gah, I was thinking T=7 not \le. my bad.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.
 Torn Apart By Dingos
 Posts: 817
 Joined: Thu Aug 03, 2006 2:27 am UTC
Re: Number problem
You should require T to be nonempty. Otherwise T={} works for any S (the empty sum is 0).

 Posts: 22
 Joined: Sun Jun 22, 2008 1:13 pm UTC
Re: Number problem
Good point. Edited.
Re: Number problem
I read this yesterday and it really wedged istelf in the back of my head. Anyone have hints or anything?
In questions of science, the authority of a thousand is not worth the humble reasoning of a single individual.
Galileo
Galileo

 Posts: 22
 Joined: Sun Jun 22, 2008 1:13 pm UTC
Re: Number problem
I have done a fair bit of research. Maybe it's wise to post it here to help people along.
First of all, if [imath]0 \in S[/imath] or if any s has an inverse in S, then the required subset is rather trivial, don't you agree? We can either take [imath]T = \{0\}[/imath] or [imath]T = \{s, s\}[/imath]. So we may rightly assume that s does not contain zero and has no inverses.
With that being said, the smallest possible set S of integers that still satisfies the second property has size 6. This is because S necessarily includes 3 positive and 3 negative numbers. The reason for this can be readily found when trying to construct such an S. I can proof it, but you'll figure it out if you try and construct one yourself, so I won't. An example would be
[math]S = \{6, 5, 3, 1, 2, 4\}[/math] (edited the 4 to be a 5... stupid typo)
Furthermore, if S is of the form 2n, then we can always find an S such that the smallest T that sums to zero will have T = n. Consider the case where S = 16. Then we can find an S like this:
[math]S = \{–254, –253, –251, –247, –239, –223, –191, –127, 1, 2, 4, 8, 16, 32, 64, 128\}[/math]
You will need at least 8 members of S to sum to zero.
I suspect that the best approach to proof this is to start with a wellchosen member s and 'expand' it, if you will, as the sum of other members of s. If, at some point, you come across s again, you will know that the sum of the remaining terms will add up to zero. However, there are some issues with this approach.
 Some numbers can be written as the sum of two members of S in more than 1 way.
 There can not be doubles in the 'expansion' of s.
 Some numbers will never reoccur in an expansion.
We will probably have to investigate the internal structure of such an S and come up with properties to show that this is indeed possible. Maybe make a graph out of it?
For instance, it's easy to show that if you keep on expanding, you will enter a loop at some point. This is simply because the number of elements in S is finite.
Hope this helps. I have some more results.. but let's just see if this is useful.
First of all, if [imath]0 \in S[/imath] or if any s has an inverse in S, then the required subset is rather trivial, don't you agree? We can either take [imath]T = \{0\}[/imath] or [imath]T = \{s, s\}[/imath]. So we may rightly assume that s does not contain zero and has no inverses.
With that being said, the smallest possible set S of integers that still satisfies the second property has size 6. This is because S necessarily includes 3 positive and 3 negative numbers. The reason for this can be readily found when trying to construct such an S. I can proof it, but you'll figure it out if you try and construct one yourself, so I won't. An example would be
[math]S = \{6, 5, 3, 1, 2, 4\}[/math] (edited the 4 to be a 5... stupid typo)
Furthermore, if S is of the form 2n, then we can always find an S such that the smallest T that sums to zero will have T = n. Consider the case where S = 16. Then we can find an S like this:
[math]S = \{–254, –253, –251, –247, –239, –223, –191, –127, 1, 2, 4, 8, 16, 32, 64, 128\}[/math]
You will need at least 8 members of S to sum to zero.
I suspect that the best approach to proof this is to start with a wellchosen member s and 'expand' it, if you will, as the sum of other members of s. If, at some point, you come across s again, you will know that the sum of the remaining terms will add up to zero. However, there are some issues with this approach.
 Some numbers can be written as the sum of two members of S in more than 1 way.
 There can not be doubles in the 'expansion' of s.
 Some numbers will never reoccur in an expansion.
We will probably have to investigate the internal structure of such an S and come up with properties to show that this is indeed possible. Maybe make a graph out of it?
For instance, it's easy to show that if you keep on expanding, you will enter a loop at some point. This is simply because the number of elements in S is finite.
Hope this helps. I have some more results.. but let's just see if this is useful.
Last edited by Nightbreeze on Mon Jun 23, 2008 5:58 pm UTC, edited 1 time in total.

 Posts: 47
 Joined: Sun Jun 22, 2008 3:54 am UTC
Re: Number problem
S={−6,−4,−3,1,2,4}
I don't see an a and b in S such that a+b= 6

 Posts: 22
 Joined: Sun Jun 22, 2008 1:13 pm UTC
Re: Number problem
a and b don't have to be distinct. In this case, choose a = b = 3
Re: Number problem
Nightbreeze wrote:the smallest possible set S of integers that still satisfies the second property has size 6. This is because S necessarily includes 3 positive and 3 negative numbers.
Wait, wait... {0} works, as does {1,0,1}
Nightbreeze wrote:I suspect that the best approach to proof this is to start with a wellchosen member s and 'expand' it, if you will, as the sum of other members of s. If, at some point, you come across s again, you will know that the sum of the remaining terms will add up to zero. However, there are some issues with this approach.
 Some numbers can be written as the sum of two members of S in more than 1 way.
 There can not be doubles in the 'expansion' of s.
 Some numbers will never reoccur in an expansion.
We will probably have to investigate the internal structure of such an S and come up with properties to show that this is indeed possible. Maybe make a graph out of it?
For instance, it's easy to show that if you keep on expanding, you will enter a loop at some point. This is simply because the number of elements in S is finite.
Hope this helps. I have some more results.. but let's just see if this is useful.
I played with the expansions as well, with nothing particularly fun coming out. Turns out, I can take 15 "dots" and connect them properly without ever running into the contradiction we're looking for. That is, given any "dot", I have to pass through at least 3 other dots before returning. I earlier made a little graph of 15 dots, all connected properly, that ran through more than 3 other dots. So I think we'll have to look at properties of Z, as well...
I think that the answer might lie in induction. "Given a set with 2n+1 elements with the given property (call it p), there is a subset with n elements whose sum is zero." We can show that a set consisting of 2(1)+1=3 elements with the given property must contain 0 (more specifically, a set of size 1 whose sum is 0). Suppose not. We have a, b, and c in our set.
a = b + c (if a = c or a = b, then we can make the substitution and have the other equal to 0, a contradiction)
b = a + c
c = a + b
> a = a + c + a + b > a = a + a > a = 0, a contradiction.
So now we do the inductive step. Suppose we've proven that the statement holds for 2n+1 (which means we've also proven it for all elements of N less than n, which is possibly important). Now, we have to show it holds for 2(n+1) + 1. If it *doesn't*, then we have that there exists no subset of a size less than or equal to n+1 that adds to 0, which *also* means that since we've done induction up to n, no subset of the form 2m+1 (where m is less than or equal to n) can have property p. And... and... then... we can... do... something neat.
Perhaps we can actually work out the induction from 3 elements to 15 elements explicitly, but I'd prefer not. O_o; Perhaps we can/should also hit the even numbers, as well.
What they (mathematicians) define as interesting depends on their particular field of study; mathematical anaylsts find pain and extreme confusion interesting, whereas geometers are interested in beauty.
Re: Number problem
z4lis wrote:Nightbreeze wrote:the smallest possible set S of integers that still satisfies the second property has size 6. This is because S necessarily includes 3 positive and 3 negative numbers.
Wait, wait... {0} works, as does {1,0,1}
Nightbreeze specifically already mentioned the cases where S contains 0 or a number and its negation, and intended those cases to be excluded in the above statement:
Nightbreeze wrote:So we may rightly assume that s does not contain zero and has no inverses.
Unfortunately the next example fails this:
Nightbreeze wrote:An example would be
[math]S = \{6, 4, 3, 1, 2, 4\}[/math]
but it can be fixed:
[math]S = \{6, 5, 3, 1, 2, 4\}[/math]
I haven't made much headway either.

 Posts: 22
 Joined: Sun Jun 22, 2008 1:13 pm UTC
Re: Number problem
jaap wrote:Unfortunately the next example fails this.
Typo's > me. Thanks for pointing it out.
z4lis wrote:I think that the answer might lie in induction.
I'm not convinced induction will be useful here. It's easy to show that S must contain zero or an inverse if S < 6, the problem lies beyond 6. The idea of using induction might be worth exploring, but the idea requires a little more elaboration before I'm convinced it might be useful. I don't see how yet.
"Explicitly" working out the induction strikes me as a contridiction in terms.
It's good to see it grabbed people's attention though =) Keep it up!
I suggest we first try to proof that there exists a subset [imath]T\subset S[/imath] which sums to zero at all. After that we can use the set's property to show that it also implies there is another T which sums to zero with T <= 7 by 'substituting' out certain members of the T we found.
Re: Number problem
I think the OP knows where this problem comes from
http://www.mathlinks.ro/viewtopic.php?p=1165531#1165531
The problem is taken from a monthly math magazine, which features 3 math problems each month.
http://www.mathlinks.ro/viewtopic.php?p=1165531#1165531
mosc wrote:How did you LEARN, exactly, to suck?

 Posts: 22
 Joined: Sun Jun 22, 2008 1:13 pm UTC
Re: Number problem
What do you mean?
I have posted this problem on several forums in the hope that someone somewhere can solve it. So far no one has done it. Time for XKCD to prove their worth.
It's taken from a dutch magazine.
I have posted this problem on several forums in the hope that someone somewhere can solve it. So far no one has done it. Time for XKCD to prove their worth.
It's taken from a dutch magazine.
Re: Number problem
It's just a math puzzle I came across somewhere
I'm just wondering whether this is the sort of thing where you send solutions back in as well
mosc wrote:How did you LEARN, exactly, to suck?

 Posts: 22
 Joined: Sun Jun 22, 2008 1:13 pm UTC
Re: Number problem
Would that make a difference to any of you people?
For the record: No, the issues is a couple of months old and the competition has long since expired.
For the record: No, the issues is a couple of months old and the competition has long since expired.
Re: Number problem
Nightbreeze wrote:Would that make a difference to any of you people?
At least one person (me), MathLinks have a similar policy regarding current magazine questions (There is a problem with M&Y questions being on the fora all the time)
mosc wrote:How did you LEARN, exactly, to suck?

 Posts: 22
 Joined: Sun Jun 22, 2008 1:13 pm UTC
Re: Number problem
Ah is that a fact. I did not know that.
Does this mean I'm not allowed to post math problems here or on mathlinks if they appeared in a magazine before? Or is there a policy on some particular magazine.
Either way, I don't think my case is a trouble to anyone afaik.
Does this mean I'm not allowed to post math problems here or on mathlinks if they appeared in a magazine before? Or is there a policy on some particular magazine.
Either way, I don't think my case is a trouble to anyone afaik.
Re: Number problem
No, its just before the magazine's deadlines run out on submitting solutions.
EDIT: Yay 256 posts
EDIT: Yay 256 posts
mosc wrote:How did you LEARN, exactly, to suck?

 Posts: 22
 Joined: Sun Jun 22, 2008 1:13 pm UTC
Re: Number problem
Do you have a take on the problem as well? gotta break the power of 2 limit some time.
Re: Number problem
Hm. Induction is a possibility. I just lack knowledge with combinatorics. Suppose we've proven our statement that a set with property p with size n (and all natural numbers less than n). (The exact statement: We take n = p mod 2. If p = 0, then a subset with a size equal to or smaller than n/2 sums to 0. If p = 1, then a subset with size equal to (n1)/2 sums to 0. Basically, if the set is even, half it. If the set is odd, subtract one and half it.) Now, we must prove that the statement holds for n+1. First, suppose n+1 is even.
If the statement is not true, then there exists no subsets that sum to 0 with a size less than or equal to (n+1)/2 = m. But this also means that it cannot contain a set of size less than or equal to n with property p. > Every element of our set is "needed" to give the set property p. That is, we can express every element of our set not only as a = b + c for some b,c in S, but we can also say that a  e = f for some e, f in S.
This is where the combinatorics come in. We now need to write down every combination of m+1 elements in S (which is alot) and add them up. I'm guessing (aka hoping and assuming) one of the sets will sum up to to be something already in the set, which means that we'll have a sum of m elements equal to 0, a contradiction.
That leaves the case if n is odd, which I'll leave for another day's ponderings.
If the statement is not true, then there exists no subsets that sum to 0 with a size less than or equal to (n+1)/2 = m. But this also means that it cannot contain a set of size less than or equal to n with property p. > Every element of our set is "needed" to give the set property p. That is, we can express every element of our set not only as a = b + c for some b,c in S, but we can also say that a  e = f for some e, f in S.
This is where the combinatorics come in. We now need to write down every combination of m+1 elements in S (which is alot) and add them up. I'm guessing (aka hoping and assuming) one of the sets will sum up to to be something already in the set, which means that we'll have a sum of m elements equal to 0, a contradiction.
That leaves the case if n is odd, which I'll leave for another day's ponderings.
What they (mathematicians) define as interesting depends on their particular field of study; mathematical anaylsts find pain and extreme confusion interesting, whereas geometers are interested in beauty.
Re: Number problem
Before worrying about getting a subset of the right size, it seems important to me that we show that there exists any nonempty subset whose members sum to 0. Afterwards, we'll likely be able to pare it down to one of size [imath]\lfloor\frac{n}{2}\rfloor[/imath] or less.
(∫p^{2})(∫q^{2}) ≥ (∫pq)^{2}
Thanks, skeptical scientist, for knowing symbols and giving them to me.
Thanks, skeptical scientist, for knowing symbols and giving them to me.
Re: Number problem
I can prove it if you allow T to be a multiset (the numbers I pick into T are not necessarily distinct)
.. does the result hold when you switch (Z,+) with less structured things ?
Also, if you know one decomposition for each number, you don't need anything else.
(you can recover the numbers from the graph of the decompositions)
.. does the result hold when you switch (Z,+) with less structured things ?
Spoiler:
Also, if you know one decomposition for each number, you don't need anything else.
(you can recover the numbers from the graph of the decompositions)

 Posts: 22
 Joined: Sun Jun 22, 2008 1:13 pm UTC
Re: Number problem
T can not be a multiset, unfortunately.
What you're doing is correct, but the fact that a member of S can not be used twice is exactly what makes it so hard to solve... I see no way of converting that proof to (Z, +) in an easy way.
What you're doing is correct, but the fact that a member of S can not be used twice is exactly what makes it so hard to solve... I see no way of converting that proof to (Z, +) in an easy way.
 Yakk
 Poster with most posts but no title.
 Posts: 11127
 Joined: Sat Jan 27, 2007 7:27 pm UTC
 Location: E pur si muove
Re: Number problem
For a set S with such a property, with S = n>1, we will attempt to show that there is a set T subset S such that T <= S/2 such that sum(T)=0.
Call a set with the (forall a in S, exist b,c in S such that a=b+c) to be splitclosed.
Handwavy inductive stuff goes here.
For any element {z} of S, define Z = S\{z}. Then either Z is splitclosed, or is not.
If Z is splitclosed, then we are done, inductively (as all smaller splitclosed sets admit a sufficiently small zerosumming set). So the handwaved inductive structure means we can assume that for each z, Z is not splitclosed.
Assuming Z is not splitclosed, then there are elements a,b from Z such that the _only_ split of a is b+z. Ie, a = b+z.
Or, reworded, we get z=ab for some elements a and b from S\{z}, for each element z from S.
Can we produce a uniqueness effect?
This applies to our b as well: b_0 = a_1b_1, giving us z = a_0 + a_1 + ... + a_k  b_k
Now, is there any way we can further restrict our choice of a_i's?
We could start with the lowest z.
Hmm.
Call a set with the (forall a in S, exist b,c in S such that a=b+c) to be splitclosed.
Handwavy inductive stuff goes here.
For any element {z} of S, define Z = S\{z}. Then either Z is splitclosed, or is not.
If Z is splitclosed, then we are done, inductively (as all smaller splitclosed sets admit a sufficiently small zerosumming set). So the handwaved inductive structure means we can assume that for each z, Z is not splitclosed.
Assuming Z is not splitclosed, then there are elements a,b from Z such that the _only_ split of a is b+z. Ie, a = b+z.
Or, reworded, we get z=ab for some elements a and b from S\{z}, for each element z from S.
Can we produce a uniqueness effect?
This applies to our b as well: b_0 = a_1b_1, giving us z = a_0 + a_1 + ... + a_k  b_k
Now, is there any way we can further restrict our choice of a_i's?
We could start with the lowest z.
Hmm.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision  BR
Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.
Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

 Posts: 22
 Joined: Sun Jun 22, 2008 1:13 pm UTC
Re: Number problem
My approach was a bit different.
Let S be a set of integers with S = 15. We may assume that S contains neither zero nor an inverse of another member of s, for it would make the choice for our subset T rather trivial. Consider now A to be the positive members of S and B to be the negative members of S. Without loss of generality, we may assume that A < B. So 3 <= A <= 7. Now define a graph G on A as follows: Let x, y be members of A. There exists an edge x > y if there exists a z in S such that x = y + z. By this definition, every member of A is adjacent to at least one other member of A, because every positive number can not be written as the sum of two negative numbers. Because A is finite, there must exist a cycle X = x_{1}, ... x_{k}. Let k be the smallest k with this property. Then there exist Z = z_{1}, ... z_{k} such that
x_{1} = x_{2} + z_{1} = x_{3} + z_{2} + z_{1} = ... = x_{1} + z_{k} + ... + z_{1}.
The the sequence z_{1}, ..., z_{k} will sum to zero.
The main problem in this proof has to do with the doubles that occur in such a sequence Z. If there are no doubles in the sequence, then we have found our T. So let's assume that there are x_{i} and x_{j} with i =/= j such that x_{i} = x_{i+1} + z and x_{j} = x_{j+1} + z. It is easy to show that z can not be a member of X. If it were, then there would exist a smaller cycle through x_{i}, x_{j} and z. That is not allowed since we chose X to be the smallest cycle in A. So we are left with the case that z is not a member of X. We need to proof that either we can replace z and still get a T with T <= 7 or that there must exist a different cycle (possibly in B) with the required properties.
I experiment some with assuming that X < 7. Then it's possible for z to be positive. There are some implications there, but nothing useful. We can 'expand' z a number of times till we reach a member of X. A new cycle might be possible in that way. Remember that our upper limit on the cycle size is equal to the upper limit on the amount of positive numbers in S. The other possibility is that z is in B. Maybe it's worth looking into the smallest cycle in B then? We have no guarantee that its length will be smaller than 7, but maybe we can proof that the biggest cycle in B can be no larger than the size of A. This certainly sounds plausible.. since negative numbers are absolutely required to make a cycle in the positive part of S.
The set I've been looking into most recently is S = {8, 4, 3, 1, 2, 5, 7, 9}. It's of size 8, naturally, but the cycle 9 > 7 > 5 > 9 has a complement Z which features the number 2 twice. I'm looking into how to fix this.
Maybe this is useful. Keep it up!
Let S be a set of integers with S = 15. We may assume that S contains neither zero nor an inverse of another member of s, for it would make the choice for our subset T rather trivial. Consider now A to be the positive members of S and B to be the negative members of S. Without loss of generality, we may assume that A < B. So 3 <= A <= 7. Now define a graph G on A as follows: Let x, y be members of A. There exists an edge x > y if there exists a z in S such that x = y + z. By this definition, every member of A is adjacent to at least one other member of A, because every positive number can not be written as the sum of two negative numbers. Because A is finite, there must exist a cycle X = x_{1}, ... x_{k}. Let k be the smallest k with this property. Then there exist Z = z_{1}, ... z_{k} such that
x_{1} = x_{2} + z_{1} = x_{3} + z_{2} + z_{1} = ... = x_{1} + z_{k} + ... + z_{1}.
The the sequence z_{1}, ..., z_{k} will sum to zero.
The main problem in this proof has to do with the doubles that occur in such a sequence Z. If there are no doubles in the sequence, then we have found our T. So let's assume that there are x_{i} and x_{j} with i =/= j such that x_{i} = x_{i+1} + z and x_{j} = x_{j+1} + z. It is easy to show that z can not be a member of X. If it were, then there would exist a smaller cycle through x_{i}, x_{j} and z. That is not allowed since we chose X to be the smallest cycle in A. So we are left with the case that z is not a member of X. We need to proof that either we can replace z and still get a T with T <= 7 or that there must exist a different cycle (possibly in B) with the required properties.
I experiment some with assuming that X < 7. Then it's possible for z to be positive. There are some implications there, but nothing useful. We can 'expand' z a number of times till we reach a member of X. A new cycle might be possible in that way. Remember that our upper limit on the cycle size is equal to the upper limit on the amount of positive numbers in S. The other possibility is that z is in B. Maybe it's worth looking into the smallest cycle in B then? We have no guarantee that its length will be smaller than 7, but maybe we can proof that the biggest cycle in B can be no larger than the size of A. This certainly sounds plausible.. since negative numbers are absolutely required to make a cycle in the positive part of S.
The set I've been looking into most recently is S = {8, 4, 3, 1, 2, 5, 7, 9}. It's of size 8, naturally, but the cycle 9 > 7 > 5 > 9 has a complement Z which features the number 2 twice. I'm looking into how to fix this.
Maybe this is useful. Keep it up!
 Yakk
 Poster with most posts but no title.
 Posts: 11127
 Joined: Sat Jan 27, 2007 7:27 pm UTC
 Location: E pur si muove
Re: Number problem
(9,7,5) has compliment (2,2,4)
But (9,2,5) has compliment (7,3,4)
9 = 7+2 = 73+5 = 734+9
Thus 734 = 0
But (9,2,5) has compliment (7,3,4)
9 = 7+2 = 73+5 = 734+9
Thus 734 = 0
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision  BR
Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.
Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.
Re: Number problem
Not a proof, but a set that works:
Let S be a mod set, specifically, Z mod 16.
Obviously, S=15={0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15}
The following are just one way to show that the first condition is satisfied, even if we mandate a and b to be distinct. Obviously there are other ways, but for giggles, I felt like showing them.
In other words, T=Z mod 7, or Z mod 5, or Z mod 3.
Let S be a mod set, specifically, Z mod 16.
Obviously, S=15={0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15}
The following are just one way to show that the first condition is satisfied, even if we mandate a and b to be distinct. Obviously there are other ways, but for giggles, I felt like showing them.
 0=15+1
 1=15+2
 2=15+3
 3=2+1
 4=3+1
 5=4+1
 6=5+1
 7=6+1
 8=7+1
 9=8+1
 10=9+1
 11=10+1
 12=11+1
 13=12+1
 14=13+1
 15=14+1
In other words, T=Z mod 7, or Z mod 5, or Z mod 3.

 Posts: 22
 Joined: Sun Jun 22, 2008 1:13 pm UTC
Re: Number problem
Yakk wrote:(9,7,5) has compliment (2,2,4)
But (9,2,5) has compliment (7,3,4)
9 = 7+2 = 73+5 = 734+9
Thus 734 = 0
I think I was a bit unclear about what 'fixing' meant. I can see there are other cycles which sum to zero. The problem was how to derive a structural approach from this particular case.
 Yakk
 Poster with most posts but no title.
 Posts: 11127
 Joined: Sat Jan 27, 2007 7:27 pm UTC
 Location: E pur si muove
Re: Number problem
I'll be more explicit!
(9,7,5) has compliment (2,2,4)
So we have:
(9,7,5)
(2,2,4)
Now, note that for any pair of such cycles, we can swap an from the top to the bottom, and the top cycle is still a cycle!
When we do this in the middle, we get:
(9,2,*)
(*,7,*)
which then moves in a different direction:
(9,2,5)
(*,7,3)
(9,2,5)
(4,7,3)
I'm wondering if that kind of swapping can be used to find "better branches".
Bah, but there is no guarantee that the new cycle is anywhere similar to the same length.
(9,7,5) has compliment (2,2,4)
So we have:
(9,7,5)
(2,2,4)
Now, note that for any pair of such cycles, we can swap an from the top to the bottom, and the top cycle is still a cycle!
When we do this in the middle, we get:
(9,2,*)
(*,7,*)
which then moves in a different direction:
(9,2,5)
(*,7,3)
(9,2,5)
(4,7,3)
I'm wondering if that kind of swapping can be used to find "better branches".
Bah, but there is no guarantee that the new cycle is anywhere similar to the same length.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision  BR
Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.
Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

 Posts: 22
 Joined: Sun Jun 22, 2008 1:13 pm UTC
Re: Number problem
I see.
The new cycle doesn't have to be the same length though, as long as it doesn't exceed the upper limit of 7.
I was thinking of something rather similar it seems. Let X be the smallest cycle x1 > ... > x1 in A (the positive members of S). Then 3 <= X <= 7, because 3 <= A <= 7 and X = 1 > 0 in S, X = 2 > S has an inverse.
Now let xi and xj be such that xi = xi+1 + z and xj = xj+1 + z and suppose that i < j. Now there are a few cases I was thinking of addressing.
 Suppose z = xk in X. Then there exists a cycle inside of X which is smaller than X itself. This is not possible since I chose X to be the smallest cycle in A.
 Suppose X < 7. Then there can possibly be m = A  X members of A which are not in X. So suppose that z in A \ X. If we expand z m times, we must arrive at a member of X (since there are only m members of A left which are not in X). Then we can construct a new cycle which includes z and might possibly be larger than X but must be smaller or equal than 7.
The final case is when z is in B. I don't know how to approach that one.
Does this make sense?
Edit: I reread it and concluded, once again, that graph theory proof are totally unreadable without some drawing or example. So I'll just give you one.
Consider S = {8, 4, 3, 1, 2, 5, 7, 9}. Then S = 8 and believe me that it satisfies the important property. Then A = {2, 5, 7, 9} and we found the cycle 9 > 7 > 5 > 9 with complement {2, 2, 4}. In this case, xi = 9, xj = 7 and z = 2. Note that X = 3 < 4 = A, so m = 1. Here, z is in amongst the remaining members of A which are not in X, so z in X \ A. Note that if we expand z, we get z = 5 + 3. 5 is a member of X, which is to be expected after m expansions. Now we can construct the cycle z > 5 > 9 > z (because 9 = xi) which satisfies our criterium.
The trick here is that the length of such a newly found cycle can not exceed A, which is what we wanted.
The new cycle doesn't have to be the same length though, as long as it doesn't exceed the upper limit of 7.
I was thinking of something rather similar it seems. Let X be the smallest cycle x1 > ... > x1 in A (the positive members of S). Then 3 <= X <= 7, because 3 <= A <= 7 and X = 1 > 0 in S, X = 2 > S has an inverse.
Now let xi and xj be such that xi = xi+1 + z and xj = xj+1 + z and suppose that i < j. Now there are a few cases I was thinking of addressing.
 Suppose z = xk in X. Then there exists a cycle inside of X which is smaller than X itself. This is not possible since I chose X to be the smallest cycle in A.
 Suppose X < 7. Then there can possibly be m = A  X members of A which are not in X. So suppose that z in A \ X. If we expand z m times, we must arrive at a member of X (since there are only m members of A left which are not in X). Then we can construct a new cycle which includes z and might possibly be larger than X but must be smaller or equal than 7.
The final case is when z is in B. I don't know how to approach that one.
Does this make sense?
Edit: I reread it and concluded, once again, that graph theory proof are totally unreadable without some drawing or example. So I'll just give you one.
Consider S = {8, 4, 3, 1, 2, 5, 7, 9}. Then S = 8 and believe me that it satisfies the important property. Then A = {2, 5, 7, 9} and we found the cycle 9 > 7 > 5 > 9 with complement {2, 2, 4}. In this case, xi = 9, xj = 7 and z = 2. Note that X = 3 < 4 = A, so m = 1. Here, z is in amongst the remaining members of A which are not in X, so z in X \ A. Note that if we expand z, we get z = 5 + 3. 5 is a member of X, which is to be expected after m expansions. Now we can construct the cycle z > 5 > 9 > z (because 9 = xi) which satisfies our criterium.
The trick here is that the length of such a newly found cycle can not exceed A, which is what we wanted.
Re: Number problem
Nightbreeze wrote:So suppose that z in A \ X. If we expand z m times, we must arrive at a member of X (since there are only m members of A left which are not in X). Then we can construct a new cycle which includes z and might possibly be larger than X but must be smaller or equal than 7.
Can you be sure it won't introduce another conflict ?

 Posts: 22
 Joined: Sun Jun 22, 2008 1:13 pm UTC
Re: Number problem
Doraki wrote:Nightbreeze wrote:So suppose that z in A \ X. If we expand z m times, we must arrive at a member of X (since there are only m members of A left which are not in X). Then we can construct a new cycle which includes z and might possibly be larger than X but must be smaller or equal than 7.
Can you be sure it won't introduce another conflict ?
No.
: (
But I'm pretty sure we can repeat this process until the conflicting z is not a member of A.
 Yakk
 Poster with most posts but no title.
 Posts: 11127
 Joined: Sat Jan 27, 2007 7:27 pm UTC
 Location: E pur si muove
Re: Number problem
A set S is said to be closed under splitting if, for all s in S, there are x, y in S such that x+y = s.
Lemma: There is a subset X of S, where S is closed under spliting, such that sum(X) = 0.
Let S be a set closed under splitting.
For each element a of S, if S\{a} is closed under split, then we have reduced the problem to a smaller sized S, and the induction follows easily.
As such, we are only concerned about the S such that, for each a, S\{a} is not closed under splitting. As S is closed under splitting, there exists an s in S such that s = a+b, and this choice of a and b is unique for that s (ie, there are no values x,y in S such that x+y = S unless one of x or y is a, and the other is b).
This is true of each element a of S.
So we get:
s_1 = a_1 + b_1
...
s_n = a_n + b_n
where the a_i are unique.
Let's assume that for some i, j, s_i = s_j. Then:
s_i = a_i + b_i = a_j + b_j
But we have that the splits are unique. As such, we have that the {s_i} are unique as well!
The {b_i} can, however, have duplicates.
Hurm.
Lemma: There is a subset X of S, where S is closed under spliting, such that sum(X) = 0.
Let S be a set closed under splitting.
For each element a of S, if S\{a} is closed under split, then we have reduced the problem to a smaller sized S, and the induction follows easily.
As such, we are only concerned about the S such that, for each a, S\{a} is not closed under splitting. As S is closed under splitting, there exists an s in S such that s = a+b, and this choice of a and b is unique for that s (ie, there are no values x,y in S such that x+y = S unless one of x or y is a, and the other is b).
This is true of each element a of S.
So we get:
s_1 = a_1 + b_1
...
s_n = a_n + b_n
where the a_i are unique.
Let's assume that for some i, j, s_i = s_j. Then:
s_i = a_i + b_i = a_j + b_j
But we have that the splits are unique. As such, we have that the {s_i} are unique as well!
The {b_i} can, however, have duplicates.
Hurm.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision  BR
Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.
Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

 Posts: 22
 Joined: Sun Jun 22, 2008 1:13 pm UTC
Re: Number problem
Yakk wrote: As S is closed under splitting, there exists an s in S such that s = a+b, and this choice of a and b is unique for that s (ie, there are no values x,y in S such that x+y = S unless one of x or y is a, and the other is b).
This is true of each element a of S.
I am not convinced. Could you elaborate on this?
Who is online
Users browsing this forum: No registered users and 10 guests