15
$\begingroup$

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

Improve this question
$\endgroup$
8
  • $\begingroup$ Sorry -- what's the conjecture referred to in the title? $\endgroup$
    – Todd Trimble
    Commented Jan 18, 2011 at 9:06
  • $\begingroup$ In particular is S(N)=0 achievable for all even N (≥6) ? $\endgroup$
    – smci
    Commented Jan 18, 2011 at 9:44
  • $\begingroup$ Also, does it exhibit no pattern and defeat induction: knowing all the results for numbers < N doesn't help at all with S(N)? $\endgroup$
    – smci
    Commented Jan 18, 2011 at 9:46
  • 1
    $\begingroup$ Can you re-edit equations with LaTeX? $\endgroup$
    – Nurdin Takenov
    Commented Jan 18, 2011 at 10:52
  • 1
    $\begingroup$ Any prime (or prime power) between $N/2$ or $N$ cannot occur in the denominator if $S(N)$ is to vanish. More generally, numbers up to $N$ with large prime factors would make it difficult for $S(N)$ to vanish if they were in the denominator, however given that half of the numbers up to $N$ have to become denominators, I would suspect that $S(N)$ will not vanish for all large $N$. Also the irregularity of the primes suggests that an inductive construction to try to prove $S(N)=0$ is possible for large $N$ is likely to fail. $\endgroup$
    – Terry Tao
    Commented Feb 2, 2015 at 20:00

1 Answer 1

Reset to default
1
$\begingroup$

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

Improve this answer
$\endgroup$
10
  • $\begingroup$ I'm surprised, as I hadn't noticed the negative vote. Also, (I think it was) your observation about s(primorial(n))>= n was useful in the happy prime new year thread, and I was sorry to see it go. Perhaps it will return. Gerhard "Thank You For Your SUpport" Paseman, 2011.01.19 $\endgroup$
    – Gerhard Paseman
    Commented Jan 19, 2011 at 17:51
  • $\begingroup$ Even if you can't prove the inductive step, any reaction to my suggestion on a probabilistic proof? $\endgroup$
    – smci
    Commented Jan 19, 2011 at 22:18
  • $\begingroup$ Since you asked, my reaction is that it is illformed. Is u_i one of the fractions or the sum? For a given 2m, there are less than 4m^2 such fractions allowed, and you don't want the sum of any of them, but of a particular subset of them which is challenging to enumerate. Until you clean up that part, I am not encouraged to proceed to the estimate of the enumeration, much less to the argument. Also, it is likely that some of the sums will be equal, and it is not clear how the probabilistic argument will handle that. Gerhard "Ask Me About System Design" Paseman, 2011.01.19 $\endgroup$
    – Gerhard Paseman
    Commented Jan 19, 2011 at 22:39
  • $\begingroup$ Dude, I wrote that u_i = (x_i/y_i) is one term, σ_i is its sign, and the summation is Σ σ_i (x_i/y_i) Yes, rarely some of the sums are equal, if we adopt some (arbitrary) ordering principle such as e.g. require the numerators {x_i} to be in increasing order. This throws out duplicate sequences with terms swapped. After that there is nearly-zero probability of two different sequences having the same sum. So the probabilistic argument gives us a (quadratic?) range of choices for each term. $\endgroup$
    – smci
    Commented Jan 27, 2011 at 21:23
  • $\begingroup$ In fact a better ordering principle is probably denominators {y_i} must be in increasing order. This makes for better legibility of the solution, but programming the recursion gets a little bit more annoying. $\endgroup$
    – smci
    Commented Jan 27, 2011 at 21:28

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .