Mondrian art puzzles - error in Numberphile video
 

The recent [url=https://www.youtube.com/watch?v=49KvZrioFB0]Numberphile video about Mondrian art puzzles[/url] has an error.

It claims that the best Mondrian score for an 18x18 square is 10. But I've achieved a Mondrian score of 8 for it.

[CODE]
[SPOILER]
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ? ? ? ?
^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ? ? ? ?
% % % < < < < < # # # # # # ? ? ? ?
% % % < < < < < # # # # # # ? ? ? ?
% % % < < < < < # # # # # # ? ? ? ?
% % % < < < < < # # # # # # ? ? ? ?
% % % < < < < < # # # # # # ? ? ? ?
% % % < < < < < # # # # # # ? ? ? ?
% % % > > > > > > > + + + + ? ? ? ?
% % % > > > > > > > + + + + = = = =
% % % > > > > > > > + + + + = = = =
% % % > > > > > > > + + + + = = = =
% % % > > > > > > > + + + + = = = =
@ @ @ @ @ @ @ @ @ @ + + + + = = = =
@ @ @ @ @ @ @ @ @ @ + + + + = = = =
@ @ @ @ @ @ @ @ @ @ + + + + = = = =
[/SPOILER]
[/CODE]

I agree!

You should send in a correction to [url=https://oeis.org/A276523]A276523[/url] and maybe send Ed an email.

[QUOTE=cuBerBruce;447919]The recent [url=https://www.youtube.com/watch?v=49KvZrioFB0]Numberphile video about Mondrian art puzzles[/url] has an error.

It claims that the best Mondrian score for an 18x18 square is 10. But I've achieved a Mondrian score of 8 for it.

[/QUOTE]

the description of that video also said that a new lowest 25 by 25 was found cool find either way. edit: I of course have mostly useless information as to how to make a solution other than if T(x)<n^2<T(x+1) then at most x distinct areas can exist.

[QUOTE=CRGreathouse;447920]I agree!

You should send in a correction to [url=https://oeis.org/A276523]A276523[/url] and maybe send Ed an email.[/QUOTE]

I've now sent Ed an email.

Ed has informed me that A276523 has now been corrected. The correction also include new values for 15x15 and 19x19 cases, found by Ed after further checking.

[QUOTE=cuBerBruce;447995]Ed has informed me that A276523 has now been corrected. The correction also include new values for 15x15 and 19x19 cases, found by Ed after further checking.[/QUOTE]

Thanks to both of you! I approved the changes.

Really fascinating puzzle!
My exahaustive code gives the following better solutions (these are optimal):
a(14)=6 (!!!)
[CODE]
aaaaaaaaaabbbb
aaaaaaaaaabbbb
aaaaaaaaaabbbb
cccdddddddbbbb
cccdddddddbbbb
cccdddddddbbbb
cccdddddddbbbb
cccdddddddbbbb
ccceeeeeffffff
ccceeeeeffffff
ccceeeeeffffff
ccceeeeeffffff
ccceeeeeffffff
ccceeeeeffffff
[/CODE]
a(16)=8
[CODE]
aaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaa
bbbbbbbbbbccccdd
bbbbbbbbbbccccdd
bbbbbbbbbbccccdd
eeefffffffccccdd
eeefffffffccccdd
eeefffffffccccdd
eeefffffffccccdd
eeefffffffccccdd
eeeggggghhhhhhdd
eeeggggghhhhhhdd
eeeggggghhhhhhdd
eeeggggghhhhhhdd
eeeggggghhhhhhdd
eeeggggghhhhhhdd
[/CODE]
a(23)=8
[CODE]
aaaaaaaaaaaaaaaaaabbbbb
aaaaaaaaaaaaaaaaaabbbbb
aaaaaaaaaaaaaaaaaabbbbb
aaaaaaaaaaaaaaaaaabbbbb
cccccccceeeeffffffbbbbb
cccccccceeeeffffffbbbbb
cccccccceeeeffffffbbbbb
cccccccceeeeffffffbbbbb
cccccccceeeeffffffbbbbb
cccccccceeeeffffffbbbbb
cccccccceeeeffffffbbbbb
cccccccceeeeffffffbbbbb
cccccccceeeeffffffbbbbb
ddddddddeeeeffffffbbbbb
ddddddddeeeeffffffbbbbb
ddddddddeeeeffffffbbbbb
ddddddddeeeeggggggggggg
ddddddddeeeeggggggggggg
ddddddddeeeeggggggggggg
ddddddddeeeeggggggggggg
ddddddddeeeeggggggggggg
ddddddddeeeeggggggggggg
ddddddddeeeeggggggggggg
[/CODE]
a(25)=10
[CODE]
aaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaa
bbbbbbbbbbbbbbbbbbbbccccc
bbbbbbbbbbbbbbbbbbbbccccc
ddeeeeeeeffffkkkkkkkccccc
ddeeeeeeeffffkkkkkkkccccc
ddeeeeeeeffffkkkkkkkccccc
ddeeeeeeeffffkkkkkkkccccc
ddeeeeeeeffffkkkkkkkccccc
ddeeeeeeeffffkkkkkkkccccc
ddeeeeeeefffflllllllllmmm
ddggghhhhfffflllllllllmmm
ddggghhhhfffflllllllllmmm
ddggghhhhfffflllllllllmmm
ddggghhhhfffflllllllllmmm
ddggghhhhjjjjjjjjnnnnnmmm
ddggghhhhjjjjjjjjnnnnnmmm
ddggghhhhjjjjjjjjnnnnnmmm
ddggghhhhjjjjjjjjnnnnnmmm
ddggghhhhjjjjjjjjnnnnnmmm
ddggghhhhjjjjjjjjnnnnnmmm
ddgggiiiiiiiiiiiinnnnnmmm
ddgggiiiiiiiiiiiinnnnnmmm
ddgggiiiiiiiiiiiinnnnnmmm
ddgggiiiiiiiiiiiinnnnnmmm
[/CODE]
a(26)=9
[CODE]
aaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaa
bbbbbbbbbbbbbbbbccccccccdd
bbbbbbbbbbbbbbbbccccccccdd
bbbbbbbbbbbbbbbbccccccccdd
eeegggggggggggggccccccccdd
eeegggggggggggggccccccccdd
eeegggggggggggggccccccccdd
eeegggggggggggggccccccccdd
eeehhhhiiiiiiiiiiiiiiiiidd
eeehhhhiiiiiiiiiiiiiiiiidd
eeehhhhiiiiiiiiiiiiiiiiidd
eeehhhhjjjjjkkkkkkkkkkkkdd
eeehhhhjjjjjkkkkkkkkkkkkdd
eeehhhhjjjjjkkkkkkkkkkkkdd
eeehhhhjjjjjkkkkkkkkkkkkdd
eeehhhhjjjjjlllllllmmmmmdd
eeehhhhjjjjjlllllllmmmmmdd
eeehhhhjjjjjlllllllmmmmmdd
eeehhhhjjjjjlllllllmmmmmdd
eeehhhhjjjjjlllllllmmmmmdd
eeehhhhjjjjjlllllllmmmmmdd
eeehhhhjjjjjlllllllmmmmmdd
fffffffffffffffffffmmmmmdd
fffffffffffffffffffmmmmmdd
fffffffffffffffffffmmmmmdd
[/CODE]
a(27)=10
[CODE]
aaaaaaaaaaaaaaaaaaaaaaaabbb
aaaaaaaaaaaaaaaaaaaaaaaabbb
ccdddddddddddddddeeeefffbbb
ccdddddddddddddddeeeefffbbb
ccdddddddddddddddeeeefffbbb
ccgghhhhhhiiiiiiieeeefffbbb
ccgghhhhhhiiiiiiieeeefffbbb
ccgghhhhhhiiiiiiieeeefffbbb
ccgghhhhhhiiiiiiieeeefffbbb
ccgghhhhhhiiiiiiieeeefffbbb
ccgghhhhhhiiiiiiieeeefffbbb
ccgghhhhhhiiiiiiieeeefffbbb
ccggjjjjjjlllllllllllfffbbb
ccggjjjjjjlllllllllllfffbbb
ccggjjjjjjlllllllllllfffbbb
ccggjjjjjjlllllllllllfffbbb
ccggjjjjjjmmmmmmmmmmmmnnnnn
ccggjjjjjjmmmmmmmmmmmmnnnnn
ccggjjjjjjmmmmmmmmmmmmnnnnn
ccggjjjjjjmmmmmmmmmmmmnnnnn
ccggkkkkkkkkoooooooooonnnnn
ccggkkkkkkkkoooooooooonnnnn
ccggkkkkkkkkoooooooooonnnnn
ccggkkkkkkkkoooooooooonnnnn
ccggkkkkkkkkoooooooooonnnnn
ccggppppppppppppppppppppppp
ccggppppppppppppppppppppppp
[/CODE]
a(28)=9
[CODE]
aaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaa
bbbbbbbbbbbbbbbbbbbbbbbbbccc
bbbbbbbbbbbbbbbbbbbbbbbbbccc
ddddddddddddddddddeeeffffccc
ddddddddddddddddddeeeffffccc
ddddddddddddddddddeeeffffccc
hhhhhjjjjjjkkkkkkkeeeffffccc
hhhhhjjjjjjkkkkkkkeeeffffccc
hhhhhjjjjjjkkkkkkkeeeffffccc
hhhhhjjjjjjkkkkkkkeeeffffccc
hhhhhjjjjjjkkkkkkkeeeffffccc
hhhhhjjjjjjkkkkkkkeeeffffccc
hhhhhjjjjjjkkkkkkkeeeffffccc
hhhhhjjjjjjkkkkkkkeeeffffccc
hhhhhllllmmmmmmmmmeeeffffccc
hhhhhllllmmmmmmmmmeeeffffccc
iiiiillllmmmmmmmmmeeeffffccc
iiiiillllmmmmmmmmmeeeggggggg
iiiiillllmmmmmmmmmeeeggggggg
iiiiillllmmmmmmmmmeeeggggggg
iiiiillllnnnnnnnnnnnnggggggg
iiiiillllnnnnnnnnnnnnggggggg
iiiiillllnnnnnnnnnnnnggggggg
iiiiillllnnnnnnnnnnnnggggggg
iiiiillllooooooooooooooooooo
iiiiillllooooooooooooooooooo
iiiiillllooooooooooooooooooo
[/CODE]

you can upper bound if for even n by using either 2n if the solution for n/2 is greater than n\4 or 4 times the solution for n\2 otherwise. edit: so for example using the 17 by 17 bound in the video is 8 so we can say with confidence that for 34 by 34 the minimum solution is upper bounded by 32. and for the n=23 example above we can say that now for n=46 the minimal solution is not greater than 32 as well. sorry adding trivialities to the thread.

[QUOTE=R. Gerbicz;448005]Really fascinating puzzle!
My exahaustive code gives the following better solutions (these are optimal):
[/QUOTE]

Good job, R. Gerbicz! Wow, I am surprised that as many as 6 cases thought to be proven optimal have been improved. I haven't rigorously checked your solutions, but I've verified with my own solver code that the scores for at least the smaller ones (up to 23x23) are achievable.

A little bit more about my initial find...

[url=http://mathpickle.com/project/mondrian-art-puzzles/]This web page[/url] listed what had been believed to be the optimal Mondrian scores for 4x4 up to 17x17. So after I found solutions that I thought were optimal for squares up to 17x17, I looked for a solution for the 18x18 square with a score that matched the 17x17 value.

After my program generated many solutions (having a score of 8), I tried to find one manually on my own. I struggled for awhile, so I finally peeked at part of one of the solutions found by my computer. I was able to complete the 18x18 square by trial and error from the set of rectangles the computer was using, and that is the solution I posted.

It probably wasn't until a couple days later or so that I realized that this solution had a score that was better by 2 than what was being claimed to be the best possible score. Until then, I didn't think my solution was anything special. Of course, I then realized I should post my solution online right away.

Many thanks for the improved solutions. I found a few bugs in my coding. I'll be posting an update at [url]http://demonstrations.wolfram.com/MondrianArtProblem/[/url] in the near future.

[QUOTE=EdPeggJr;448051]Many thanks for the improved solutions. I found a few bugs in my coding. I'll be posting an update at [url]http://demonstrations.wolfram.com/MondrianArtProblem/[/url] in the near future.[/QUOTE]

Welcome to the forum! :hello: