1

Links to similar questions:

What is the minimum number of squares needed to produce an $ n \times n $ grid?

How can we draw $14$ squares to obtain an $8 \times 8$ table divided into $64$ unit squares?

The second link is a similar question, but at the bottom, someone has provided a graphical representation of the problem. If anyone could provide a conclusive solution to this question, it'd be much appreciated.

  • Is it permissible, along with the $n$-squares-on-a-side grid, to have other "left over" lines? The answer will be different if you require a "clean" grid with no extraneous lines. – Mark Fischler Mar 11 '19 at 21:13

1 Answers1

2

For all $n\ge 4$, the optimal number of squares is $2(n-1)$.

A construction, taken from Jorik's answer, is as follows.

If $n$ is even,

  • $n-2$ squares have lower left corner $(0,0)$, whose widths comprise all integers between $1$ and $n-1$ except for $n/2$.

  • $n-2$ squares have upper right corner $(n,n)$, with these same widths.

  • Two squares have width $n/2$. One has its lower right corner at $(n,0)$, the other has its upper left corner at $(0,n)$.

If $n$ is odd,

  • $n-3$ squares have lower left corner $(0,0)$, whose widths comprise all integers between $1$ and $n-1$ except for $(n-1)/2$ and $(n+1)/2$.

  • $n-3$ squares have upper right corner $(n,n)$, with these same widths.

  • Two squares have width $(n-1)/2$. One has its lower right corner at $(n,0)$, the other has its upper left corner at $(0,n)$.

  • Two squares have width $(n+1)/2$. One has its lower right corner at $(n,0)$, the other has its upper left corner at $(0,n)$.

Here is a proof that this is optimal, taken from joriki's answer.

Consider the $4(n-1)$ unit line segments in the grid which have one endpoint on the outside of the grid and the other endpoint inside the grid. Each square can cover at most two of these line segments. Therefore, in order to cover all of them, you need at least $4(n-1)/2=2(n-1)$ squares.

Community
  • 1
Mike Earnest
  • 75,930
  • 1
    For $n=3$, the optimum of $2(3-1)=4$ can be reached by placing a $2x2$ square in every corner. – Wolfgang Kais Mar 11 '19 at 22:53
  • @Mike Earnest Thanks for responding. I completely understand your answer apart from the last part where you attempt to prove 2(n-1) is optimal from Joriki's answer. I don't understand what you mean by the unit line segments which have one endpoint outside the grid and another endpoint inside? –  Mar 12 '19 at 10:49
  • @Student_1996 For example, the line segment connecting $(k,0)$ to $(k,1)$, for $k=1,2,\dots,n-1$. Those are on the bottom border. Or the line segments connecting $(n-1,k)$ to $(n,k)$ for $k=1,\dots,n-1$ on the right border. – Mike Earnest Mar 12 '19 at 17:17