|
16
|
|
edited Jan 28 2011 at 9:31 |
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 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
|
|
|
|
|
15
|
|
edited Jan 27 2011 at 21:26 |
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).
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 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
|
|
edited Jan 27 2011 at 21:17 |
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).
Addenda:
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
|
|
edited Jan 19 2011 at 3:35 |
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).
Addenda:
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 $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
|
|
|
|
|
12
|
|
edited Jan 18 2011 at 23:11 |
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) S(50) < 10^{-6}$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.
...
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:
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 $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
|
|
|
|
|
11
|
|
edited Jan 18 2011 at 22:27 |
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) $S(50) < 10^(-6)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)?
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:
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 $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
|
|
|
|
|
10
|
|
edited Jan 18 2011 at 19:34 |
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)?
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:
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 $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:
\indent
$\binom{N}{\lceil \;\;\;\;\;\;\;\;\; \binom{N}{\lceil N/2 \rceil}$ ways to pick the numerators {x_i}\indent
$\lfloor \;\;\;\;\;\;\;\;\; \lfloor N/2 \rfloor !$ ways to pick all the denominators y_i for each x_i ;\indent
$\;\;\;\;\;\;\;\;\; 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
|
|
|
|
|
9
|
|
edited Jan 18 2011 at 19:28 |
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)?
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:
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 $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:
\indent $\binom{N}{\lceil N/2 \rceil}$ ways to pick the numerators {x_i}
\indent $\lfloor N/2 \rfloor !$ ways to pick all the denominators y_i for each x_i ;
\indent $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
|
|
|
|
|
8
|
|
edited Jan 18 2011 at 19:22 |
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)?
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).
Addendum
Addenda:
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 $u_i = e^ [ \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 maybe you can approximate them as continuouslook 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 \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 2^{\lceil N/2 \rceil$ rceil}$ ways to choose signs σ_i
=>
$\implies complexity(N) is
$\lfloor \sim \lfloor N/2 \rfloor ! * \binom{n}{\lceil binom{N}{\lceil N/2 \rceil} * 2^ \lceil 2^{\lceil N/2 \rceil$
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 thatk → ∞ S(2k) → 0
, at least for even N, $\lim_{2M\to\infty} S(2M)=0$
and also a weak upper bound S(N) ≤ 3.25 / N$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
|
|
|
|
|
7
|
|
edited Jan 18 2011 at 19:07 |
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:
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)?
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).
Addendum:
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 $u_i = e^ [ ln(x_i) - ln(y_i) ]$
consider the distribution of possible values of u_i. The u_i are discrete but maybe you can approximate them as continuous.
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:
C(n, ⌈n/2⌉) $\binom{n}{\lceil N/2 \rceil}$ ways to pick the numerators {x_i}
$\lfloor N/2 \rfloor$ rfloor !$ ways to pick all the denominators y_i for each x_i 2^$\lceil ;
$2^ \lceil N/2 \rceil$ ways to choose signs σ_i
=> complexity(ncomplexity(N) is
$\lfloor N/2 \rfloor$ rfloor ! * C(n, $\lceil \binom{n}{\lceil N/2 \rceil$) rceil} * 2^$\lceil 2^ \lceil N/2 \rceil$
and that boils down to
$2^(2M)$ 2^{2M}$ (even case) and $2^(2(M+1)) 2^{2(M+1)} / (M+2)$ (odd case).
User steppenwolf (see reference 1) sketched a proof that k → ∞ S(2k) → 0
and also a weak upper bound S(N) ≤ 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
|
|
|
|
|
6
|
|
edited Jan 18 2011 at 18:54 |
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:
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)?
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).
Addendum:
I had one thought about a probabilistic proof:
Write each of the ⌈N/2⌉ $\lceil N/2 \rceil$ terms as (x_i/y_i) $(x_i/y_i) = u_i
u_i$
and also call σ_i the sign chosen for each term u_i.
Then consider our sum $Σ σ_i (x_i/y_i)x_i/y_i)$
Noting that $u_i = e^ [ ln(x_i) - ln(y_i) ]$
consider the distribution of possible values of u_i. The u_i are discrete but maybe you can approximate them as continuous.
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 nN! choices to assign the n N numbers into ⌈n/2⌉ $\lceil N/2 \rceil$ fraction terms x_i/y_i $x_i/y_i$ ;
and an additional ⌈n/2⌉ $\lceil N/2 \rceil$ choices for the signs {σ_i}
Thus it is exponential (2^n) 2^N) complexity.
without loss of generality, choose an ordered notation where the fractions $σ (x/y) x/y)$ are written in order of increasing numerators x.
Then there are:
C(n, ⌈n/2⌉) ways to pick the numerators {x_i}
⌊n/2⌋ $\lfloor N/2 \rfloor$ ! (factorial) ways to pick all the denominators y_i for each x_i
2^⌈n/2⌉ 2^$\lceil N/2 \rceil$ ways to choose signs σ_i
=> complexity(n) is
⌊n/2⌋ $\lfloor N/2 \rfloor$ ! * C(n, ⌈n/2⌉) $\lceil N/2 \rceil$) * 2^⌈n/2⌉
2^$\lceil N/2 \rceil$
and that boils down to
2^2m $2^(2M)$ (even case) and 2^2(m+1) $2^(2(M+1)) / (m+2) M+2)$ (odd case).
User steppenwolf (see reference 1) sketched a proof that k → ∞ S(2k) → 0
and also a weak upper bound S(nS(N) ≤ 3.25 / nN
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
|
|
|
|
|
5
|
|
edited Jan 18 2011 at 15:45 |
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:
S(6)=0 = 1/2 -4/3 +5/6
S(8)=0 = 1/3 -5/4 +7/6 -2/8
S(12)=0
S(10)=0 = 1/2-3/9-7/6+4/8+5/10-2/3+1/12-7/6-9/5+8/10+11/41/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)?
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).
Addendum:
I had one thought about a probabilistic proof:
Write each of the ⌈N/2⌉ terms as (x_i/y_i) = u_i
and also call σ_i the sign chosen for each term u_i.
Then consider our sum Σ σ_i (x_i/y_i)
Noting that u_i = e^ [ ln(x_i) - ln(y_i) ]
consider the distribution of possible values of u_i. The u_i are discrete but maybe you can approximate them as continuous.
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 ⌈n/2⌉ fraction terms x_i/y_i ;
and an additional ⌈n/2⌉ 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:
C(n, ⌈n/2⌉) ways to pick the numerators {x_i}
⌊n/2⌋ ! (factorial) ways to pick all the denominators y_i for each x_i
2^⌈n/2⌉ ways to choose signs σ_i
=> complexity(n) is
⌊n/2⌋ ! * C(n, ⌈n/2⌉) * 2^⌈n/2⌉
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 k → ∞ S(2k) → 0
and also a weak upper bound S(n) ≤ 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
|
|
|
|
|
4
|
|
edited Jan 18 2011 at 9:49 |
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:
S(6)=0 = 1/2 -4/3 +5/6
S(8)=0 = 1/3 -5/4 +7/6 -2/8
S(12)=0 = 1/2-3/9-7/6+4/8+5/10-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)?
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).
Addendum:
I had one thought about a probabilistic proof:
Write each of the ⌈N/2⌉ terms as (x_i/y_i) = u_i
and also call σ_i the sign chosen for each term u_i.
Then Σ u_i = consider our sum Σ σ_i (x_i/y_i)
Noting that u_i = e^ [ ln(x_i) - ln(y_i) ]
consider the distribution of possible values of u_i. The u_i are discrete but maybe you can approximate them as continuous.
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 ⌈n/2⌉ fraction terms x_i/y_i ;
and an additional ⌈n/2⌉ 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:
C(n, ⌈n/2⌉) ways to pick the numerators {x_i}
⌊n/2⌋ ! (factorial) ways to pick all the denominators y_i for each x_i
2^⌈n/2⌉ ways to choose signs σ_i
=> complexity(n) is
⌊n/2⌋ ! * C(n, ⌈n/2⌉) * 2^⌈n/2⌉
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 k → ∞ S(2k) → 0
and also a weak upper bound S(n) ≤ 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
|
|
|
|
|
3
|
|
edited Jan 18 2011 at 9:30 |
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 integers 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:
S(6)=0 = 1/2 -4/3 +5/6
S(8)=0 = 1/3 -5/4 +7/6 -2/8
S(12)=0 = 1/2-3/9-7/6+4/8+5/10-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)?
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).
Addendum:
I had one thought about a probabilistic proof:
Write each of the ⌈N/2⌉ terms as (x_i/y_i) = u_i
and also call σ_i the sign chosen for each term u_i.
Then Σ u_i = Σ σ_i (x_i/y_i)
Noting that u_i = e^ [ ln(x_i) - ln(y_i) ]
consider the distribution of possible values of u_i. The u_i are discrete but maybe you can approximate them as continuous.
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 ⌈n/2⌉ fraction terms x_i/y_i ;
and an additional ⌈n/2⌉ 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:
C(n, ⌈n/2⌉) ways to pick the numerators {x_i}
⌊n/2⌋ ! (factorial) ways to pick all the denominators y_i for each x_i
2^⌈n/2⌉ ways to choose signs σ_i
=> complexity(n) is
⌊n/2⌋ ! * C(n, ⌈n/2⌉) * 2^⌈n/2⌉
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 k → ∞ S(2k) → 0
and also a weak upper bound S(n) ≤ 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
|
|
|
|
|
2
|
|
edited Jan 18 2011 at 8:45 |
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 integers 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:
S(6)=0 = 1/2 -4/3 +5/6
S(8)=0 = 1/3 -5/4 +7/6 -2/8
S(12)=0 = 1/2-3/9-7/6+4/8+5/10-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) $S(N) \equiv 0 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)?
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).
Addendum:
I had one thought about a probabilistic proof:
Write each of the ⌈N/2⌉ terms as (x_i/y_i) = u_i
and also call σ_i the sign chosen for each term u_i.
Then Σ u_i = Σ σ_i (x_i/y_i)
Noting that u_i = e^ [ ln(x_i) - ln(y_i) ]
consider the distribution of possible values of u_i. The u_i are discrete but maybe you can approximate them as continuous.
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 ⌈n/2⌉ fraction terms x_i/y_i ;
and an additional ⌈n/2⌉ 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:
C(n, ⌈n/2⌉) ways to pick the numerators {x_i}
⌊n/2⌋ ! (factorial) ways to pick all the denominators y_i for each x_i
2^⌈n/2⌉ ways to choose signs σ_i
=> complexity(n) is
⌊n/2⌋ ! * C(n, ⌈n/2⌉) * 2^⌈n/2⌉
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 k → ∞ S(2k) → 0
and also a weak upper bound S(n) ≤ 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
|
|
|
|
|
1
|
|
asked Jan 18 2011 at 8:11 |
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 integers 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:
S(6)=0 = 1/2 -4/3 +5/6
S(8)=0 = 1/3 -5/4 +7/6 -2/8
S(12)=0 = 1/2-3/9-7/6+4/8+5/10-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)?
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.
Addendum:
I had one thought about a probabilistic proof:
Write each of the ⌈N/2⌉ terms as (x_i/y_i) = u_i
and also call σ_i the sign chosen for each term u_i.
Then Σ u_i = Σ σ_i (x_i/y_i)
Noting that u_i = e^ [ ln(x_i) - ln(y_i) ]
consider the distribution of possible values of u_i. The u_i are discrete but maybe you can approximate them as continuous.
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 ⌈n/2⌉ fraction terms x_i/y_i ;
and an additional ⌈n/2⌉ 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:
C(n, ⌈n/2⌉) ways to pick the numerators {x_i}
⌊n/2⌋ ! (factorial) ways to pick all the denominators y_i for each x_i
2^⌈n/2⌉ ways to choose signs σ_i
=> complexity(n) is
⌊n/2⌋ ! * C(n, ⌈n/2⌉) * 2^⌈n/2⌉
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 k → ∞ S(2k) → 0
and also a weak upper bound S(n) ≤ 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
|
|
|
