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 = \dfrac12 -\dfrac43 +\dfrac56$
$S(8)=0 = \dfrac13 -\dfrac54 +\dfrac76 -\dfrac28$
$S({10})=0 = \dfrac12 -\dfrac39 -\dfrac76 +\dfrac48 +\dfrac5{10}$
$S({12})=0=-\dfrac23 +\dfrac1{12} -\dfrac76 -\dfrac95 +\dfrac8{10} +\dfrac{11}4$
$… S({20})=0 = \dfrac{18}2 +\dfrac93 +\dfrac{11}{15} +\dfrac7{14} +\dfrac4{10} +\dfrac5{12} +\dfrac{13}8 +\dfrac6{16} -\dfrac{17}1 +\dfrac{19}{20}$
For $N={50}$, user Vašek found this one with $S({50}) < {10}^{-6}$: $9.844*{10}^{-7} =-\dfrac {26}{18} +\dfrac {44}7 -\dfrac {35}6 -\dfrac {13}{46} +\dfrac {39}{50} +\dfrac {27}2 -\dfrac {21}{14} -\dfrac {34}{41} +\dfrac 3{47} -\dfrac {29}{19} +\dfrac {49}{48} -\dfrac 1{10} -\dfrac {42}{12} -\dfrac {28}{20} -\dfrac {24}{22} +\dfrac {33}{32} -\dfrac {25}9 -\dfrac 5{11} +\dfrac {38}{31} -\dfrac {40}{16} -\dfrac {15}{36} +\dfrac {43}{37} +\dfrac 84 -\dfrac {45}{17} -\dfrac {23}{30}$
ksoileau using a hill-climbing algorithm found these near-zeros:
$ S(40)≤4.38055291*10^ {-8} = \dfrac 2{1}-\dfrac{3}{9}-\dfrac{5}{6}-\dfrac{7}{8}-\dfrac{4}{10}+\dfrac{21}{25}+\dfrac{17}{11 }-\dfrac{13}{23}-\dfrac{15}{39}+\dfrac{35}{38}+\dfrac{14}{32}+\dfrac{19}{33
}-\dfrac{24}{29}-\dfrac{27}{28}-\dfrac{16}{12}-\dfrac{26}{22}-\dfrac{30}{34 }+\dfrac{31}{36}+\dfrac{37}{20}-\dfrac{18}{40}$
$S(50)≤5.56460829*10^ {-8} = -\dfrac{1}{48}-\dfrac{3}{4}-\dfrac{5}{9}-\dfrac{7}{8}-\dfrac{20}{6}+\dfrac{10}{18 }+\dfrac{13}{30}-\dfrac{15}{16}+\dfrac{45}{12}+\dfrac{34}{17 }-\dfrac{39}{42}-\dfrac{23}{24}-\dfrac{25}{26}-\dfrac{2}{31 }+\dfrac{14}{29}+\dfrac{28}{32}+\dfrac{33}{19}-\dfrac{35}{36 }-\dfrac{37}{38}-\dfrac{21}{40}-\dfrac{41}{44}+\dfrac{43}{22 }+\dfrac{11}{46}+\dfrac{47}{27}-\dfrac{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) = \dfrac13 = 1 -\dfrac23$
$S(5) =0 = \dfrac31 +\dfrac42 – 5$
$S(7) =0 = \dfrac13 +\dfrac52 +\dfrac76 – 4$
$S(9) =0 = \dfrac12 -\dfrac68 -\dfrac74 -\dfrac93 + 5 $ or $\dfrac13 +\dfrac76 -\dfrac84 -\dfrac92 + 5$ etc.
$… S({19}) ≤ 1E-5 = \dfrac12 +\dfrac34 +\dfrac56 +\dfrac78 +\dfrac{12}{10} +\dfrac{14}{11} +\dfrac{16}{15} +\dfrac{18}{13} +\dfrac{19}{17} – 9 , $
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
Best Answer
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