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

[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.)