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