A336659 a(n) is the maximal number of 1 X 1 squares in an arrangement of n squares, from 1 X 1 to n X n, where the squares are inside the n X n square.

1, 1, 2, 4, 8, 10, 15, 22, 28, 34, 41, 52, 60, 70, 83

Offset

1,3

Comments

Note that distinct arrangements could give the same result for some values of n.

Up to rotation and reflection, the solutions for n=8 and n=9 shown in the examples are unique. There are 4 solutions corresponding to a(10)=34, 12 for a(11)=41 and 8 for a(12)=52. See Rosenthal links. - Hugo Pfoertner, Aug 04 2020

Lower bounds for the next terms are a(14)>=70, a(15)>=83, a(16)>=93, a(17)>=107, a(18)>=121, a(19)>=136, a(20)>=153 (from Hermann Jurksch, private communication). - Hugo Pfoertner, Aug 30 2020

More lower bounds a(21)>=168, a(22)>=187, a(23)>=206, a(24)>=222, a(25)>=242 (from Hermann Jurksch, private communication). - Rainer Rosenthal, Oct 07 2020

References

Rodolfo Kurchan, Mesmerizing Math Puzzles, Sterling Publications, (2000), problem 87, Square Stamps, p. 57.

Links

Table of n, a(n) for n=1..15.

Rodolfo Kurchan, Problem 577, Puzzle Fun, December 1997.

Rodolfo Kurchan, Solutions to problem 577, Puzzle Fun, December 1998.

Rodolfo Kurchan, Solutions n <= 25 to problem 577, Puzzle Fun, September 2020.

Rainer Rosenthal, Illustrations for n = 8, 9, 10.

Rainer Rosenthal, Illustration of the maximal solutions for n=11 and n=12.

Example

From Omar E. Pol, Jul 30 2020: (Start)
Consider the first quadrant of the square grid.
For n = 1 we draw a 1 X 1 square, so a(1) = 1.
For n = 2 we draw a 2 X 2 square and then we draw a 1 X 1 square, both with a vertex at the point (0,0) as shown below:
    _ _
   |_  |
   |_|_|
.
We can see only one 1 X 1 square in the arrangement, so a(2) = 1.
For n = 3 first we draw a 3 X 3 square and then we draw a 2 X 2 square, both with a vertex at the point (0,0) as shown below:
    _ _ _
   |_ _  |
   |   | |
   |_ _|_|
.
Finally we draw a 1 X 1 square on the cell (3,2) as shown below:
    _ _ _
   |_ _ _|
   |   |_| <-- cell (3,2)
   |_ _|_|
.
Note that below the cell (3,2), on the cell (3,1), we have formed a new 1 X 1 square, hence the total number of 1 X 1 squares in the arrangement is equal to 2, so a(3) = 2. (End)
From Hugo Pfoertner, Aug 02 2020: (Start)
Based on exhaustive enumeration by Hermann Jurksch, the following arrangements of squares are examples of optimal solutions:
a(8) = 22
side lower left vertex
  1   (7, 7)
  2   (6, 3)
  3   (5, 1)
  4   (4, 2)
  5   (1, 3)
  6   (0, 0)
  7   (0, 0)
  8   (0, 0)
.
a(9) = 28
side lower left vertex
  1   (0, 6)
  2   (1, 7)
  3   (1, 3)
  4   (0, 5)
  5   (0, 4)
  6   (3, 1)
  7   (2, 2)
  8   (0, 0)
  9   (0, 0). (End)

Crossrefs

Cf. A336660 (another version), A336782 (with links to list of solutions and illustrations).

Sequence in context: A331627 A102431 A076919 * A341655 A171757 A350780

Adjacent sequences: A336656 A336657 A336658 * A336660 A336661 A336662

Keyword

nonn,hard,more

Author

Rodolfo Kurchan, Jul 28 2020

Extensions

a(8)-a(9) corrected by Hugo Pfoertner, based on data from Hermann Jurksch, Aug 02 2020

a(10) corrected by Hugo Pfoertner and Hermann Jurksch, Aug 04 2020

a(11) from Hermann Jurksch, communicated privately to Hugo Pfoertner, Aug 05 2020

a(12)-a(13) from Hermann Jurksch, communicated privately to Rainer Rosenthal, Aug 07 2020, Aug 15 2020

a(14)-a(15) from Hugo Pfoertner, Sep 06 2020

Status

approved