wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> putnam exam (pure math) >> Number problem
        
(Message started by: NightBreeze on Jun 21^st, 2008, 11:11am)

Title: Number problem
Post by NightBreeze on Jun 21^st, 2008, 11:11am

I offer you the following problem.

---------------------------------------------------------
Consider a set S http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/subset.gif http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/bbz.gif with |S| = 15 and the following property:

http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/forall.gif s http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/in.gif S, http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/exists.gif a,b http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/in.gif S such that s = a+b

Prove that for every such S, there exists a non-empty subset T http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/subset.gif S with |T| <= 7 such that the sum of the elements of T equals zero.
---------------------------------------------------------

I don't know the proof.

There is a b-side:

---------------------------------------------------------
Prove that for arbitrary S http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/subset.gif http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/bbz.gif with |S|=16, this statement is not true.
---------------------------------------------------------

I have found a counterexample to prove this.

Good luck!

Title: Re: Number problem
Post by Eigenray on Jun 24^th, 2008, 12:34am

I don't know but in theory it's a finite computation:

Let s = (s₁,...,s_n) list the elements of S. For each i, there exist f(i), g(i) such that s_i = s_f(i) + s_g(i). Then there is an nxn matrix A with As=0, namely A = I - http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif (E_i,f(i)+E_i,g(i)), where E_i,j is the matrix with a 1 in position (i,j) and 0s elsewhere.

We want to show that either two elements of S are equal, or that some subset of them sums to zero. In other words, we want to show that any element in the kernel of A must lie in one of a finite number of hyperplanes. However, since we are working over an infinite field, the condition ker A http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/subseteq.gif http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/cup.gif H_i is equivalent to ker A http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/subseteq.gif H_i for some i.

So the problem is equivalent to proving that for each possible matrix A, at least one of a finite number of vectors is in its row span, namely a vector with either
(a) one 1, one -1, and the rest 0s; or
(b) between one and seven 1s, and the rest 0.

Of course, there are 105¹⁵ possibilities for A, so this isn't exactly feasible.

Here are some sets of 15 elements such that each is a sum of two others, and such that no two of them sum to 0:
{-17, -15, -14, -11, -8, -4, -2, 1, 3, 6, 9, 10, 13, 18, 20}
{-21, -16, -11, -9, -8, -5, -3, 2, 4, 6, 7, 10, 12, 13, 19}
{-22, -16, -12, -9, -8, -6, 2, 3, 5, 7, 10, 13, 14, 15, 18}
{-22, -18, -16, -12, -10, -1, 2, 3, 4, 7, 8, 9, 11, 13, 20}
{-8, -7, -5, -4, -3, -1, 2, 6, 9, 10, 13, 14, 18, 22, 23}
{-16, -14, -13, -12, -10, -8, -5, 1, 2, 3, 4, 9, 18, 22, 23}
{-20, -15, -8, -7, -5, -4, -1, 2, 3, 9, 11, 13, 16, 18, 24}
{-22, -15, -14, -12, -8, 1, 2, 4, 5, 6, 7, 10, 13, 19, 24}
{-23, -20, -18, -15, -6, -5, -4, 1, 2, 3, 11, 13, 17, 22, 24}
{-26, -18, -16, -12, -8, -2, -1, 4, 5, 9, 10, 11, 14, 17, 19}
{-10, -7, -4, -3, 1, 2, 5, 6, 12, 14, 15, 16, 18, 20, 26}
{-21, -19, -13, -11, -10, -6, -2, 3, 8, 9, 12, 14, 15, 22, 27}
{-19, -12, -11, -7, -6, -5, -1, 2, 4, 8, 21, 23, 24, 25, 27}
{-27, -19, -16, -8, -5, -3, 2, 4, 7, 11, 15, 21, 22, 23, 26}
{-27, -19, -13, -8, -6, -2, -1, 7, 9, 11, 12, 14, 16, 24, 25}
{-28, -21, -18, -16, -14, -10, -5, 1, 2, 3, 7, 8, 11, 12, 23}
{-28, -25, -23, -13, -4, -3, -2, 1, 5, 6, 10, 16, 18, 20, 24}
{-24, -23, -20, -12, -11, -10, -1, 3, 4, 7, 8, 14, 15, 22, 28}
{-28, -15, -13, -12, -8, -7, -5, 2, 4, 9, 16, 17, 18, 21, 25}
{-20, -18, -16, -15, -12, -4, -3, 7, 8, 9, 21, 24, 25, 28, 29}
{-15, -9, -7, -6, -3, 1, 4, 5, 8, 10, 11, 13, 17, 19, 30}
{-30, -25, -22, -16, -5, -3, 4, 7, 8, 9, 11, 12, 13, 19, 23}
{-30, -24, -21, -20, -15, -11, -5, 1, 6, 7, 8, 9, 10, 17, 25}

