login
Partition an n X n square into multiple non-congruent integer-sided rectangles. a(n) is the least possible difference between the largest and smallest area.
4

%I #87 Jun 02 2021 22:15:00

%S 2,4,4,5,5,6,6,8,6,7,8,6,8,8,8,8,8,9,9,9,8,9,10,9,10,9,9,11,11,10,12,

%T 12,11,12,11,10,11,12,13,12,12,12,13,13,12,14,12,13,14,13,14,15,14,14,

%U 15,15,14,15,15,14,15,15,15

%N Partition an n X n square into multiple non-congruent integer-sided rectangles. a(n) is the least possible difference between the largest and smallest area.

%C Developed as the Mondrian Art Puzzle.

%C The rectangles can be similar, though. - _Daniel Forgues_, Nov 22 2016

%C That is, there can be a 1x2 rectangle and a 2x4 rectangle (these are similar), but there can't be two 1x2 rectangles (these are congruent). - _Michael B. Porter_, Oct 13 2018

%C Upper bounds for a(n) are n if n is odd, and min(2*n, 4 * a(n/2)) if n is even. - _Roderick MacPhee_, Nov 28 2016

%C An upper bound seems to be ceiling(n/log(n))+3, or A050501+3. See A278970. Holds to at least a(96). - _Ed Pegg Jr_, Dec 02 2016

%C Best known values for a(58)-a(96) as follows: 16, 15, 18, 15, 16, 18, 15, 18, 16, 18, 19, 18, 19, 18, 20, 20, 20, 20, 19, 20, 21, 21, 20, 21, 20, 20, 21, 22, 18, 22, 20, 22, 24, 23, 22, 22, 24, 24, 24

%H Michel Gaillard, <a href="/A276523/a276523_1.txt">Optimal tilings for n=58..65</a>

%H Robert Gerbicz, <a href="/A276523/a276523.txt">Optimal tilings for n=3..57</a>

%H Gordon Hamilton, <a href="http://mathpickle.com/project/mondrian-art-puzzles/">Mondrian Art Puzzles</a> (2015).

%H Gordon Hamilton and Brady Haran, <a href="https://www.youtube.com/watch?v=49KvZrioFB0">Mondrian Puzzle</a>, Numberphile video (2016)

%H Mersenneforum.org puzzles, <a href="http://mersenneforum.org/showthread.php?t=21775">Mondrian art puzzles</a>

%H Cooper O'Kuhn, <a href="https://arxiv.org/abs/1810.04585">The Mondrian Puzzle: A Connection to Number Theory</a>, arXiv:1810.04585 [math.CO], 2018.

%H Cooper O'Kuhn and Todd Fellman, <a href="https://arxiv.org/abs/2006.12547">The Mondrian Puzzle: A Bound Concerning the M(n)=0 Case</a>, arXiv:2006.12547 [math.NT], 2020. See also <a href="http://math.colgate.edu/~integers/v37/v37.mail.html">Integers</a> (2021) Vol. 21, #A37.

%H Ed Pegg Jr, <a href="http://demonstrations.wolfram.com/MondrianArtProblem/">Mondrian Art Problem</a>.

%e A size-11 square can be divided into 3 X 4, 2 X 6, 2 X 7, 3 X 5, 4 X 4, 2 X 8, 2 X 9, and 3 X 6 rectangles. 18 - 12 = 6, the minimal area range.

%e The 14 X 14 square can be divided into non-congruent rectangles of area 30 to 36:

%e aaaaaaaaaabbbb

%e aaaaaaaaaabbbb

%e aaaaaaaaaabbbb

%e cccdddddddbbbb

%e cccdddddddbbbb

%e cccdddddddbbbb

%e cccdddddddbbbb

%e cccdddddddbbbb

%e ccceeeeeffffff

%e ccceeeeeffffff

%e ccceeeeeffffff

%e ccceeeeeffffff

%e ccceeeeeffffff

%e ccceeeeeffffff

%Y Cf. A050501, A278970, A279596.

%K nonn,hard,more

%O 3,1

%A _Ed Pegg Jr_, Nov 15 2016

%E Bruce Norskog corrected a(18), and a recheck by Pegg corrected a(15) and a(19). - _Charles R Greathouse IV_, Nov 28 2016

%E Correction of a(14), a(16), a(23) and new terms a(25)-a(28) from _Robert Gerbicz_, Nov 28 2016

%E a(29)-a(44) from _Robert Gerbicz_, Dec 02 2016

%E a(45)-a(47) from _Robert Gerbicz_ added, as well as best known values to a(96).

%E Correction of a(45), a(46) and new terms a(48)-a(57) from _Robert Gerbicz_, Dec 27 2016

%E a(58)-a(65) from _Michel Gaillard_, Oct 23 2020