2

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

Notes:

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

-There will be no drawings outside the table.

Peter Phipps
  • 3,065
Guest47812
  • 63
  • Is the outer edge of the table already drawn? If not I don't think it can be done in less than 15. – Jorik Dec 17 '15 at 15:07
  • The number $14$ makes me think of three sets of four, one in each quadrant or one along each side, plus two centered squares. – Ross Millikan Dec 17 '15 at 15:07
  • @Jorik, The outer edge is not drawn. – Guest47812 Dec 17 '15 at 15:13
  • May I request you to add a part 2 to this question? The part 2 being as follows - How can one analytically model this problem to find the formula for the least number of squares needed to construct a chess board of dimensions n x n? – Deepak Gupta Dec 17 '15 at 15:14
  • This is (or was) part of a live contest: http://www.puzzleup.com/2015/puzzle/?16 Has that contest ended? – lulu Dec 17 '15 at 15:19
  • @DeepakGupta For even $n = 2m$, the least number of squares is $2n-2$. The $2n-2$ squares can be chosen as $[0,k]^2$ and $[k,n]^2$ for $0 < k < n$ excluding $k = m$ plus $[0,m]\times[m,2m]$ and $[m,2m]\times[0,m]$. – achille hui Dec 17 '15 at 15:19
  • @achillehui I found the same just now. You can also make it work for odd $n$. I can prove you can't do it with less either. I'll post an answer. – Jorik Dec 17 '15 at 15:20
  • @achillehui Ah, good. This earlier post (from the same writer) is relevant: http://math.stackexchange.com/questions/1578664/what-is-the-minimum-number-of-squares-to-be-drawn-on-a-paper-in-order-to-obtain – lulu Dec 17 '15 at 15:21
  • @lulu Yeah this question is seems to be a straight up duplicate. Should we mark it as such? I could post my answer on that question. – Jorik Dec 17 '15 at 15:22
  • @lulu The contest ended. – Guest47812 Dec 17 '15 at 15:22
  • @Jorik Well, the other one got put on hold (as the contest was live). If the contest is done, maybe the best thing is to lift the hold? – lulu Dec 17 '15 at 15:23
  • @Guest47812 So I see, thanks. If we can, I'd say it was better to lift the hold on the original post (which has some good work on it). Failing that, maybe it's useful to link to the older question here. – lulu Dec 17 '15 at 15:24
  • Oh I found an oversight in my proof. I'll have to think about it a bit more. – Jorik Dec 17 '15 at 15:31
  • 2
    @Jorik, the lower bound that one need $2n-2$ squares is easy. There are $4n-4$ edges perpendicular to the table boundary and any square we allowed to use cover at most $2$ such edges. – achille hui Dec 17 '15 at 15:47
  • @achillehui Ah of course you are correct. I was looking at the horizontal lines only but missed an edge case there. – Jorik Dec 17 '15 at 16:10
  • @achillehui That was a very elegant way to prove minimality. Thanks a lot. Any non-dagrammatic way of modeling the question? For example, using combinatorics? – Deepak Gupta Dec 17 '15 at 18:33
  • @achillehui I did not understand the last part of your answer - " excluding $k=m$ plus $[0,m]\times[m,2m]$ and $[m,2m]\times[0,m]$" – Deepak Gupta Dec 17 '15 at 18:37
  • 1
    @DeepakGupta Start from the $2n-2$ squares $[0,k]^2, [k,n]^2$ for $0 < k < n$, it cover all but two of the squares. The two unit squares at the corners: $[n-1,n]\times [0,1]$ and $[0,1]\times [n-1,n]$. Instead of wasting one more square, one can replace the two squares of side $4$ (i.e. replace $[0,m]^2$ and $[m,n]^2$ by $[0,m]\times [m,n]$ and $[m,n]\times [0,m]$ ) to finish the job. – achille hui Dec 18 '15 at 02:34
  • That "gotcha!" feeling :) Thanks. Though I still find it hard to interpret your notation that you use for representing the two corner unit squares (top left) and (bottom right). @Jorik's diagrams helped. – Deepak Gupta Dec 18 '15 at 11:07

1 Answers1

8

The comments on the question pretty much contain all the information you need about this question. I figured I'd add some pretty pictures. In general if $n\geq 4$ then you can draw $2(n-1)$ squares to end up with an $n\times n$ grid of squares and you can't do it with less.

For even $n$ the solution looks like this:enter image description here

For odd $n$ the solution looks like this:enter image description here

Jorik
  • 1,411