Fdtxjr

Is a party consisting of only a bard, a cleric, and a warlock functional long-term?

Why do Australian milk farmers need to protest supermarkets' milk price?

How to deal with a cynical class?

Why do passenger jet manufacturers design their planes with stall prevention systems?

Official degrees of earth’s rotation per day

how to draw discrete time diagram in tikz

Does Wild Magic Surge trigger off of spells on the Sorcerer spell list, if I learned them from another class?

Why is the President allowed to veto a cancellation of emergency powers?

How could a scammer know the apps on my phone / iTunes account?

How to read the value of this capacitor?

Is it normal that my co-workers at a fitness company criticize my food choices?

What do Xenomorphs eat in the Alien series?

If curse and magic is two sides of the same coin, why the former is forbidden?

Hacking a Safe Lock after 3 tries

Dice rolling probability game

Do the common programs (for example: "ls", "cat") in Linux and BSD come from the same source code?

My Graph Theory Students

Gantt Chart like rectangles with log scale

How do anti-virus programs start at Windows boot?

How to change two letters closest to a string and one letter immediately after a string using notepad++

My adviser wants to be the first author

What's the meaning of “spike” in the context of “adrenaline spike”?

Gravity magic - How does it work?

Is it true that good novels will automatically sell themselves on Amazon (and so on) and there is no need for one to waste time promoting?

Minimum number of squares on white sheet

How can we draw $14$ squares to obtain an $8 times 8$ table divided into $64$ unit squares?What is the minimum number of squares needed to produce an $ n times n $ grid?How can I count the number of colored combinations in a set of regions?Number of White squaresThe Weaver Android app $rightarrow$ cute combinatorics problemWhat is the minimum number of squares needed to produce an $ n times n $ grid?A combinatorial interpretation of a counting problenCombinatorics question: Number of ways to sequentially grow linear chains of $n$ balls under a conditionThe Game of Square GuessingProblem 6.1.26 From The Arts and Crafts of Problem SolvingRosenfeld's $7 times 7$ square puzzleNumber of closed loops in a square grid

2

$begingroup$

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?

This question has been asked a number of times on this website, but I can't seem to find one solution which everyone supports.

Links to previously asked questions:

What is the minimum number of squares needed to produce an $ n $ x $ 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.

combinatorics discrete-mathematics

share|cite|improve this question

asked Mar 11 at 20:50

Student_1996Student_1996

533

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  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.
  $endgroup$
  – Mark Fischler
  Mar 11 at 21:13
  

  
  
  
  

add a comment | 

2

$begingroup$

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?

This question has been asked a number of times on this website, but I can't seem to find one solution which everyone supports.

Links to previously asked questions:

What is the minimum number of squares needed to produce an $ n $ x $ 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.

combinatorics discrete-mathematics

share|cite|improve this question

asked Mar 11 at 20:50

Student_1996Student_1996

533

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  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.
  $endgroup$
  – Mark Fischler
  Mar 11 at 21:13
  

  
  
  
  

add a comment | 

$begingroup$

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?

This question has been asked a number of times on this website, but I can't seem to find one solution which everyone supports.

Links to previously asked questions:

What is the minimum number of squares needed to produce an $ n $ x $ 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.

combinatorics discrete-mathematics

share|cite|improve this question

asked Mar 11 at 20:50

Student_1996Student_1996

533

$endgroup$

share|cite|improve this question

asked Mar 11 at 20:50

Student_1996Student_1996

533

share|cite|improve this question

asked Mar 11 at 20:50

Student_1996Student_1996

533

asked Mar 11 at 20:50

Student_1996Student_1996

533

asked Mar 11 at 20:50

Student_1996Student_1996

533

1 Answer
1

active

oldest

votes

2

$begingroup$

For all $nge 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.

share|cite|improve this answer

edited Mar 11 at 22:20

answered Mar 11 at 21:22

Mike EarnestMike Earnest

24.7k22151

$endgroup$

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  For $n=3$, the optimum of $2(3-1)=4$ can be reached by placing a $2x2$ square in every corner.
  $endgroup$
  – Wolfgang Kais
  Mar 11 at 22:53
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @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?
  $endgroup$
  – Student_1996
  Mar 12 at 10:49
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @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.
  $endgroup$
  – Mike Earnest
  Mar 12 at 17:17
  

  
  
  
  

add a comment | 

Your Answer

StackExchange.ifUsing("editor", function ()
return StackExchange.using("mathjaxEditing", function ()
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
);
);
, "mathjax-editing");

StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "69"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);

else
createEditor();

);

function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);



);

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name

Email

Required, but never shown

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3144226%2fminimum-number-of-squares-on-white-sheet%23new-answer', 'question_page');

);

Post as a guest

Name

Email

Required, but never shown

2

$begingroup$

For all $nge 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.

share|cite|improve this answer

edited Mar 11 at 22:20

answered Mar 11 at 21:22

Mike EarnestMike Earnest

24.7k22151

$endgroup$

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  For $n=3$, the optimum of $2(3-1)=4$ can be reached by placing a $2x2$ square in every corner.
  $endgroup$
  – Wolfgang Kais
  Mar 11 at 22:53
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @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?
  $endgroup$
  – Student_1996
  Mar 12 at 10:49
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @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.
  $endgroup$
  – Mike Earnest
  Mar 12 at 17:17
  

  
  
  
  

add a comment | 

2

$begingroup$

For all $nge 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.

share|cite|improve this answer

edited Mar 11 at 22:20

answered Mar 11 at 21:22

Mike EarnestMike Earnest

24.7k22151

$endgroup$

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  For $n=3$, the optimum of $2(3-1)=4$ can be reached by placing a $2x2$ square in every corner.
  $endgroup$
  – Wolfgang Kais
  Mar 11 at 22:53
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @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?
  $endgroup$
  – Student_1996
  Mar 12 at 10:49
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @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.
  $endgroup$
  – Mike Earnest
  Mar 12 at 17:17
  

  
  
  
  

add a comment | 

$begingroup$

For all $nge 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.

share|cite|improve this answer

edited Mar 11 at 22:20

answered Mar 11 at 21:22

Mike EarnestMike Earnest

24.7k22151

$endgroup$

share|cite|improve this answer

edited Mar 11 at 22:20

answered Mar 11 at 21:22

Mike EarnestMike Earnest

24.7k22151

answered Mar 11 at 21:22

Mike EarnestMike Earnest

24.7k22151

answered Mar 11 at 21:22

Mike EarnestMike Earnest

24.7k22151