Number problem

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

Nightbreeze
Posts: 22
Joined: Sun Jun 22, 2008 1:13 pm UTC

Number problem

Postby Nightbreeze » Sun Jun 22, 2008 1:28 pm UTC

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 non-empty 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.

Robin S
Posts: 3579
Joined: Wed Jun 27, 2007 7:02 pm UTC
Location: London, UK
Contact:

Re: Number problem

Postby Robin S » Sun Jun 22, 2008 3:12 pm UTC

If this is homework help, you should make that clear.
This is a placeholder until I think of something more creative to put here.

Nightbreeze
Posts: 22
Joined: Sun Jun 22, 2008 1:13 pm UTC

Re: Number problem

Postby Nightbreeze » Sun Jun 22, 2008 3:56 pm UTC

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.

User avatar
DubioserKerl
Posts: 71
Joined: Sat Jun 07, 2008 8:23 am UTC

Re: Number problem

Postby DubioserKerl » Sun Jun 22, 2008 6:19 pm UTC

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
Image

Nightbreeze
Posts: 22
Joined: Sun Jun 22, 2008 1:13 pm UTC

Re: Number problem

Postby Nightbreeze » Sun Jun 22, 2008 6:23 pm UTC

Whoops. No idea where that A came from, it's supposed to be an S.

Edited.

User avatar
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

Postby jestingrabbit » Sun Jun 22, 2008 7:21 pm UTC

This looks wrong

Spoiler:
[imath]S=\{0,1,2,3,4,5,6,7,8,9,10,11,12,13,14\}[/imath] satisfies the hypothesis but not the conclusion.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

Nightbreeze
Posts: 22
Joined: Sun Jun 22, 2008 1:13 pm UTC

Re: Number problem

Postby Nightbreeze » Sun Jun 22, 2008 7:23 pm UTC

Take [imath]T = \{0\}[/imath].

User avatar
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

Postby jestingrabbit » Sun Jun 22, 2008 7:25 pm UTC

Gah, I was thinking |T|=7 not \le. my bad.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

User avatar
Torn Apart By Dingos
Posts: 817
Joined: Thu Aug 03, 2006 2:27 am UTC

Re: Number problem

Postby Torn Apart By Dingos » Sun Jun 22, 2008 7:25 pm UTC

You should require T to be nonempty. Otherwise T={} works for any S (the empty sum is 0).

Nightbreeze
Posts: 22
Joined: Sun Jun 22, 2008 1:13 pm UTC

Re: Number problem

Postby Nightbreeze » Sun Jun 22, 2008 7:29 pm UTC

Good point. Edited.

User avatar
spdqbr
Posts: 171
Joined: Sat Mar 08, 2008 1:41 am UTC
Location: A shaker of salt

Re: Number problem

Postby spdqbr » Mon Jun 23, 2008 2:30 pm UTC

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

Nightbreeze
Posts: 22
Joined: Sun Jun 22, 2008 1:13 pm UTC

Re: Number problem

Postby Nightbreeze » Mon Jun 23, 2008 2:53 pm UTC

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 well-chosen 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.

AnotherUser
Posts: 47
Joined: Sun Jun 22, 2008 3:54 am UTC

Re: Number problem

Postby AnotherUser » Mon Jun 23, 2008 3:30 pm UTC

S={−6,−4,−3,1,2,4}

I don't see an a and b in S such that a+b= -6

Nightbreeze
Posts: 22
Joined: Sun Jun 22, 2008 1:13 pm UTC

Re: Number problem

Postby Nightbreeze » Mon Jun 23, 2008 3:38 pm UTC

a and b don't have to be distinct. In this case, choose a = b = -3

User avatar
z4lis
Posts: 767
Joined: Mon Mar 03, 2008 10:59 pm UTC

Re: Number problem

Postby z4lis » Mon Jun 23, 2008 5:18 pm UTC

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 well-chosen 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.

User avatar
jaap
Posts: 2094
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

Re: Number problem

Postby jaap » Mon Jun 23, 2008 5:40 pm UTC

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.

Nightbreeze
Posts: 22
Joined: Sun Jun 22, 2008 1:13 pm UTC

Re: Number problem

Postby Nightbreeze » Mon Jun 23, 2008 6:12 pm UTC

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.

User avatar
SimonM
Posts: 280
Joined: Sat Jul 21, 2007 4:49 pm UTC
Location: Guernsey, CI
Contact:

Re: Number problem

Postby SimonM » Mon Jun 23, 2008 6:28 pm UTC

I think the OP knows where this problem comes from

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?

Nightbreeze
Posts: 22
Joined: Sun Jun 22, 2008 1:13 pm UTC

Re: Number problem

Postby Nightbreeze » Mon Jun 23, 2008 6:36 pm UTC

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.

User avatar
SimonM
Posts: 280
Joined: Sat Jul 21, 2007 4:49 pm UTC
Location: Guernsey, CI
Contact:

Re: Number problem

Postby SimonM » Mon Jun 23, 2008 6:42 pm UTC

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?

Nightbreeze
Posts: 22
Joined: Sun Jun 22, 2008 1:13 pm UTC

Re: Number problem

Postby Nightbreeze » Mon Jun 23, 2008 7:24 pm UTC

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.

User avatar
SimonM
Posts: 280
Joined: Sat Jul 21, 2007 4:49 pm UTC
Location: Guernsey, CI
Contact:

Re: Number problem

Postby SimonM » Mon Jun 23, 2008 7:29 pm UTC

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?

Nightbreeze
Posts: 22
Joined: Sun Jun 22, 2008 1:13 pm UTC

Re: Number problem

