Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Here is a generalization of an integer challenge that was asked on Yahoo!Answers in 2009, I believe it could be original, defies induction and has exponential-complexity. Not aware of any theory that covers it.

Using the natural numbers 1 through N exactly once each, write a (signed) sum of $\lceil N/2 \rceil$ fractions x/y giving the smallest positive minimum, S(N), and ideally try to achieve $S(N) \equiv 0$. In particular is $S(N)\equiv 0$ achievable for all even $N\geq6$ ? Or else for what values of N is that achievable, or not achievable? Is there any pattern?

Examples:

people found exact-zero solutions for even N up to 20, thereafter approximations

S(6)=0 = 1/2 -4/3 +5/6

S(8)=0 = 1/3 -5/4 +7/6 -2/8

S(10)=0 = 1/2-3/9-7/6+4/8+5/10

S(12)=0=-2/3+1/12-7/6-9/5+8/10+11/4

... S(20)=0 = 18/2 +9/3 +11/15 +7/14 +4/10 +5/12 +13/8 +6/16 -17/1 +19/20

For N=50, user Vašek found this one with S(50) < 10^(-6): 9.844E-7 = - 26/18 + 44/7 - 35/6 - 13/46 + 39/50 + 27/2 - 21/14 - 34/41 + 3/47 - 29/19 + 49/48 - 1/10 - 42/12 - 28/20 - 24/22 + 33/32 - 25/9 - 5/11 + 38/31 - 40/16 - 15/36 + 43/37 + 8/4 - 45/17 - 23/30

ksoileau using a hill-climbing algorithm found these near-zeros:

S(40)≤4.38055291*10^(-8) = 2/1-3/9-5/6-7/8-4/10+21/25+17/11 -13/23-15/39+35/38+14/32+19/33 -24/29-27/28-16/12-26/22-30/34 +31/36+37/20-18/40

S(50)≤5.56460829*10^(-8) = -1/48-3/4-5/9-7/8-20/6+10/18 +13/30-15/16+45/12+34/17 -39/42-23/24-25/26-2/31 +14/29+28/32+33/19-35/36 -37/38-21/40-41/44+43/22 +11/46+47/27-49/50

