Mondrian Art Puzzle
The latest Numberphile video concerns a math puzzle based on the artworks for Piet Mondrian (Scroll to bottom of post for some corrections and updates)
Here's the video featuring Gordon Hamilton:
More can be found at Gord's Math Pickle website.
A man who has done some additional work in this area is Ed Pegg Jr.
I had some useful correspondence with him. This demonstration created by Ed is very useful.
And some of our correspondence is shared below with his permission.
---
I'm using two methods. The numerical one can start with the areas of all rectangles that can be cut from a square. For example, the 9x9 can have subrectangles of area 1, 2, 3, 4, 4, 5, 6, 6, 7, 8, 8, 9, 9, 10, 12, 12, 14, 15, 16, 16, 18, 18, 20, 21, 24, 24, 25, 27, 28, 30, 32, 35, 36, 36, 40, 42, 45, 48, 49, 54, 56, 63, 64, 72, 81. One easy cut is 4x5 and 5x5, for a difference of 9. So look for all ranges less than that, and see if they can be put back together.
The other method uses graphs. The number of graphs gets high fast.
http://www.numericana.com/data/polycount.htm
For example, 1000 by 1000 might need 35 rectangles, with 5986979643542 graphs to check through. But it might be more.
Both methods become computationally difficult pretty quickly. I'm not sure which of my solutions up to 32 can be considered unbeatable. I was just trying for a hard-to-beat baseline. It probably wouldn't be too hard to do a numerical analysis of the existing solutions and check to see if there was a smaller range that might yield a solution.
---
I should start by mentioning the Mrs. Perkin's Quilt problem. For a given square, divide it into smaller squares so that the sizes are relatively prime. Solved for smaller values back in the 1950's. I use the old programs on new computers and extended the results. Details of the older programs at squaring.net.
http://demonstrations.wolfram.com/MrsPerkinssQuilts/
From a crushed version of those squares, I developed the Mondrian puzzles
http://demonstrations.wolfram.com/MondrianPuzzles/In PickleMondrain.nb, I give all the solutions I had up to 32.In mondrian.xmpuzzle, I give a set-up file for Burr Tools.
http://burrtools.sourceforge.net/Let's look at the 6x6. The range of rectangles 4, 4, 5, 6, 8, 9 might be a solution. Over in Burr Tools, you can use the 6x6 as a goal and then pick out the rectangles with those areas. Note that you have two choices for the area 6 rectangle and can only choose one at a time. Sometimes you might have 40 or more combinations to go though. the 6x6 is solved readily.For the 9x9, there is a known solution with defect 6. There is a possible split with areas 14, 15, 16, 18, 18. With Burr Tools, we can prove that split is impossible. So the 9x9 is proven optimal.For 10x10 to 17x17, I pretty much did that. I may have missed a few combos somewhere, but probably not.For the 18x18, there is a defect 10 solution. There are four area sets that might give a defect 8 solution. I used Burr Tools to check all the combos, and none of them gave solutions. So the 18x18 is proven optimal.For the 19x19 a defect 11 solution was known. Just now, I looked at the promising defect 9 case, and found a solution with Burr Tools. All of the solutions there had two rectangles sharing a full edge, so they wouldn't be found in a search of 3-connected graphs with the electrical method.For 20-32, it looks like there are many smaller cases I didn't check. It would likely be possible to check through all of them by hand within a few days. My gut feeling is that there might be 2 or 3 improvements if all cases and combos were checked.
After doing these for a while, you start to appreciate complete sets of rectangles, because that usually means a low defect and only 1 combo to check. For the 36x36, I noticed that the 24 rectangles of area 48 to 60 might work. Burr Tools immediately found hundreds of solutions.
Then I branched out into 3D. Is it possible to make a polyhedron out of different rectangles? I managed to do it with 30 rectangles.
http://community.wolfram.com/groups/-/m/t/928487Is it possible to divide a square into different rectangles so that all the diagonal have the same length? I solved that one, too.http://math.stackexchange.com/questions/1958738/same-diagonal-dissectionHope that helps.
POST SCRIPT: After the video was published, Ed improved his 25x25 score from 12 to 11... Here is the result...
POST SCRIPT 2: Ed reports Bruce Norskog found an improvement to n(18). Ed himself went through and rechecked everything, and also found improvements for n(15) and n(19).
OEIS Sequence: https://oeis.org/A276523