TAOCP 7.2.2.1 Exercise 375

Solution to TAOCP 7.2.2.1 Exercise 375.

taocpmathematicsalgorithmsvolume-4math-hard

Section 7.2.2.1: Dancing Links

Exercise 375. [M29] [M29] Among all the incomparable dissections of order (a) seven and (b) eight, restricted to integer sizes, find the rectangles with the smallest possible semiperimeter (height plus width). Also find the smallest possible squares that have incomparable dissections in integers. Hint: Show that there are $2^l$ potential ways to fix the $b$'s with the $u$'s, preserving their order; and find the smallest semiperimeter for each of those cases.

Verified: no
Solve time: 3m26s