A234951 Array read by antidiagonals upwards: T(n,k) (n>=1, k>=1) is the solution to the (n,k) stick problem.
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, 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, 13, 16, 16, 18, 17, 15, 11, 1, 5, 8, 12, 14, 17, 18, 19, 20, 19
Offset: 1
Examples
The array begins: n\k| 1 2 3 4 5 6 7 8 9 10 ... -------------------------------------- 1 | 1 2 3 4 5 6 7 8 9 10 ... 2 | 1 3 4 6 7 9 10 12 13 15 ... 3 | 1 3 5 7 9 11 13 15 17 19 ... 4 | 1 4 6 9 11 14 15 18 20 23 ... 5 | 1 4 6 9 12 14 16 19 21 24 ... 6 | 1 4 7 10 13 16 18 21 ... 7 | 1 5 7 11 13 17 ... 8 | 1 5 8 11 14 ... 9 | 1 5 8 12 ... 10 | 1 5 8 12 ... 11 | 1 5 ... 12 | 1 5 ... 13 | 1 6 ... 14 | 1 6 ... ...
Links
- A. Bertagnolli, The Stick Problem, 2013.
Formula
No (nontrivial) rows or columns have so far been identified.
Comments from Don Reble, Jan 14 2014: (Start)
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
Q=[floor(3K/2)-A + floor(A/2)] sides.
A
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
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.
(End)
Comments from Alex Meiburg, Jan 14 2014: (Start)
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 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.
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
The condition corresponding to sides of length 4 would then be floor(x_2/2) + min(x_3, x_1)
(x_1=x_2) || (x_3+x_1=x_1) ) & ( ((floor(x_2 / 2)+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 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.
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.
(End)
Comments