Title: Re: Number problem
Post by NightBreeze on Jun 24^th, 2008, 10:30am

Well, it's good to see you're taking a different approach than I had in mind. Perhaps this road will lead somewhere
It hasn't made thinking about the problem any easier for me though, I must admit. The brilliant insight that will solve it still eludes me. But perhaps it works for you. Do you plan to work on it some more?

Noone I showed this problem to has ever been able to proof it. It's ridiculous.

And how did you generate this amount of 15 element sets. By computer? :P

Title: Re: Number problem
Post by towr on Jun 24^th, 2008, 11:36am

I haven't gotten very far. But if we assume the majority of numbers are positive (which we can do without loss of generality, because cases are symmetrical with respect to switching the sign of all numbers), then I can at least say we only need to look at cases with at least 4 numbers smaller than 0 and at most 7.
First we can exclude the case with 0 http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/in.gif S, because that trivially gives T = {0}.
Now, if there were less than three negative number, then the minimum couldn't be the sum of two numbers. And if there were exactly three, than we'd have x=y+z with x<y<z, and y could only be x+p for some positive number p. But then z = -p, so picking T = {z,p} fits the bill.
So the only cases that would still need to be looked at are with 4,5,6,7 negative numbers.

[edit]
So suppose there are 4 numbers < 0. x < y < z < w < 0, and we don't have x = y + z (because that would give the same result as before), then either x = y + w, or x = z + w, and y = z + w or y = x + p for some positive p.
case:
x = y + w y = x + p => 0 = w+p
x = y + w y = z + w =>
subcase:
w = x+p -> 0 = y+p
w = y+q -> 0 = z+q
w = z+r ->
subsubcase:
  z = x+s -> 0 = y+s+r
  z = y+t -> 0 = w+t
x = z + w y = x + p =>
subcase:
w = x+q -> 0 = z+q
w = y+r -> 0 = z+p+r
w = z+s ->
subsubcase:
z = x+t -> 0 = w+t
   z = y+u -> 0 = z+p+u+s

So what's left is cases with 5,6 or 7 negative numbers
I suppose they might be handled in a similar way, but it's a fair bit of work..
[/edit]

Title: Re: Number problem
Post by NightBreeze on Jun 24^th, 2008, 12:25pm

This is more along the lines of how I was tackling it.

on 06/24/08 at 11:36:27, towr wrote:

Now, if there were less than three negative number, then the minimum couldn't be the sum of two numbers. And if there were exactly three, than we'd have x=y+z with x<y<z, and y could only be x+p for some positive number p. But then z = -p, so picking T = {z,p} fits the bill.

I don't think this is true. Your first statement is false because if S contains less then three negative numbers (2 for instance), then the smallest can be double the largest. What it does imply is that S must contain an inverse (or 0...).

Now let's assume that S contains neither 0 nor an inverse of another member of S, for it would make choosing T fairly trivial. With this assumption, it can be proven that S has to contain at least 3 negative and at least 3 positive numbers. So it's possible for S to have exactly 3 negative numbers without any inverses.
Example:

S = {-6,-5,-3,1,2,4,8,16,...}

You logic misses something, but I find it hard to point out exactly what it is :P. You conclude that an inverse must be present too quickly it seems. Perhaps you skip over the fact that a member of S might be written as the sum of twice another member...

Let's keep working on it!

Title: Re: Number problem
Post by towr on Jun 24^th, 2008, 12:29pm

on 06/24/08 at 12:25:39, NightBreeze wrote:

I don't think this is true. Your first statement is false because if S contains less then three negative numbers (2 for instance), then the smallest can be double the largest.

Hmm, yeah, it seems I assumed that each number in S had to be the sum of two unique numbers in S.
That messes up the rest of the story a bit.

Title: Re: Number problem
Post by NightBreeze on Jun 24^th, 2008, 12:57pm

on 06/24/08 at 12:29:35, towr wrote:

Hmm, yeah, it seems I assumed that each number in S had to be the sum of two unique numbers in S.
That messes up the rest of the story a bit.

Many pitfalls on this one. Don't let it discourage you! ^^

