Unsolved problem writeup

[simont]

Thanks to everyone who commented on my previous entry with proofs, software and other useful comments. I think I've now taken the investigation of this problem as far as I have the energy to, at least for the moment. A collection of all the useful things I know about it, including a big pile of data, is now up on a web page: http://www.chiark.greenend.org.uk/~sgtatham/matchsticks/.

Comments

m = 4

[bjh21.me.uk]

Your comment on patterns in column 4 led me to notice that there's a pattern in the optimal dissections in that column that can easily be extended. Here's a new dissector that implements this and hence fills in 27,4 and 29,4:

def col4_dissector(n,m):
    if m != 4: return []
    if n % 2 == 0: return []
    d = (n-1)/2
    bit = Fraction(1, d)
    return [([[(2, (n*bit,) * d), (2, ((n-2)*bit,) * d + (2,))],
              [(1, (2, 2)), (n - 1, (n*bit, (n-2)*bit))]],
             "general pattern for m = 4, n odd")]

Sorry to provide you with additional results just when you thought you'd finished.

[jack]

Oh good, I'm glad to see how far you got.

FWIW, I compared the results to my extended conjecture that all dissections have an equal-length division of SOME stick (and that the other divisions are either equal length, or equal length after removing some fragments from previous divisions), and I thought I was onto something, but if my regex is correct, it fails for exactly one case so far, (23,13).

I looked at that by hand, and indeed, it has no equal-division for any stick. I previously conjectured that if you tried to perturb the smallest-length fragments, and adjust everything else as necessary, that would produce a better dissection, unless it terminated in a contradiction where one stick was equally divided, but you tried to make all the fragments longer or shorter. But (23,13) ends in a contradiction without any equal-division, so so much for that guess. Although it's interesting that we had to go up to fairly high and fairly prime stick lengths in order to find the counter-example.

[angoel.livejournal.com]

n=21, m=5

Best known dissection should be equal to the upper bound of 7/3:

Divide 5 sticks size 21:
2 x (7/3 + 7/3 + 7/3 + 7/3 + 7/3 + 7/3 + 7/3 + 7/3 + 7/3)
3 x (8/3 + 8/3 + 8/3 + 8/3 + 8/3 + 8/3 + 8/3 + 7/3)

Reassemble as 21 sticks size 5:
21 x (7/3 + 8/3)

(Dissection found by me fiddling about when I should have been sleeping)

[angoel.livejournal.com]

n=22, m=5

Best known dissection should be equal to the upper bound of 9/4

Divide 5 sticks size 22:
1 x (11/4 + 11/4 + 11/4 + 11/4 + 11/4 + 11/4 + 11/4 + 11/4)
4 x (9/4 + 9/4 + 10/4 + 5 + 5 + 5)

Reassemble as 22 sticks size 5:
12 x (5)
2 x (10/4 + 10/4)
8 x (9/4 + 11/4)

(Dissection found by me fiddling about when I should have been sleeping)

[angoel.livejournal.com]

n=22, m=6

Best known dissection should be equal to the upper bound of 11/4

Divide 6 sticks size 22:
4 x (13/4 + 13/4 + 13/4 + 13/4 + 3 + 6)
2 x (11/4 + 11/4 + 11/4 + 11/4 + 11/4 + 11/4 + 11/4 + 11/4)

Recombine as 22 sticks size 6:
4 x (6)
2 x (3 + 3)
16 x (11/4 + 13/4)

(Dissection found by me fiddling about when I should have been sleeping)

[angoel.livejournal.com]

n=19, m=7

I believe that the dissection shown 25/8 is the best possible. My reasoning is as follows:

Any better divisor must divide all size 7 sticks into two substicks size between 25/8 and 31/8. (Subdivisions of 3 would be size at best 7/3 - contradiction; subdivisions of 1 can be treated as two substicks size 7/2).

These size constraints mean that four of the size 19 sticks must be divided into five and three of them must be divided into six. By the pigeonhole principle, one of the size seven sticks must have both subpieces the size 19 sticks divided into five. Call this stick A.

Consider the sub-pieces of stick A, and choose the smaller of them; this can be at most size 7/2. Consider the other subpieces in the size 19 stick this is in; the largest of the remaining four subpieces must size (19 - 7/2) / 4 = 31/8 or greater. The the other half of this subpiece must be size 25/8 or smaller.

Therefore 25/8 is the best divisor.

[simont]

bjh21 and I (well, mostly him) have generalised that reasoning and applied it to the table, and it's made a pleasing number of extra cells green. Thanks for this!

[angoel.livejournal.com]

Excellent - you've saved me the effort of doing it.

I note that your proof states an assumption "and also the resulting 2n pieces are distributed as evenly as possible between the n-sticks (i.e. every n-stick is composed of at least ⌊2n/m⌋ and at most ⌈2n/m⌉ pieces)".

I don't think this is required to be an assumption - if any n-stick is composed of fewer than ⌊2n/m⌋ pieces, the bound holds trivially, and n-sticks consisting of more than than ⌈2n/m⌉ pieces cannot result in there being fewer n-sticks made out of ⌊2n/m⌋ pieces (and the number of n-sticks made out of ⌊2n/m⌋ pieces is what the proof depends on).

[angoel.livejournal.com]

I think that you may be able to use a fairly similar proof but reversed to prove (11,9), (19,11), (29,13), (17,14), (26,15) and (22,18) are optimal. (i.e. n-sticks are divided into two; one n-stick must have both sub-pieces appear in m-sticks which have ⌈2n/m⌉ pieces; consider the m-stick which has the larger piece; the remaining ⌈2n/m⌉ pieces must be smaller than X.)

