Author |
Topic: Number problem (Read 2666 times) |
|
NightBreeze
Newbie
Posts: 26
|
 |
Number problem
« on: Jun 21st, 2008, 11:11am » |
 Quote  Modify
|
I offer you the following problem.
---------------------------------------------------------
Consider a set S   with |S| = 15 and the following property:
 s  S,  a,b S such that s = a+b
Prove that for every such S, there exists a non-empty subset T 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 with |S|=16, this statement is not true.
---------------------------------------------------------
I have found a counterexample to prove this.
Good luck!
|
| « Last Edit: Jun 22nd, 2008, 12:29pm by NightBreeze » |
 IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender: 
Posts: 1948
|
|
Re: Number problem
« Reply #1 on: Jun 24th, 2008, 12:34am » |
Quote Modify
|
I don't know but in theory it's a finite computation:
Let s = (s1,...,sn) list the elements of S. For each i, there exist f(i), g(i) such that si = sf(i) + sg(i). Then there is an nxn matrix A with As=0, namely A = I -  (Ei,f(i)+Ei,g(i)), where Ei,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   Hi is equivalent to ker A Hi 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 10515 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}
|
| « Last Edit: Jun 24th, 2008, 4:38pm by Eigenray » |
IP Logged |
|
|
|
NightBreeze
Newbie
Posts: 26
|
|
Re: Number problem
« Reply #2 on: Jun 24th, 2008, 10:30am » |
Quote Modify
|
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? 
|
| « Last Edit: Jun 24th, 2008, 10:39am by NightBreeze » |
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Number problem
« Reply #3 on: Jun 24th, 2008, 11:36am » |
Quote Modify
|
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 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]
|
| « Last Edit: Jun 24th, 2008, 11:50am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
NightBreeze
Newbie
Posts: 26
|
|
Re: Number problem
« Reply #4 on: Jun 24th, 2008, 12:25pm » |
Quote Modify
|
This is more along the lines of how I was tackling it.
on Jun 24th, 2008, 11:36am, 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 . 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!
|
| « Last Edit: Jun 24th, 2008, 12:27pm by NightBreeze » |
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Number problem
« Reply #5 on: Jun 24th, 2008, 12:29pm » |
Quote Modify
|
on Jun 24th, 2008, 12:25pm, 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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
NightBreeze
Newbie
Posts: 26
|
|
Re: Number problem
« Reply #6 on: Jun 24th, 2008, 12:57pm » |
Quote Modify
|
on Jun 24th, 2008, 12:29pm, 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'?
|
| « Last Edit: Jun 24th, 2008, 2:14pm by NightBreeze » |
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Number problem
« Reply #7 on: Jun 24th, 2008, 3:59pm » |
Quote Modify
|
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).
|
| « Last Edit: Jun 24th, 2008, 4:32pm by Eigenray » |
IP Logged |
|
|
|
NightBreeze
Newbie
Posts: 26
|
|
Re: Number problem
« Reply #8 on: Jun 25th, 2008, 2:43am » |
Quote Modify
|
on Jun 24th, 2008, 3:59pm, 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 2n-1 which is smaller than -2n+1.
I don't know if it's useful, but there it is anyways. In drawing the graph of S6, I couldn't find any property which would indicate how the zero-sum subsets might be constructed. But I'll keep looking.
|
| « Last Edit: Jun 25th, 2008, 2:44am by NightBreeze » |
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
on Jun 25th, 2008, 2:43am, 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.
|
|
IP Logged |
|
|
|
NightBreeze
Newbie
Posts: 26
|
|
Re: Number problem
« Reply #10 on: Jun 25th, 2008, 1:52pm » |
Quote Modify
|
on Jun 25th, 2008, 4:54am, 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 x1, ..., xk. Assume that k is minimal with this property. Then there exists zi in S such that
x1 = x2 + z1 = x3 + z2 + z2 = ... = x1 + zk + ... + z1.
This means that the zi 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 x1 such that the cycle contains double? Every cycle I tried, including those not entirely inside A or B does not contain doubles  . 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
|
| « Last Edit: Jun 25th, 2008, 5:00pm by NightBreeze » |
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Number problem
« Reply #11 on: Jun 25th, 2008, 4:42pm » |
Quote Modify
|
on Jun 24th, 2008, 12:34am, 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?
|
| « Last Edit: Jun 25th, 2008, 4:45pm by Aryabhatta » |
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Number problem
« Reply #12 on: Jun 25th, 2008, 4:54pm » |
Quote Modify
|
The key point is that if a subspace W is contained in a finite union of subspaces Vi, and the field is infinite, then W must actually be contained in a single Vi. So if we have a finite list of vectors vi such that any vector in ker A is orthogonal to some vi, then there must be a single i such that all of ker A is orthogonal to vi, and so vi 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 vi in its row space. The converse is obvious: if we can do this, then we have proved the result.
|
| « Last Edit: Jun 25th, 2008, 4:56pm by Eigenray » |
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Number problem
« Reply #13 on: Jun 25th, 2008, 7:12pm » |
Quote Modify
|
on Jun 25th, 2008, 4:54pm, Eigenray wrote:| ... So if we have a finite list of vectors vi such that any vector in ker A is orthogonal to some vi... |
|
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 vi, 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!
|
| « Last Edit: Jun 25th, 2008, 7:19pm by Aryabhatta » |
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Number problem
« Reply #14 on: Jun 25th, 2008, 8:01pm » |
Quote Modify
|
on Jun 25th, 2008, 7:12pm, Aryabhatta wrote:
Quote:| So if we have a finite list of vectors vi such that any vector in ker A is orthogonal to some vi |
|
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.)
|
| « Last Edit: Jun 25th, 2008, 9:48pm by Eigenray » |
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Number problem
« Reply #15 on: Jun 25th, 2008, 8:10pm » |
Quote Modify
|
on Jun 25th, 2008, 8:01pm, 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.
|
|
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Number problem
« Reply #16 on: Jun 25th, 2008, 9:12pm » |
Quote Modify
|
Actually it is false in characteristic p:
{1, 7, 12, 13, 17, 18, 20} mod 23
has no subset of size  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.
|
| « Last Edit: Jun 26th, 2008, 3:11am by Eigenray » |
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Number problem
« Reply #17 on: Jun 26th, 2008, 11:20am » |
Quote Modify
|
on Jun 25th, 2008, 9:12pm, 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!
|
| « Last Edit: Jun 26th, 2008, 11:21am by Aryabhatta » |
IP Logged |
|
|
|
NightBreeze
Newbie
Posts: 26
|
|
Re: Number problem
« Reply #18 on: Jun 26th, 2008, 12:58pm » |
Quote Modify
|
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.
|
| « Last Edit: Jul 8th, 2008, 1:05pm by NightBreeze » |
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Number problem
« Reply #19 on: Jun 26th, 2008, 8:28pm » |
Quote Modify
|
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,...,2n-1} mod 2n-1. But if 2n-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.
|
| « Last Edit: Jun 26th, 2008, 8:55pm by Eigenray » |
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Number problem
« Reply #20 on: Jun 26th, 2008, 8:58pm » |
Quote Modify
|
on Jun 25th, 2008, 1:52pm, 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?
|
|
IP Logged |
|
|
|
NightBreeze
Newbie
Posts: 26
|
|
Re: Number problem
« Reply #21 on: Jun 27th, 2008, 2:25am » |
Quote Modify
|
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 = 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 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 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 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.
|
| « Last Edit: Jun 27th, 2008, 2:27am by NightBreeze » |
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Number problem
« Reply #22 on: Jun 30th, 2008, 1:59am » |
Quote Modify
|
on Jun 26th, 2008, 12:58pm, 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... 
|
|
IP Logged |
|
|
|
NightBreeze
Newbie
Posts: 26
|
|
Re: Number problem
« Reply #23 on: Jun 30th, 2008, 7:33am » |
Quote Modify
|
on Jun 30th, 2008, 1:59am, Aryabhatta wrote:
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... |
|
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.
|
| « Last Edit: Jun 30th, 2008, 7:36am by NightBreeze » |
IP Logged |
|
|
|
NightBreeze
Newbie
Posts: 26
|
|
Re: Number problem
« Reply #24 on: Jul 8th, 2008, 11:02am » |
Quote Modify
|
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?
|
| « Last Edit: Jul 8th, 2008, 1:06pm by NightBreeze » |
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print
subsetsum8.txt