We need some new ideas before we can proceed. I don't think I can work with the problem as stated by Eigenray, but perhaps he can figure something out.

Maybe a graph can be useful? We have to figure out some properties of the internal structure of such an S. For instance, for every S, there are at least three members which are not the double of another. Maybe those are useful when 'expanding'?

Title: Re: Number problem
Post by Eigenray on Jun 24^th, 2008, 3:59pm

For the matrix A I'm talking about, I-A is the adjacency matrix of the graph you're talking about, if we form edges i -> f(i) and i -> g(i).

For n=6, the set {-4, -2, -1, 3, 5, 6} is essentially unique. Up to scalar multiplication, it is the only set of 6 elements, with each a sum of two others, and such that no element is the negative of another.

For n=7, however, this is the complete list of solutions:
{-10, -9, -5, 1, 2, 4, 6}
{-10, -8, -5, 1, 2, 3, 6}
{-10, -7, -5, 1, 2, 3, 6}
{-8, -7, -4, 1, 2, 3, 5}
{-8, -6, -4, 1, 2, 3, 5}
{-8, -5, -4, 1, 2, 3, 6}
{-8, -5, -4, 1, 3, 6, 7}
{-8, -4, -2, 1, 3, 6, 7}
{-8, -4, -2, 1, 5, 6, 7}
{-8, -4, -2, 3, 5, 6, 9}
{-8, -4, -2, 3, 6, 7, 9}
{-6, -5, -3, 1, 2, 4, 8}
{-4, -3, -2, 1, 5, 6, 7}
{-4, -3, -2, 1, 5, 7, 10}
{-4, -3, -2, 1, 5, 8, 10}
{-4, -2, -1, 3, 5, 6, 8}
{-4, -2, -1, 3, 5, 6, 9}
{-4, -2, -1, 3, 5, 6, 10}
{-4, -2, -1, 3, 5, 6, 11}
{-4, -2, -1, 3, 5, 6, 12}
{-4, -2, -1, 3, 5, 7, 8}
{-4, -2, -1, 3, 5, 9, 10}
{-4, -2, -1, 3, 6, 7, 9}
{-4, -2, -1, 3, 7, 8, 10}
{-4, -2, -1, 3, 7, 9, 10}.

In each case there is a set of three which sum to 0. But you can see how this could quickly become infeasible for larger n (the list for n=15 was generated by picking matrices at random).

Title: Re: Number problem
Post by NightBreeze on Jun 25^th, 2008, 2:43am

on 06/24/08 at 15:59:32, Eigenray wrote:

For the matrix A I'm talking about, I-A is the adjacency matrix of the graph you're talking about, if we form edges i -> f(i) and i -> g(i).

But in the case of I-A, if an element is double another element, the matrix will have a 2 in a certain position, which is not allowed.

Can we proof that there exists no more than 1 set S with |S| = 6 (no zero, no inverses) and no more than 25 with |S| = 7? It's probably not very useful but I'm curious nonetheless.

In the case of |S| = 6, the adjacency matrix looks like this:

[ 0 1 0 0 0 0 ]
[ 0 0 1 0 0 0 ]
[ 1 0 0 1 0 0 ]
[ 0 1 0 0 1 0 ]
[ 0 0 1 0 0 1 ]
[ 0 0 0 1 0 0 ]

This is certainly interesting. Eigenray's I-A would look the same, only with 2's instead of 1's in the rows with only one non-zero entry.

So why is this the only configuration which will give a 'working' S? Besides brute-forcing and using the fact that gcd(s1, ... , s6) = 1.

There are only 3 possible subsets of this S which sum to zero, all of which have size 3:

{-2, -1, 3}
{-4, -1, 5}
{-4, -2, 6}

I have also shown that for |S| = 2n with n some natural number, an S can always be found of which the smallest subset T which sums to zero has cardinality n. For example, in the case of |S| = 16,

S = {–254, –253, –251, –247, –239, –223, –191, –127, 1, 2, 4, 8, 16, 32, 64, 128}

Using succesive powers of 2, you can see that we can create sets of arbitrary size with this. This means that the upper bound on the size of T can not drop below n for any even |S|. This also means that for odd |S|, it can't drop below n either. Say |S| = 2n + 1. Construct an S, as above, with size 2n and then double the smallest negative number. This number is not useful for summing to zero, because the sum of all positive numbers is 2^n-1 which is smaller than -2ⁿ⁺¹.