[angoel.livejournal.com]

n=23, m=5

Best known dissection should be equal to the upper bound of 23/10.

Cut up 5 sticks of length 23 as follows:
1 x (23/10 + 23/10 + 23/10 + 23/10 + 23/10 + 23/10 + 23/10 + 23/10 + 23/10 + 23/10)
1 x (27/10 + 27/10 + 27/10 + 27/10 + 27/10 + 24/10 + 24/10 + 24/10 + 23/10)
3 x (27/10 + 27/10 + 27/10 + 27/10 + 27/10 + 26/10 + 23/10 + 23/10 + 23/10)

Reassemble as 23 sticks of length 5 as follows:
20 × (23/10 + 27/10)
3 × (24/10 + 26/10)

[angoel.livejournal.com]

n=24, m=5

Best known dissection should be equal to the upper bound of 7/3:

Divide 5 sticks size 24:
3 x (7/3 + 7/3 + 7/3 + 7/3 + 7/3 + 7/3 + 7/3 + 7/3 + 8/3 + 8/3)
2 x (8/3 + 8/3 + 8/3 + 8/3 + 8/3 + 8/3 + 8/3 + 8/3 + 8/3)

Reassemble as 24 sticks size 5:
24 x (7/3 + 8/3)

[angoel.livejournal.com]

n=26, m=5

Best known dissection should be equal to the upper bound of 7/3:

Divide 5 sticks size 26:
3 x (7/3 + 7/3 + 7/3 + 7/3 + 7/3 + 7/3 + 7/3 + 7/3 + 7/3 + 7/3 + 8/3)
2 x (7/3 + 7/3 + 8/3 + 8/3 + 8/3 + 8/3 + 8/3 + 8/3 + 8/3 + 8/3)

Reassemble as 26 sticks size 5:
24 x (7/3 + 8/3)

[simont]

Thanks for all these! It seems to me that there's probably room for a search program focusing specifically on some kind of identifiable easy case along these lines (something like, divide all the short sticks up the same way and then see what you can do with the long ones), if neither of our existing search programs found these fairly obvious-looking answers given half an hour of CPU time per instance...

The one above doesn't seem quite right to me, though: (a) I think the number of pieces only adds up if you have 2 x the first arrangement and 3 x the second, not vice versa; (b) the short sticks should read 26 x (7/3 + 8/3) not 24; and (c) 7/3 isn't the proven upper bound for (26,5) at all, 26/11 is.

[angoel.livejournal.com]

That's OK - it's a fun problem, and it's nice to be decreasing the amount of red in the grid.

With respect to (26,5), you're right - I think that I'd got myself confused when looking at the various different dissections. Apologies about that.

[simont]

Actually, ahem. One of the existing search programs could perfectly well have found those and more, if it hadn't been for an optimisation bug or two. I'm updating the web page: now only one remaining red cell exists, namely (29,9).

[angoel.livejournal.com]

Yay! All the red has been defeated. Except for (29,9). So I attacked that and came up with 41/10 which I think is provably optimal using similar logic as for (19,7) above.

Best known dissection should be equal to 41/10:

Divide 9 sticks size 29:

2 x (41/10 + 41/10 + 41/10 + 41/10 + 41/10 + 17/4 + 17/4)
2 x (33/8 + 33/8 + 33/8 + 33/8 + 25/6 + 25/6 + 25/6)
2 x (49/10 + 49/10 + 49/10 + 49/10 + 49/10 + 9/2)
2 x (39/8 + 39/8 + 39/8 + 39/8 + 19/4 + 19/4)
1 x (29/6 + 29/6 + 29/6 + 29/6 + 29/6 + 29/6)

Reassemble as 29 sticks size 9:
10 x (41/10 + 49/10)
8 x (33/8 + 39/8)
6 x (25/6 + 29/6)
4 x (19/4 + 17/4)
1 x (9/2 + 9/2)

[simont]

Gosh. Well found. That solution wasn't found by my solver for a good reason – it violates my conjecture about the denominator bound!

That is, it violates the stronger form of it on which my search program depends: although the denominator of the minimum fragment size is less than n, the lowest common denominator for the whole solution is not, since in this case it's 120. My program searches whole-solution denominators up to n, and the best it found for this instance was a min fragment of 4.

That suggests that other yellow cells may not have the values they should have either...

[angoel.livejournal.com]

I'm not sure you need to go all the way up to 120 - when putting together this dissection, I worked to maximise all stick lengths, but if you accept that the lower bound is 41/10, you can shorten some stick lengths to give a denominator of 10 throughout (which, as a bonus, gives a simpler dissection).

Of course, this does mean that your program should probably be looking for larger denominators...

Best known dissection should be equal to 41/10:

Divide 9 sticks size 29:

4 x (41/10 + 41/10 + 41/10 + 41/10 + 42/10 + 42/10 + 42/10)
3 x (48/10 + 48/10 + 48/10 + 48/10 + 49/10 + 49/10)
2 x (49/10 + 49/10 + 49/10 + 49/10 + 49/10 + 45/10)

Reassemble as 29 sticks size 9:
16 x (41/10 + 49/10)
12 x (42/10 + 48/10)
1 x (45/10 + 45/10)

[simont]

Ah, thank you. Program debugged again, and now it does find that dissection.