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