I don't know if it's useful, but there it is anyways. In drawing the graph of S₆, I couldn't find any property which would indicate how the zero-sum subsets might be constructed. But I'll keep looking.

Title: Re: Number problem
Post by Eigenray on Jun 25^th, 2008, 4:54am

on 06/25/08 at 02:43:56, NightBreeze wrote:

But in the case of I-A, if an element is double another element, the matrix will have a 2 in a certain position, which is not allowed.

The entries of an adjacency matrix are the number of edges from one vertex to another. For a non-simple graph they can be larger than 1.

Quote:

Can we proof that there exists no more than 1 set S with |S| = 6 (no zero, no inverses) and no more than 25 with |S| = 7?

For |S|=6 it should be possible, since there aren't that many possible graphs. |S|=7 is probably infeasible to enumerate by hand.

For |S|=8, there are precisely 510 sets with no zero and no pair of negatives: 278 with a 3-5 split, and 232 with 4-4. They are attached. These are the only ones which don't have a subset of size 3 summing to zero:
{-16, -12, -8, 1, 2, 4, 5, 9}
{-8, -6, -4, 1, 2, 9, 11, 13}
{-8, -4, -2, -1, 7, 11, 13, 14}
{-7, -4, -3, -2, 1, 8, 12, 16}
In each case there is a subset of size 4 summing to zero.

Title: Re: Number problem
Post by NightBreeze on Jun 25^th, 2008, 1:52pm

on 06/25/08 at 04:54:04, Eigenray wrote:

The entries of an adjacency matrix are the number of edges from one vertex to another. For a non-simple graph they can be larger than 1.

Ah, of course you are correct.

I actually meant proving these things using properties of S, instead of brute force ^^ That's the reason I would want to try and prove it.. to find more properties.

Edit:

My most recent thoughts are pursuing this: Say |S| = 15 (no zero, no negatives, etc) and define A = {s in S | s positive}, B = {s in S | s negative}. Note that S = A union B. Without loss of generality, let there be more positive numbers than negative numbers in S. We take a look at A with 3 <= |A| <= 7. Define G to be the an unoriented graph in A. Let x and y be adjacent if there exists a z in S such that x = y + z. This means that every vertex is adjacent to at least one edge. Then, because of the finiteness of A, there exists a cycle x₁, ..., x_k. Assume that k is minimal with this property. Then there exists z_i in S such that

x₁ = x₂ + z₁ = x₃ + z₂ + z₂ = ... = x₁ + z_k + ... + z₁.

This means that the z_i sum up to zero and there can be no more than 7 terms, because the cycle was of length 7 maximum. Now all we have to show is that it's always possible to substitute number for other numbers to make sure they are all distinct. Is that doable?

Can you please show me a set S and a starting point x₁ such that the cycle contains double? Every cycle I tried, including those not entirely inside A or B does not contain doubles :O. Perhaps we can show that substituting is not even necessary.

Edit2: It seems it's very possible to reach another cycle in the graph and getting stuck...

Edit3: An unoriented graph doesn't seem like the way to go. It has to be oriented or cycles can appear too quicky. Consider 9 = 6 + 3 and of course 6 = 3 + 3. Then there exists a cycle 9-6-3-9 which is of no use.

Edit4: If we orient the graph like this it seems to Work. If x = y + z, then there is an edge x -> y and x -> z. If we can find a cycle using this definition (and there must be), then it can necessarily be used to sum to zero. Now to show that either all elements are distinct, or that they can be made distinct.

Edit5: I think it's impossible to get double elements in the expansion if we take the smallest cycle in both A and B. If we were to find a double, then a smaller cycle would exist , which is not possible. I believe this might be the complete proof, except for the fact that smallest cycle might lie in the set with more than 7 members, thus not guaranteeing it's length is <= 7

Title: Re: Number problem
Post by Aryabhatta on Jun 25^th, 2008, 4:42pm

on 06/24/08 at 00:34:36, Eigenray wrote:

<snip>

So the problem is equivalent to proving that for each possible matrix A, at least one of a finite number of vectors is in its row span, namely a vector with either
(a) one 1, one -1, and the rest 0s; or
(b) between one and seven 1s, and the rest 0.

I am not able to see why this must be true.

If rank A = 14 then it is true, as every vector orthogonal to any non-zero vector in the null space must be in the orthogonal complement (hence row space).

If rank A < 14 then it need not be true, right?

What am I missing?

Title: Re: Number problem
Post by Eigenray on Jun 25^th, 2008, 4:54pm

