16 added 6 characters in body

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

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

14 added 18 characters in body

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

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

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

13 added 82 characters in body
11 added 2 characters in body
10 trying latex indents; added 1 characters in body; added 36 characters in body
9 added 46 characters in body; deleted 26 characters in body; [made Community Wiki]
8 latex; added 3 characters in body
7 latex
6 LaTex
5 added 12 characters in body
4 minor algebra correction
3 Clarified 'integers' -> 'natural numbers'
2 added 37 characters in body
1