This site is supported by donations to The OEIS Foundation. 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. 2
 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 (list; table; graph; refs; listen; history; text; internal format)
 OFFSET 1,3 COMMENTS For the precise definition of T(n,k) see Section 2.4 of Bertagnolli (2013). 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= 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 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=x_2)   ||   (x_3+x_1=x_1)  ) & (  ((floor(x_2 / 2)+x_3

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

Last modified October 23 12:19 EDT 2019. Contains 328345 sequences. (Running on oeis4.)