mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2016-11-27, 20:31   #1
cuBerBruce
 
cuBerBruce's Avatar
 
Aug 2012
Mass., USA

2×3×53 Posts
Default Mondrian art puzzles - error in Numberphile video

The recent Numberphile video about Mondrian art puzzles 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:

~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ? ? ? ?
^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ? ? ? ?
% % % < < < < < # # # # # # ? ? ? ?
% % % < < < < < # # # # # # ? ? ? ?
% % % < < < < < # # # # # # ? ? ? ?
% % % < < < < < # # # # # # ? ? ? ?
% % % < < < < < # # # # # # ? ? ? ?
% % % < < < < < # # # # # # ? ? ? ?
% % % > > > > > > > + + + + ? ? ? ?
% % % > > > > > > > + + + + = = = =
% % % > > > > > > > + + + + = = = =
% % % > > > > > > > + + + + = = = =
% % % > > > > > > > + + + + = = = =
@ @ @ @ @ @ @ @ @ @ + + + + = = = =
@ @ @ @ @ @ @ @ @ @ + + + + = = = =
@ @ @ @ @ @ @ @ @ @ + + + + = = = =
cuBerBruce is offline   Reply With Quote
Old 2016-11-27, 21:10   #2
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

173216 Posts
Default

I agree!

You should send in a correction to A276523 and maybe send Ed an email.
CRGreathouse is offline   Reply With Quote
Old 2016-11-27, 21:11   #3
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

202618 Posts
Default

Quote:
Originally Posted by cuBerBruce View Post
The recent Numberphile video about Mondrian art puzzles 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.
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.

Last fiddled with by science_man_88 on 2016-11-27 at 22:10
science_man_88 is offline   Reply With Quote
Old 2016-11-27, 22:08   #4
cuBerBruce
 
cuBerBruce's Avatar
 
Aug 2012
Mass., USA

2·3·53 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
I agree!

You should send in a correction to A276523 and maybe send Ed an email.
I've now sent Ed an email.
cuBerBruce is offline   Reply With Quote
Old 2016-11-28, 19:43   #5
cuBerBruce
 
cuBerBruce's Avatar
 
Aug 2012
Mass., USA

4768 Posts
Default

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.
cuBerBruce is offline   Reply With Quote
Old 2016-11-28, 20:12   #6
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

2·2,969 Posts
Default

Quote:
Originally Posted by cuBerBruce View Post
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.
Thanks to both of you! I approved the changes.
CRGreathouse is offline   Reply With Quote
Old 2016-11-28, 23:33   #7
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

26118 Posts
Default

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
a(16)=8
Code:
aaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaa
bbbbbbbbbbccccdd
bbbbbbbbbbccccdd
bbbbbbbbbbccccdd
eeefffffffccccdd
eeefffffffccccdd
eeefffffffccccdd
eeefffffffccccdd
eeefffffffccccdd
eeeggggghhhhhhdd
eeeggggghhhhhhdd
eeeggggghhhhhhdd
eeeggggghhhhhhdd
eeeggggghhhhhhdd
eeeggggghhhhhhdd
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
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
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
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
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
R. Gerbicz is offline   Reply With Quote
Old 2016-11-29, 01:51   #8
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

20B116 Posts
Default

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.

Last fiddled with by science_man_88 on 2016-11-29 at 01:54
science_man_88 is offline   Reply With Quote
Old 2016-11-29, 04:52   #9
cuBerBruce
 
cuBerBruce's Avatar
 
Aug 2012
Mass., USA

1001111102 Posts
Default

Quote:
Originally Posted by R. Gerbicz View Post
Really fascinating puzzle!
My exahaustive code gives the following better solutions (these are optimal):
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...

This web page 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.
cuBerBruce is offline   Reply With Quote
Old 2016-11-29, 19:44   #10
EdPeggJr
 
Nov 2016

1016 Posts
Default

Many thanks for the improved solutions. I found a few bugs in my coding. I'll be posting an update at http://demonstrations.wolfram.com/MondrianArtProblem/ in the near future.
EdPeggJr is offline   Reply With Quote
Old 2016-11-30, 21:10   #11
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

3×43×71 Posts
Default

Quote:
Originally Posted by EdPeggJr View Post
Many thanks for the improved solutions. I found a few bugs in my coding. I'll be posting an update at http://demonstrations.wolfram.com/MondrianArtProblem/ in the near future.
Welcome to the forum!
Batalov is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Near repdigit primes on Numberphile lavalamp Lounge 68 2018-09-09 19:01
a numberphile like channel by kids science_man_88 science_man_88 0 2017-11-17 21:37
Trinity Hall Prime (from Numberphile) Mini-Geek Lounge 3 2017-09-08 06:18
prime gap- numberphile vid firejuggler Prime Gap Searches 8 2017-07-19 20:22
Leyland Numbers - Numberphile Mini-Geek Lounge 5 2014-10-29 07:28

All times are UTC. The time now is 12:09.

Fri Nov 27 12:09:46 UTC 2020 up 78 days, 9:20, 4 users, load averages: 1.02, 1.25, 1.23

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.