Author 
Topic: Number problem (Read 2680 times) 

NightBreeze
Newbie
Posts: 26


Number problem
« on: Jun 21^{st}, 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 nonempty 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 bside:  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 22^{nd}, 2008, 12:29pm by NightBreeze » 
IP Logged 



Eigenray
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 1948


Re: Number problem
« Reply #1 on: Jun 24^{th}, 2008, 12:34am » 
Quote Modify

I don't know but in theory it's a finite computation: Let s = (s_{1},...,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  (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 H_{i} is equivalent to ker A 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^{15} 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 24^{th}, 2008, 4:38pm by Eigenray » 
IP Logged 



NightBreeze
Newbie
Posts: 26


Re: Number problem
« Reply #2 on: Jun 24^{th}, 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 24^{th}, 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 24^{th}, 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 24^{th}, 2008, 11:50am by towr » 
IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



NightBreeze
Newbie
Posts: 26


Re: Number problem
« Reply #4 on: Jun 24^{th}, 2008, 12:25pm » 
Quote Modify

This is more along the lines of how I was tackling it. on Jun 24^{th}, 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 24^{th}, 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 24^{th}, 2008, 12:29pm » 
Quote Modify

on Jun 24^{th}, 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 24^{th}, 2008, 12:57pm » 
Quote Modify

on Jun 24^{th}, 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 24^{th}, 2008, 2:14pm by NightBreeze » 
IP Logged 



Eigenray
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 1948


Re: Number problem
« Reply #7 on: Jun 24^{th}, 2008, 3:59pm » 
Quote Modify

For the matrix A I'm talking about, IA 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 24^{th}, 2008, 4:32pm by Eigenray » 
IP Logged 



NightBreeze
Newbie
Posts: 26


Re: Number problem
« Reply #8 on: Jun 25^{th}, 2008, 2:43am » 
Quote Modify

on Jun 24^{th}, 2008, 3:59pm, Eigenray wrote:For the matrix A I'm talking about, IA 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 IA, 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 IA would look the same, only with 2's instead of 1's in the rows with only one nonzero entry. So why is this the only configuration which will give a 'working' S? Besides bruteforcing 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^{n1} which is smaller than 2^{n+1}. I don't know if it's useful, but there it is anyways. In drawing the graph of S_{6}, I couldn't find any property which would indicate how the zerosum subsets might be constructed. But I'll keep looking.

« Last Edit: Jun 25^{th}, 2008, 2:44am by NightBreeze » 
IP Logged 



Eigenray
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 1948

on Jun 25^{th}, 2008, 2:43am, NightBreeze wrote:But in the case of IA, 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 nonsimple 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 35 split, and 232 with 44. 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 25^{th}, 2008, 1:52pm » 
Quote Modify

on Jun 25^{th}, 2008, 4:54am, Eigenray wrote: The entries of an adjacency matrix are the number of edges from one vertex to another. For a nonsimple 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_{1}, ..., x_{k}. Assume that k is minimal with this property. Then there exists z_{i} in S such that x_{1} = x_{2} + z_{1} = x_{3} + z_{2} + z_{2} = ... = x_{1} + z_{k} + ... + z_{1}. 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_{1} 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 9639 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 25^{th}, 2008, 5:00pm by NightBreeze » 
IP Logged 



Aryabhatta
Uberpuzzler
Gender:
Posts: 1321


Re: Number problem
« Reply #11 on: Jun 25^{th}, 2008, 4:42pm » 
Quote Modify

on Jun 24^{th}, 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 nonzero 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 25^{th}, 2008, 4:45pm by Aryabhatta » 
IP Logged 



Eigenray
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 1948


Re: Number problem
« Reply #12 on: Jun 25^{th}, 2008, 4:54pm » 
Quote Modify

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.

« Last Edit: Jun 25^{th}, 2008, 4:56pm by Eigenray » 
IP Logged 



Aryabhatta
Uberpuzzler
Gender:
Posts: 1321


Re: Number problem
« Reply #13 on: Jun 25^{th}, 2008, 7:12pm » 
Quote Modify

on Jun 25^{th}, 2008, 4:54pm, 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 coordinates. 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!

« Last Edit: Jun 25^{th}, 2008, 7:19pm by Aryabhatta » 
IP Logged 



Eigenray
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 1948


Re: Number problem
« Reply #14 on: Jun 25^{th}, 2008, 8:01pm » 
Quote Modify

on Jun 25^{th}, 2008, 7:12pm, 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 2dimensional 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, 2i, 4, 42 i, 6, 8} {23 i, 22 i, 2i, 2, 2+i, 1, 2 i, i, i, 13 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, 1i, 12 i, 2, 2i, 22 i, 3, 3i} Note that 'i' could be replaced by any field element, as long as the entries remain distinct. (I haven't yet found any 2dimensional sets that have no pairs summing to zero though.)

« Last Edit: Jun 25^{th}, 2008, 9:48pm by Eigenray » 
IP Logged 



Aryabhatta
Uberpuzzler
Gender:
Posts: 1321


Re: Number problem
« Reply #15 on: Jun 25^{th}, 2008, 8:10pm » 
Quote Modify

on Jun 25^{th}, 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 25^{th}, 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 26^{th}, 2008, 3:11am by Eigenray » 
IP Logged 



Aryabhatta
Uberpuzzler
Gender:
Posts: 1321


Re: Number problem
« Reply #17 on: Jun 26^{th}, 2008, 11:20am » 
Quote Modify

on Jun 25^{th}, 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 coordinates is maintained across elements of the Null Space... For a given matrix, a nonzero 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 nonzero probability. If p is small enough, we might even be able to use the pigeonhole 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 26^{th}, 2008, 11:21am by Aryabhatta » 
IP Logged 



NightBreeze
Newbie
Posts: 26


Re: Number problem
« Reply #18 on: Jun 26^{th}, 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 8^{th}, 2008, 1:05pm by NightBreeze » 
IP Logged 



Eigenray
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 1948


Re: Number problem
« Reply #19 on: Jun 26^{th}, 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,...,2^{n1}} mod 2^{n}1. But if 2^{n}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 26^{th}, 2008, 8:55pm by Eigenray » 
IP Logged 



Eigenray
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 1948


Re: Number problem
« Reply #20 on: Jun 26^{th}, 2008, 8:58pm » 
Quote Modify

on Jun 25^{th}, 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 27^{th}, 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 = 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 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.

« Last Edit: Jun 27^{th}, 2008, 2:27am by NightBreeze » 
IP Logged 



Aryabhatta
Uberpuzzler
Gender:
Posts: 1321


Re: Number problem
« Reply #22 on: Jun 30^{th}, 2008, 1:59am » 
Quote Modify

on Jun 26^{th}, 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 30^{th}, 2008, 7:33am » 
Quote Modify

on Jun 30^{th}, 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 ndimensional 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 30^{th}, 2008, 7:36am by NightBreeze » 
IP Logged 



NightBreeze
Newbie
Posts: 26


Re: Number problem
« Reply #24 on: Jul 8^{th}, 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 8^{th}, 2008, 1:06pm by NightBreeze » 
IP Logged 



