[seqfan] Re: Nice new sequence based on the "sticks problem"

[Alex M]

Indeed, I think he mentions that in the paper. It's nice to have a proof
though. :)

I'm particularly curious about column two -- it seems to be a pretty simple
question, really; it answers the questions "How many items between 1 and N
can you pick, such that no two non-zero, non-intersecting subsets have the
same sum". This is NP Hard to check (very close to the knapsack problem) in
a specific instance, but one would hope that it has some sort of simple
solution.

I have the following proof that each row grows asymptotically linearly
(and, I believe, with a periodic deviation from the exact linear fit):

View the problem of picking the x_i objects, for i=1 to n, as picking a
point in Z^n. That is, the tuples they list in their paper e.g. (0,4,4) as
a counterexample, corresponds to the point (0,4,4) in 3-space. Now each of
the constraints can be modeled by a set of hyperplanes. For instance, each
n has the limitation that x_1<k, which corresponds to the restriction on
making k sides of length 1. For sides of length 2, we have  x_2 + floor(x_1
/ 2)<k, where the left hand side the maximum sides of length 2
constructable as a function of x_1 and x_2. For sides of length 3, the
expression is a bit more complex: x_3 + min(x_2, x_1) +
max(0,floor((x_1-x_2)/3))<k. The min/max are responsible for describing
either the case where we have more 1s than 2s, in which case it simplifies
to x_3+x_2+floor((x_1-x_2)/3), or the case where we have more 2s than 1s,
in which case it simplifies to x_3+x_1. These two cases can be combined
into one boolean condition, then, based on which of the two cases is true.
The condition corresponding to sides of length 4 would then be floor(x_2 /
2) + min(x_3, x_1)<k. It can similarly be split based on which of the two
cases is true, then. We could look at sides of length 5 and above, but
obviously these are rendered superfluous by the lower numbers. The
condition is as follows, then, for the full case of n=3:

(x_1<k) && (x_2 + floor(x_1/2)<k) && (  (x_3+x_2+floor((x_1-x_2)/3)<k &&
x_1>=x_2)   ||   (x_3+x_1<k && x_2>=x_1)  ) && (  ((floor(x_2 / 2)+x_3<k)
&& (x_3<=x_1) || ((floor(x_2 / 2)+x_1<k) && (x_1<=x_3)))

It should be clear that any kind of expression involving max/min can be
split up similarly. The general algorithm for generating such an algorithm
for any n is to look at each side length (until the maximum side length is
reached, which can be bounded by n(n+1)/2, because in order to make k
copies of that we already have at least k-1 copies of one of the numbers
from 1 to n), find the various permutations that generate it, put them in a
max() function to choose the one that will generate the most, and then
break this max apart into several conditions.

This boolean expression, no matter how complicated, is only composed of
linear combinations and floors (the only non-linear element, which I'm
going to call pseudo-linear) -- and, crucially, is fixed for a given n, so
we can change k and the condition remains the same. In n-space, this
condition defines a polytope -- if it was just a bunch of inequalities
joined with &&, then we would have the simplex problem; with the max, we
get concavities in our solution space. Still, it's entirely pseudo-linear.
The problem is maximizing x_1+x_2+x_3..., amid these conditions. This
maximum solution is then the "counterexample", and adding one more is
necessarily outside of the solution set.

All of these pseudo-linear conditions only deviate by a bounded value from
a true linear condition. It's not hard to see that, as k varies and these
hyperplanes move, they add a constant linear amount to that maximizing
vertex - look at solutions of the simplex algorithm with a similar setup.
Thus, as k varies, the sequence as a whole grows roughly linearly. The only
deviations are due to the floor functions, which are periodic. This leads
me to believe that the deviation from an "exact" linear solution is
periodic as well, although I'm not sure how to prove this or find the
period exactly.

~6 out of 5 statisticians say that the
number of statistics that either make
no sense or use ridiculous timescales
at all has dropped over 164% in the
last 5.62474396842 years.


On Tue, Jan 14, 2014 at 7:35 PM, Don Reble <djr at nk.ca> wrote:

> As the author says, none of the rows or columns seem to be in the
>> OEIS, and no formulas are known!
>>
>
>    The second row is floor(3K/2).
>
>    Part A) With K-1 ones and floor(K/2) twos, one can't make a K-sided
>            polygon. (Total sticks: floor(3K/2)-1.)
>    There aren't enough ones for a length-1 K-polygon.
>    The total length is <= (K-1)+K, not enough for a length-2 K-polygon.
>
>    Part B) With A ones and floor(3K/2)-A twos, one can make a K-sided
>            polygon.
>    If there are K or more ones, make a length-1 K-polygon.
>    If not, then A<K. In any case, one can make length-2 polygon with
>    Q=[floor(3K/2)-A + floor(A/2)] sides.
>
>        A<K implies A-floor(A/2) = ceiling(A/2) <= floor(K/2)
>
>    Q = floor(3K/2)-A + floor(A/2)
>      = floor(3K/2) - (A - floor(A/2))
>     >= floor(3K/2) - floor(K/2)
>      = K + floor(K/2) - floor(K/2) = K
>
>    So the length-2 polygon has at least K sides.
>
>    ---
>
>    The third row is 2K-1. The 2K-2 counterexamples are [0,K-1,K-1]
>    (as hinted by Bertagnolli's 4.2).
>
>    Part B) With A ones, B twos, and 2K-1-(A+B) threes, one can make a
>            K-sided polygon.
>    If there are K or more ones, or K or more twos, make a 1-or-2-length.
>    If not, then A<K and B<K. In any case, one can make a length-3
>    polygon with Q=[2K-1-(A+B) + min(A,B)] sides.
>
>    A+B = max(A,B) + min(A,B), so
>
>    Q = 2K-1 - (A+B) + min(A,B) = 2K-1 - max(A,B) > 2K-1 - K = K-1
>        The length-3 polygon has more than K-1 sides, so at least K.
>
>
>
> ---
>
>    P.S. Hey! While I composed this message, my program finished
>         calculating A059958(18). But I have to check some things.
>         Film at 11...
>
> --
> Don Reble  djr at nk.ca
>
>
>
> _______________________________________________
>
> Seqfan Mailing list - http://list.seqfan.eu/
>