login
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.
4
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
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.
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
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