A369891 Minimum possible uncovered area when at most k squares of side k, k = 1..n, are packed into a square of side n*(n+1)/2 = A000217(n).

0, 0, 4, 4, 16, 13, 8, 8, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0

Offset: 0

Author

Pontus von Brömssen, Feb 04 2024

Keywords

• nonn
• more

Comments

The total area of the small squares is equal to the area of the large square, because 1^3+2^3+...+n^3 = (1+2+...+n)^2 = (n*(n+1)/2)^2 (Nicomachus's theorem).

The small squares are assumed to be oriented in the same way as the large square.

The partridge puzzle for size n is to determine whether a(n) = 0. The generalization considered here was suggested by Rodolfo Kurchan.

Apparently, Robert T. Wainwright showed that a(12) = 0. This was also shown by Ågren et al., and Carl F. Schwenke noted that their solution can be modified to show that also a(14) = 0 and a(16) = 0.

Is a(n) = 0 for all n >= 8?

Links

• Magnus Ågren, Nicolas Beldiceanu, Mats Carlsson, Mohamed Sbihi, Charlotte Truchet, and Stéphane Zampelli, Six ways of integrating symmetries within non-overlapping constraints, in: Willem-Jan van Hoeve and John N. Hooker (eds), Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, CPAIOR 2009, Lecture Notes in Computer Science, vol 5547, Springer 2009; alternative link.
• Pontus von Brömssen, A perfect packing for n = 10, showing that a(10) = 0.
• Erich Friedman, Problem of the Month (August 2002).
• Rodolfo Kurchan, Puzzle Fun (see Partridge Puzzle).
• Robert T. Wainwright, The Partridge Puzzle.
• Wikipedia, Squared triangular number.

Crossrefs

Cf. A000217.

Formula

a(2*k+1) <= a(2*k), because 2*k+1 squares of side 2*k+1 can be added in an L-shape to a square of side k*(2*k+1) to obtain a square of side (2*k+1)*(k+1).