# Conjecture on signed sum of integer fractions x/y from 1..N?

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

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

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