1

What is the minimum number of squares that one needs to draw on a white sheet in order to obtain a complete grid with $ n $ squares on a side?

I know that the answer is $ 2n-1 $, the problem is that I don't know how to prove that this is the least number of squares needed. Thanks.

Notes:

-The squares to be drawn can be of any size.

-There will be no drawings outside the table.

user376343
  • 8,311
A. Rober
  • 51

2 Answers2

1

For a proof that $2n-1$ squares suffice, apply the construction below twice at opposite vertices of a square. This is based on the fact that $1+3+\cdots+(2n-1)=n^2$.

I don't know how this can imply minimality, though.

enter image description here

(image from http://www.9math.com/book/sum-first-n-odd-natural-numbers)

lhf
  • 216,483
1

I don't see how to prove that $2n-1$ are required, but here's a proof that $2n-2$ are required. A square can cover at most $2$ of the segments incident on the borders, since otherwise it would have to cover two opposite ones and thus would extend beyond the boundary. There are $4(n-1)$ such segments, so we need at least $2(n-1)$ squares to cover them.

P.S.: achille hui's comment and link under the question show that $2n-2$ actually suffice for $n\ge4$.

joriki
  • 238,052
  • What do you mean by 'segments incident'? – A. Rober Mar 07 '16 at 13:31
  • @A.Rober: Adjoining, meeting the border -- every internal horizontal or vertical line meets the border at two places, and I'm referring to the one-unit internal segments right next to the border. – joriki Mar 07 '16 at 14:05