

A276523


Partition an n X n square into multiple noncongruent integersided rectangles. a(n) is the least possible difference between the largest and smallest area.


4



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, 12, 11, 12, 11, 10, 11, 12, 13, 12, 12, 12, 13, 13, 12, 14, 12, 13, 14, 13, 14, 15, 14, 14, 15, 15, 14, 15, 15, 14, 15, 15, 15
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

3,1


COMMENTS

Developed as the Mondrian Art Puzzle.
The rectangles can be similar, though.  Daniel Forgues, Nov 22 2016
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
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
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
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


LINKS

Table of n, a(n) for n=3..65.
Robert Gerbicz, Optimal tilings for n=3..57
Gordon Hamilton, Mondrian Art Puzzles (2015).
Gordon Hamilton and Brady Haran, Mondrian Puzzle, Numberphile video (2016)
Mersenneforum.org puzzles, Mondrian art puzzles
Cooper O'Kuhn, The Mondrian Puzzle: A Connection to Number Theory, arXiv:1810.04585 [math.CO], 2018.
Cooper O'Kuhn and Todd Fellman, The Mondrian Puzzle: A Bound Concerning the M(n)=0 Case, arXiv:2006.12547 [math.NT], 2020.
Ed Pegg Jr, Mondrian Art Problem.
Michel Gaillard, Optimal tilings for n=58..65


EXAMPLE

A size11 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.
The 14 X 14 square can be divided into noncongruent rectangles of area 30 to 36 with
aaaaaaaaaabbbb
aaaaaaaaaabbbb
aaaaaaaaaabbbb
cccdddddddbbbb
cccdddddddbbbb
cccdddddddbbbb
cccdddddddbbbb
cccdddddddbbbb
ccceeeeeffffff
ccceeeeeffffff
ccceeeeeffffff
ccceeeeeffffff
ccceeeeeffffff
ccceeeeeffffff


CROSSREFS

Cf. A050501, A278970, A279596.
Sequence in context: A036437 A053306 A108422 * A244320 A084616 A196259
Adjacent sequences: A276520 A276521 A276522 * A276524 A276525 A276526


KEYWORD

nonn,hard,more


AUTHOR

Ed Pegg Jr, Nov 15 2016


EXTENSIONS

Bruce Norskog corrected a(18), and a recheck by Pegg corrected a(15) and a(19).  Charles R Greathouse IV, Nov 28 2016
Correction of a(14), a(16), a(23) and new terms a(25)a(28) from Robert Gerbicz, Nov 28 2016
a(29)a(44) from Robert Gerbicz, Dec 02 2016
a(45)a(47) from Robert Gerbicz added, as well as best known values to a(96).
Correction of a(45), a(46) and new terms a(48)a(57) from Robert Gerbicz, Dec 27 2016
a(58)a(65) from Michel Gaillard, Oct 23 2020


STATUS

approved