Postby Nightbreeze » Mon Jun 23, 2008 9:02 pm UTC

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.

User avatar
SimonM
Posts: 280
Joined: Sat Jul 21, 2007 4:49 pm UTC
Location: Guernsey, CI
Contact:

Re: Number problem

Postby SimonM » Mon Jun 23, 2008 9:27 pm UTC

No, its just before the magazine's deadlines run out on submitting solutions.

EDIT: Yay 256 posts :)
mosc wrote:How did you LEARN, exactly, to suck?

Nightbreeze
Posts: 22
Joined: Sun Jun 22, 2008 1:13 pm UTC

Re: Number problem

Postby Nightbreeze » Mon Jun 23, 2008 9:41 pm UTC

Do you have a take on the problem as well? :P gotta break the power of 2 limit some time.

User avatar
z4lis
Posts: 767
Joined: Mon Mar 03, 2008 10:59 pm UTC

Re: Number problem

Postby z4lis » Mon Jun 23, 2008 11:36 pm UTC

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 (n-1)/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.
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.

Cauchy
Posts: 602
Joined: Wed Mar 28, 2007 1:43 pm UTC

Re: Number problem

Postby Cauchy » Tue Jun 24, 2008 4:38 am UTC

Before worrying about getting a subset of the right size, it seems important to me that we show that there exists any non-empty 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.

User avatar
Doraki
Posts: 69
Joined: Sun Feb 03, 2008 9:52 am UTC
Location: France
Contact:

Re: Number problem

Postby Doraki » Tue Jun 24, 2008 5:08 pm UTC

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 ?
Spoiler:
It's possible to split the numbers in 2 categories,
such that any number in one category has a decomposition using at least one number in the same category
(for example, use the positive ones and the negative ones)
Look in the smallest category and find a cycle.
It means you have a1=b2+a2, a2=b3+a3 ... an=b1+a1, and you can get that the sum of the bi is zero.
But they may not be all distinct.

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)

Nightbreeze
Posts: 22
Joined: Sun Jun 22, 2008 1:13 pm UTC

Re: Number problem

Postby Nightbreeze » Tue Jun 24, 2008 5:38 pm UTC

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.

User avatar
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

Postby Yakk » Thu Jun 26, 2008 8:17 pm UTC

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 split-closed.

Hand-wavy inductive stuff goes here.

For any element {z} of S, define Z = S\{z}. Then either Z is split-closed, or is not.

If Z is split-closed, then we are done, inductively (as all smaller split-closed sets admit a sufficiently small zero-summing set). So the hand-waved inductive structure means we can assume that for each z, Z is not split-closed.

Assuming Z is not split-closed, 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=a-b 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_1-b_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.

Nightbreeze
Posts: 22
Joined: Sun Jun 22, 2008 1:13 pm UTC

Re: Number problem

Postby Nightbreeze » Thu Jun 26, 2008 11:33 pm UTC

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 = x1, ... xk. Let k be the smallest k with this property. Then there exist Z = z1, ... zk such that

x1 = x2 + z1 = x3 + z2 + z1 = ... = x1 + zk + ... + z1.

The the sequence z1, ..., zk 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 xi and xj with i =/= j such that xi = xi+1 + z and xj = xj+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 xi, xj 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!

User avatar
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

Postby Yakk » Fri Jun 27, 2008 3:09 am UTC

(9,7,5) has compliment (2,2,-4)
But (9,2,5) has compliment (7,-3,-4)

9 = 7+2 = 7-3+5 = 7-3-4+9
Thus 7-3-4 = 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.

User avatar
root
Posts: 88
Joined: Sun May 18, 2008 11:55 pm UTC

Re: Number problem

Postby root » Fri Jun 27, 2008 3:55 am UTC

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.
  • 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
Now we can let T be any of the prime modulus less than or equal to 7 (but not 2). We could have let T be Z mod 11 or Z mod 13, but the problem specifically asks for less than 7, so meh.

In other words, T=Z mod 7, or Z mod 5, or Z mod 3.

Nightbreeze
Posts: 22
Joined: Sun Jun 22, 2008 1:13 pm UTC

Re: Number problem

Postby Nightbreeze » Fri Jun 27, 2008 9:18 am UTC

Yakk wrote:(9,7,5) has compliment (2,2,-4)
But (9,2,5) has compliment (7,-3,-4)

9 = 7+2 = 7-3+5 = 7-3-4+9
Thus 7-3-4 = 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.

User avatar
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

Postby Yakk » Fri Jun 27, 2008 1:35 pm UTC

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.
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.

Nightbreeze
Posts: 22
Joined: Sun Jun 22, 2008 1:13 pm UTC

Re: Number problem

Postby Nightbreeze » Fri Jun 27, 2008 2:00 pm UTC

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.

User avatar
Doraki
Posts: 69
Joined: Sun Feb 03, 2008 9:52 am UTC
Location: France
Contact:

Re: Number problem

Postby Doraki » Fri Jun 27, 2008 4:10 pm UTC

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 ?

Nightbreeze
Posts: 22
Joined: Sun Jun 22, 2008 1:13 pm UTC

Re: Number problem

Postby Nightbreeze » Fri Jun 27, 2008 5:28 pm UTC

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.

User avatar
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

Postby Yakk » Fri Jun 27, 2008 6:21 pm UTC

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.
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.

Nightbreeze
Posts: 22
Joined: Sun Jun 22, 2008 1:13 pm UTC

Re: Number problem

Postby Nightbreeze » Fri Jun 27, 2008 6:29 pm UTC

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?


Return to “Mathematics”

Who is online

Users browsing this forum: No registered users and 8 guests