The key point is that if a subspace W is contained in a finite union of subspaces V_i, and the field is infinite, then W must actually be contained in a single V_i. So if we have a finite list of vectors v_i such that any vector in ker A is orthogonal to some v_i, then there must be a single i such that all of ker A is orthogonal to v_i, and so v_i is in the row space of A.

But this direction only tells us that such a proof is possible. That is, assuming the result is true, then for any possible matrix, we can always find one of these v_i in its row space. The converse is obvious: if we can do this, then we have proved the result.

Title: Re: Number problem
Post by Aryabhatta on Jun 25^th, 2008, 7:12pm

on 06/25/08 at 16:54:37, Eigenray wrote:

... So if we have a finite list of vectors v_i such that any vector in ker A is orthogonal to some v_i...

I guess we only need to show/assume this.

The problem as stated only talks about vectors with integer co-ordinates. So, I think we also need to prove that any vector in ker A is orthogonal to some v_i, which seems true as I think we can show that the result of the problem is true for reals if it is true for integers (extend to rationals and then perhaps use some kind of density/real = vector over Q arguments). Or maybe just consider our field to be Q...

And I think I get your point: pretty neat observation, Eigenray!

Title: Re: Number problem
Post by Eigenray on Jun 25^th, 2008, 8:01pm

on 06/25/08 at 19:12:02, Aryabhatta wrote:

Quote:

So if we have a finite list of vectors v_i such that any vector in ker A is orthogonal to some v_i

I guess we only need to show/assume this.

But this is exactly what the problem is asking us to prove: if we have a set [vector] with the property that any element is the sum of two others [in ker A], then either two elements are the same [orthogonal to some (..1...-1..)], or a subset of it sums to zero [orthogonal to some (..1...1...1..)].

Since we can turn this into a statement about the ranks of certain integer matrices, it's independent of the field, as long as it has characteristic 0. (Is it still true in characteristic p?)

While it suffices to prove it for integers (and it may certainly be easier there), in general the numbers don't have to break up into positive and negative. For example, here are some 2-dimensional sets:
{-10+i, -9+i, -8+i, -7+i, -3, -2, -1+i, -1, i, 1, 3, 4, 5, 7+i, 8}
{-7+2 i, -5+i, -3+i, -3, -2+i, -1+i, -1, i, 1, 2, 2-i, 4, 4-2 i, 6, 8}
{-2-3 i, -2-2 i, -2-i, -2, -2+i, -1, -2 i, -i, i, 1-3 i, 1+i, 1+2 i, 3, 5+i, 5+2 i}
{-4+2 i, -2+2 i, -2+i, -2, -1+i, i, -i, 1, 1-i, 1-2 i, 2, 2-i, 2-2 i, 3, 3-i}
Note that 'i' could be replaced by any field element, as long as the entries remain distinct. (I haven't yet found any 2-dimensional sets that have no pairs summing to zero though.)

Title: Re: Number problem
Post by Aryabhatta on Jun 25^th, 2008, 8:10pm

on 06/25/08 at 20:01:34, Eigenray wrote:

I guess we only need to show/assume this. But this is exactly what the problem is asking us to prove

Yes, I was only trying to fill in the gaps (of my understanding) in your proof of equivalence of the statement of the problem and the statement that Row Span of A contains one of the finite set of vectors.

Title: Re: Number problem
Post by Eigenray on Jun 25^th, 2008, 9:12pm

Actually it is false in characteristic p:
{1, 7, 12, 13, 17, 18, 20} mod 23
has no subset of size http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gif 3 summing to 0. The associated adjacency matrix is

0 0 2 0 0 0 0
0 0 0 1 1 0 0
0 0 0 0 1 1 0
1 0 1 0 0 0 0
0 0 0 0 0 0 2
1 0 0 0 1 0 0
0 1 0 1 0 0 0,

and the matrix A has determinant -23. Over the integers then, there is no solution. But mod 23, A has rank 6, and adding any of the vectors in question increases its rank to 7. But adding {1, 1, 0, 0, 0, 1, 1} does not increase its rank, so it is in the row span, and indeed 1+7+18+20=0.

In this case, expressing any required vector as a linear combination of the rows must involve division by 23, so this may not be the best way to think about it. The fact that we can order the elements is surely important.

Title: Re: Number problem
Post by Aryabhatta on Jun 26^th, 2008, 11:20am

on 06/25/08 at 21:12:07, Eigenray wrote:

....
so this may not be the best way to think about it. The fact that we can order the elements is surely important.

I am not so sure about the ordering being necessary. I am not sure if the ordering among the co-ordinates is maintained across elements of the Null Space...

For a given matrix, a non-zero sum will fail to happen only for a finite number of such p (assuming the problem statement is correct)

Also, if we consider them as elements of F_p for the correct p, we might be able to attack this problem using the probabilistic method... generate an element of the row span randomly and see if we get one of the finite set of vectors with non-zero probability. If p is small enough, we might even be able to use the pigeon-hole principle.

Or we might be able to move to other fields (eg function fields) etc and have more methods available to us.

But, we never know what surprises this problem might hold!

Title: Re: Number problem
Post by NightBreeze on Jun 26^th, 2008, 12:58pm

I wonder what will be the outcome of your ventures :)

