A336659 - OEIS

%I #97 Oct 11 2020 06:55:14

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

%N 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.

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

%C 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

%C 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

%C 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

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

%H Rodolfo Kurchan, <a href="http://www.puzzlefun.online/puzzle-fun-18">Problem 577</a>, Puzzle Fun, December 1997.

%H Rodolfo Kurchan, <a href="http://www.puzzlefun.online/puzzle-fun-20">Solutions to problem 577</a>, Puzzle Fun, December 1998.

%H Rodolfo Kurchan, <a href="http://www.puzzlefun.online/puzzle-fun-32">Solutions n <= 25 to problem 577</a>, Puzzle Fun, September 2020.

%H Rainer Rosenthal, <a href="/A336659/a336659_1.png">Illustrations for n = 8, 9, 10</a>.

%H Rainer Rosenthal, <a href="/A336659/a336659_2.png">Illustration of the maximal solutions for n=11 and n=12</a>.

%e From _Omar E. Pol_, Jul 30 2020: (Start)

%e Consider the first quadrant of the square grid.

%e For n = 1 we draw a 1 X 1 square, so a(1) = 1.

%e 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:

%e     _ _

%e    |_  |

%e    |_|_|

%e .

%e We can see only one 1 X 1 square in the arrangement, so a(2) = 1.

%e 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:

%e     _ _ _

%e    |_ _  |

%e    |   | |

%e    |_ _|_|

%e .

%e Finally we draw a 1 X 1 square on the cell (3,2) as shown below:

%e     _ _ _

%e    |_ _ _|

%e    |   |_| <-- cell (3,2)

%e    |_ _|_|

%e .

%e 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)

%e From _Hugo Pfoertner_, Aug 02 2020: (Start)

%e Based on exhaustive enumeration by Hermann Jurksch, the following arrangements of squares are examples of optimal solutions:

%e a(8) = 22

%e side lower left vertex

%e   1   (7, 7)

%e   2   (6, 3)

%e   3   (5, 1)

%e   4   (4, 2)

%e   5   (1, 3)

%e   6   (0, 0)

%e   7   (0, 0)

%e   8   (0, 0)

%e .

%e a(9) = 28

%e side lower left vertex

%e   1   (0, 6)

%e   2   (1, 7)

%e   3   (1, 3)

%e   4   (0, 5)

%e   5   (0, 4)

%e   6   (3, 1)

%e   7   (2, 2)

%e   8   (0, 0)

%e   9   (0, 0). (End)

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

%K nonn,hard,more

%O 1,3

%A _Rodolfo Kurchan_, Jul 28 2020

%E a(8)-a(9) corrected by _Hugo Pfoertner_, based on data from Hermann Jurksch, Aug 02 2020

%E a(10) corrected by _Hugo Pfoertner_ and Hermann Jurksch, Aug 04 2020

%E a(11) from Hermann Jurksch, communicated privately to _Hugo Pfoertner_, Aug 05 2020

%E a(12)-a(13) from Hermann Jurksch, communicated privately to _Rainer Rosenthal_, Aug 07 2020, Aug 15 2020

%E a(14)-a(15) from _Hugo Pfoertner_, Sep 06 2020