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]

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.