The problem is excerpt from a mathematics magazine, so it is not a trick question.

Title: Re: Number problem
Post by Eigenray on Jun 26^th, 2008, 8:28pm

Well, proving the statement in a single characteristic p for |S|=n doesn't necessarily imply the result in characteristic 0. But proving it for infinitely many p would, for a given n.

By the way, for any n, we can form a set of size n in some ring which has no nonempty subset of size < n summing to 0: simply take {1,2,4,...,2^n-1} mod 2ⁿ-1. But if 2ⁿ-1 is not prime this need not embed into a field.

Is there a set of size n, mod p, which has no nonempty subset summing to 0?

Here are some sets that require large subsets:
2/2: 1,2 mod 3
3/3: 1,2,4 mod 7
3/4: 1,2,4,6 mod 11
5/5: 1,2,4,8,16 mod 31
4/6: 1,4,5,6,9,15 mod 17
7/7: 1,2,4,8,16,32,64 mod 127
But I haven't found any beating 4/8.

Title: Re: Number problem
Post by Eigenray on Jun 26^th, 2008, 8:58pm

on 06/25/08 at 13:52:08, NightBreeze wrote:

I think it's impossible to get double elements in the expansion if we take the smallest cycle in both A and B. If we were to find a double, then a smaller cycle would exist , which is not possible.

Can you elaborate on this?

Title: Re: Number problem
Post by NightBreeze on Jun 27^th, 2008, 2:25am

It's not true. The I think at the start of that sentence was key. I was working with the unoriented graph at that time, which made the observation true. However, the unoriented graph does not work for this problem, so I had to abandon that idea altogether. It's a little bit more complicated. Forget that last post, I'll just write up what I've thought up so far.

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₁, ... x_k. Let k be the smallest k with this property. Then there exist Z = z₁, ... z_k such that

x₁ = x₂ + z₁ = x₃ + z₂ + z₁ = ... = x₁ + z_k + ... + z₁.

The the sequence z₁, ..., z_k will sum to zero.

The way I see it, 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 experimented 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 trying to find a structural way to avoid this.

Title: Re: Number problem
Post by Aryabhatta on Jun 30^th, 2008, 1:59am

on 06/26/08 at 12:58:28, NightBreeze wrote:

I wonder what will be the outcome of your ventures :)

The problem is excerpt from a mathematics magazine, so it is not a trick.

What magazine is this? Was this result mentioned in some article or was it a puzzle corner or something? Linear algebra looks promising but perhaps is overkill for this problem and perhaps simple counting/combinatorial arguments will do... :-/

Title: Re: Number problem
Post by NightBreeze on Jun 30^th, 2008, 7:33am

on 06/30/08 at 01:59:01, Aryabhatta wrote:

The problems are for math undergrads, taken from a university mag. Linear algebra should be known. The other 2 problems were about real analysis and n-dimensional calculus. I don't know if you're supposed to solve it with linear algebra or if it's a graph theory thing .. or just simple combinatorics. But all three disciplines should be known to the reader.

Title: Re: Number problem
Post by NightBreeze on Jul 8^th, 2008, 11:02am

Hey guys. Normally I'm not a big fan of bumping, but I would really like to see some attention directed to this problem. There were some interesting developments at first, but now it seems progress has stagnated.

Any new ideas?

Title: Re: Number problem
Post by Aryabhatta on Sep 11^th, 2008, 5:01pm

NightBreeze, do you have a solution for this?

Title: Re: Number problem
Post by NightBreeze on Sep 25^th, 2008, 1:56pm

I'm afraid I do not.

Invested a lot of time in it but haven't found my breakthrough idea. It's on hold as far as I'm concerned.