mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Puzzles (https://www.mersenneforum.org/forumdisplay.php?f=18)
-   -   Mondrian art puzzles - error in Numberphile video (https://www.mersenneforum.org/showthread.php?t=21775)

 cuBerBruce 2016-11-27 20:31

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]

 CRGreathouse 2016-11-27 21:10

I agree!

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

 science_man_88 2016-11-27 21:11

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

 cuBerBruce 2016-11-27 22:08

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

 cuBerBruce 2016-11-28 19:43

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.

 CRGreathouse 2016-11-28 20:12

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

 R. Gerbicz 2016-11-28 23:33

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]

 science_man_88 2016-11-29 01:51

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.

 cuBerBruce 2016-11-29 04:52

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

 EdPeggJr 2016-11-29 19:44

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.

 Batalov 2016-11-30 21:10

[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:

All times are UTC. The time now is 22:57.