Can you say anything at all (analytically or statistically) about the behavior of S(N)? For what values of N should $S(N) \equiv 0$ (even if you can't show the solution)?

What's interesting is it seems to have no pattern and defeat induction: knowing all the results for numbers < N doesn't help at all with S(N)?

Odd-N cases:

S(3) = 1/3 = 1 -2/3

S(5) = 0 = 3/1 +4/2 -5

S(7) = 0 = 1/3 +5/2 +7/6 -4

S(9) = 0 = 1/2 -6/8 -7/4 -9/3 +5 or 1/3 +7/6 -8/4 -9/2 +5 etc.

... S(19) ≤ 1E-5 = +1/2 +3/4 +5/6 +7/8 +12/10 +14/11 +16/15 +18/13 +19/17 -9 , can you do better?

Presumably it makes most sense to break out odd and even N separately. i.e. S(2M) forms one decreasing(?) sequence, and S(2M+1) forms another. Anyone with time on their hands, feel free to compute and post tables of S(N) for N.

See if you can even prove whether the even-N case {S(2M)} is or is not monotone decreasing (at least for some subrange of 2M).

Addenda:

To eliminate duplicates with order of terms swapped, let us adopt some (arbitrary) ordering principle such as e.g. require the denominators {y_i} to be in increasing order.

I had one thought about a probabilistic proof: Write each of the $\lceil N/2 \rceil$ terms as $(x_i/y_i) = u_i$ and also call σ_i the sign chosen for each term u_i. Then consider our sum $\sum σ_i (x_i/y_i)$

Noting that each of the terms $u_i = \exp{[ ln(x_i) - ln(y_i) ]}$ consider the distribution of all possible $N! (N-1)!$ values of the {u_i}. The u_i are discrete but look how exponentially $N! (N-1)!$ grows with N. It seems intuitive that the more possible values for the u_i we have, the more probabilistic that we can choose some signed sum of {u_i} to minimize S(N), and specifically to make S(N) < S(N-2). Try to calculate that probability?

(PS be careful of precision and roundoff errors if you program this.)

PPS: A note on the complexity of this problem:

There are N! choices to assign the N numbers into $\lceil N/2 \rceil$ fraction terms $x_i/y_i$ ; and an additional $\lceil N/2 \rceil$ choices for the signs {σ_i} Thus it is exponential (2^N) complexity. without loss of generality, choose an ordered notation where the fractions $σ (x/y)$ are written in order of increasing numerators x. Then there are:

$\;\;\;\;\;\;\;\;\; \binom{N}{\lceil N/2 \rceil}$ ways to pick the numerators {x_i}

$\;\;\;\;\;\;\;\;\; \lfloor N/2 \rfloor !$ ways to pick all the denominators y_i for each x_i ;

$\;\;\;\;\;\;\;\;\; 2^{\lceil N/2 \rceil}$ ways to choose signs σ_i

$\implies complexity(N) \sim \lfloor N/2 \rfloor ! * \binom{N}{\lceil N/2 \rceil} * 2^{\lceil N/2 \rceil}$

and that boils down to: $2^{2M}$ (even case) and $2^{2(M+1)} / (M+2)$ (odd case).

User steppenwolf (see reference 1) sketched a proof that, at least for even N, $\lim_{2M\to\infty} S(2M)=0$

and also a weak upper bound $S(N) \leq 3.25/N$

I originally asked this on Yahoo!Answers as a generalization of a previous question by user ksoileau: http://answers.yahoo.com/question/index?qid=20090330224143AA2zDfL

share|improve this question
    
Sorry -- what's the conjecture referred to in the title? –  Todd Trimble Jan 18 '11 at 9:06
    
In particular is S(N)=0 achievable for all even N (≥6) ? –  smci Jan 18 '11 at 9:44
    
Also, does it exhibit no pattern and defeat induction: knowing all the results for numbers < N doesn't help at all with S(N)? –  smci Jan 18 '11 at 9:46
1  
Can you re-edit equations with LaTeX? –  Nurdin Takenov Jan 18 '11 at 10:52
    
There is a reference to N possibly being odd, but I don't see how the fractions (which have the same number of numerators as denominators) are supposed to work in this case. Or is zero allowed as a numerator in the odd case? –  Mark Bennet Jan 18 '11 at 19:49
show 2 more comments

1 Answer 1

This is a suggestion to not dismiss induction too readily.

If I were to attempt an inductive proof, one approach I would take would be an inductive definition of T(2m), the set of all sums arrived at by forming m fractions as directed and then taking all signed sums. T(2m+2) is an incremental change to T(2m), but with most likely more than exponential growth. If you can prove that T(2m) contains either fraction (2m+1)/(2m+2) or its multiplicative inverse, you can conclude S(2m+2) is 0. That would be too easy, though. I suspect you will need solve equations like x/(2m+2) + (2m+1)/y = P for some value of P that is related to a value in T(2m).

Gerhard "Ask Me About System Design" Paseman, 2011.01.18

share|improve this answer
    
I'm surprised, as I hadn't noticed the negative vote. Also, (I think it was) your observation about s(primorial(n))>= n was useful in the happy prime new year thread, and I was sorry to see it go. Perhaps it will return. Gerhard "Thank You For Your SUpport" Paseman, 2011.01.19 –  Gerhard Paseman Jan 19 '11 at 17:51
    
Even if you can't prove the inductive step, any reaction to my suggestion on a probabilistic proof? –  smci Jan 19 '11 at 22:18
    
Since you asked, my reaction is that it is illformed. Is u_i one of the fractions or the sum? For a given 2m, there are less than 4m^2 such fractions allowed, and you don't want the sum of any of them, but of a particular subset of them which is challenging to enumerate. Until you clean up that part, I am not encouraged to proceed to the estimate of the enumeration, much less to the argument. Also, it is likely that some of the sums will be equal, and it is not clear how the probabilistic argument will handle that. Gerhard "Ask Me About System Design" Paseman, 2011.01.19 –  Gerhard Paseman Jan 19 '11 at 22:39
    
Dude, I wrote that u_i = (x_i/y_i) is one term, σ_i is its sign, and the summation is Σ σ_i (x_i/y_i) Yes, rarely some of the sums are equal, if we adopt some (arbitrary) ordering principle such as e.g. require the numerators {x_i} to be in increasing order. This throws out duplicate sequences with terms swapped. After that there is nearly-zero probability of two different sequences having the same sum. So the probabilistic argument gives us a (quadratic?) range of choices for each term. –  smci Jan 27 '11 at 21:23
    
In fact a better ordering principle is probably denominators {y_i} must be in increasing order. This makes for better legibility of the solution, but programming the recursion gets a little bit more annoying. –  smci Jan 27 '11 at 21:28
show 5 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.