login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A234951 Array read by antidiagonals upwards: T(n,k) (n>=1, k>=1) is the solution to the (n,k) stick problem. 4

%I #33 Mar 28 2022 21:38:20

%S 1,1,2,1,3,3,1,3,4,4,1,4,5,6,5,1,4,6,7,7,6,1,4,6,9,9,9,7,1,5,7,9,11,

%T 11,10,8,1,5,7,10,12,14,13,12,9,1,5,8,11,13,14,15,15,13,10,1,5,8,11,

%U 13,16,16,18,17,15,11,1,5,8,12,14,17,18,19,20,19

%N Array read by antidiagonals upwards: T(n,k) (n>=1, k>=1) is the solution to the (n,k) stick problem.

%C For the precise definition of T(n,k) see Section 2.4 of Bertagnolli (2013).

%H A. Bertagnolli, <a href="http://ajbertagnolli.com/wp-content/uploads/2013/10/sticks2.pdf">The Stick Problem</a>, 2013.

%F No (nontrivial) rows or columns have so far been identified.

%F Comments from _Don Reble_, Jan 14 2014: (Start)

%F The second row is floor(3K/2).

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

%F There aren't enough ones for a length-1 K-polygon.

%F The total length is <= (K-1)+K, not enough for a length-2 K-polygon.

%F Part B) With A ones and floor(3K/2)-A twos, one can make a K-sided polygon.

%F If there are K or more ones, make a length-1 K-polygon.

%F If not, then A<K. In any case, one can make length-2 polygon with

%F Q=[floor(3K/2)-A + floor(A/2)] sides.

%F A<K implies A-floor(A/2) = ceiling(A/2) <= floor(K/2)

%F Q = floor(3K/2)-A + floor(A/2)

%F = floor(3K/2) - (A - floor(A/2))

%F >= floor(3K/2) - floor(K/2)

%F = K + floor(K/2) - floor(K/2) = K

%F So the length-2 polygon has at least K sides.

%F ---

%F The third row is 2K-1. The 2K-2 counterexamples are [0,K-1,K-1]

%F (as hinted by Bertagnolli's 4.2).

%F Part B) With A ones, B twos, and 2K-1-(A+B) threes, one can make a K-sided polygon.

%F If there are K or more ones, or K or more twos, make a 1-or-2-length.

%F If not, then A<K and B<K. In any case, one can make a length-3

%F polygon with Q=[2K-1-(A+B) + min(A,B)] sides.

%F A+B = max(A,B) + min(A,B), so

%F Q = 2K-1 - (A+B) + min(A,B) = 2K-1 - max(A,B) > 2K-1 - K = K-1

%F The length-3 polygon has more than K-1 sides, so at least K.

%F (End)

%F Comments from _Alex Meiburg_, Jan 14 2014: (Start)

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

%F 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 nonzero, 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.

%F 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 constructible 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.

%F 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:

%F (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)))

%F 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.

%F 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 were 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.

%F 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.

%F 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.

%F (End)

%e The array begins:

%e n\k| 1 2 3 4 5 6 7 8 9 10 ...

%e --------------------------------------

%e 1 | 1 2 3 4 5 6 7 8 9 10 ...

%e 2 | 1 3 4 6 7 9 10 12 13 15 ...

%e 3 | 1 3 5 7 9 11 13 15 17 19 ...

%e 4 | 1 4 6 9 11 14 15 18 20 23 ...

%e 5 | 1 4 6 9 12 14 16 19 21 24 ...

%e 6 | 1 4 7 10 13 16 18 21 ...

%e 7 | 1 5 7 11 13 17 ...

%e 8 | 1 5 8 11 14 ...

%e 9 | 1 5 8 12 ...

%e 10 | 1 5 8 12 ...

%e 11 | 1 5 ...

%e 12 | 1 5 ...

%e 13 | 1 6 ...

%e 14 | 1 6 ...

%e ...

%K nonn,tabl,nice

%O 1,3

%A _N. J. A. Sloane_, Jan 12 2014. If there are more comments for the Formula section I will create a separate .txt file to contain them all.

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 29 03:51 EDT 2024. Contains 371264 sequences. (Running on oeis4.)