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

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

Offset: 3

Author

Ed Pegg Jr, Nov 15 2016

Keywords

• nonn
• hard
• more

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(66)-a(96) as follows: 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. - (shortened by Ruud H.G. van Tol, Oct 25 2024)

Examples

			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.
The 14 X 14 square can be divided into non-congruent rectangles of area 30 to 36:
  aaaaaaaaaabbbb
  aaaaaaaaaabbbb
  aaaaaaaaaabbbb
  cccdddddddbbbb
  cccdddddddbbbb
  cccdddddddbbbb
  cccdddddddbbbb
  cccdddddddbbbb
  ccceeeeeffffff
  ccceeeeeffffff
  ccceeeeeffffff
  ccceeeeeffffff
  ccceeeeeffffff
  ccceeeeeffffff
		

Links

• Michel Gaillard, Optimal tilings for n=58..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. See also Integers (2021) Vol. 21, #A37.
• Ed Pegg Jr, Mondrian Art Problem.

Crossrefs

Cf. A050501, A278970, A279596.

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