Cutting sticks puzzle

Solution 1:

This is not a solution, just something I found that might be relevant.

On the page linked to in the question, a reduction and various strategies are considered. I'll briefly reproduce the reduction, both because I think it's the most useful part of that page and perhaps not everyone will want to read that entire page, and also because I need it to say what I found.

Let a counterexample with minimal $n$ be given. If one of the sticks were of length $n$, we could use that stick as the target stick of length $n$ and cut the remaining sticks into lengths $1$ through $n-1$, since otherwise they would form a smaller counterexample. Likewise, if one of the sticks had length greater than $2n-2$, we could cut off a stick of length $n$ and the remaining sticks would all be of length $\ge n-1$, so again we could cut them into lengths $1$ through $n-1$ because otherwise they would form a smaller counterexample. Thus,

the lengths of the sticks in a counterexample with minimal $n$ must be $\gt n$ and $\lt 2n-1$.

Problem instances that satisfy these conditions for a potential minimal counterexample are called "hard" on that page; I suggest we adopt that terminology here.

The strategies discussed on that page include various ways of forming the target sticks in order of decreasing length. It was found that there are counterexamples both for the strategy of always cutting the next-longest target stick from the shortest possible remaining stick (counterexample $\langle11,12,16,16\rangle$) and for the strategy of always cutting the next-longest target stick from the longest remaining stick unless it already exists (counterexample $\langle10,10,12,13\rangle$), whereas if the stick to cut from was randomized, it was always possible to form the desired sticks up to $n=23$.

I've checked that all hard problem instances up to $n=30$ are solvable, and I found that they remain solvable independent of which stick we cut the target stick of length $n$ from. This is equivalent to saying that a problem instance for $n-1$ can always be solved if all stick lengths except one are $\gt n$ and $\lt 2n-1$ and one is $\lt n-1$, since all of these instances can result from cutting a stick of length $n$ from a hard problem instance for $n$.

I thought that this might be generalized to the solvability of an instance being entirely determined by whether the sticks of length $\le n$ can be cut to form distinct integers, but that's not the case, since it's possible to leave only a few holes below $n$ such that the few remaining sticks above $n$ can't fill them.

Solution 2:

I have implemented the suggestion I made in a comment to joriki's answer. For $3 \le n \le 18$, I have generated a list of subsets $S \subset \{1,2,...,n-1\}$ with the property that if a set of sticks with total length $n(n+1)/2$ takes all the lengths in $S$, together with any other lengths ≥n, then the sticks can always be cut into sticks of length $1,2,...,n$. It is available at this link (it's about 900K).

I stared at it for a while, but nothing jumped out at me.

Edited to add: I have changed the program to output the sets in a more human-friendly order: part 1 (n = 1 to 17) and part 2 (n = 18).

Solution 3:

There are variations on the problem where the division is always possible and a proof using complete induction.

The first variation is: [..original problem ...] where at least one of the sticks is >=2n.
The second variation is: [..original problem ...] where it is allowed to glue two of the sticks together and break once at an arbitrary position.

Proof for the variations:

The case n=1 is trivial - one stick of length 1. Then we suppose the assumption holds for n and consider the case n+1. I.e. given a number of sticks of integral length >= n+1 whose lengths add to (n+1)(n+2)/2 - can these be divided into sticks of lengths 1,2,3,…,n+1?

Break off from one of the sticks a length n+1. In the first variation we use the stick with lenght >= 2n+2. This part will be the required stick of length n+1 in the solution. Because we broke off a length n+1 the remaining total length is (n+1)(n+2)/2 - (n+1) = n(n+1)/2. In the first variation the inducution step is valid, in the second variation we may not yet use the induction step because the other part of the broken stick may now be smaller then n+1. In that case the second variation allows us to glue together this part with one of the other sticks. Now the induction step is valid and we break the rest of the collection of sticks in {1,..n} and have succeeded in the division {1,.. n+1}.