Punch 2000 holes in 2000 polygons with 1000 needles












26












$begingroup$


You have two identical perfectly square pieces of paper. The area of each paper is 1000 units.



On each paper, draw 1000 convex, non-overlapping polygons with all polygons having the same area (exactly 1 unit). Obviously, the polygons are covering both papers completely and edges of paper also serve as edges of some polygons). Polygons may have different shapes and number of sides and the drawing on the first paper is completely different from the drawing on the second paper.



Now put the first paper on top of the second and align paper edges perfectly. Prove that it is always possible to punch a hole in all 2000 polygons with 1000 needles (each needle goes through both papers).



What have I tried?



This problem came from my son who likes to torture his father with difficult problems brought back from his math school. My first try was to steal his clever analysis book while he was sleeping and find the right page in the answer section. Alas, this problem had no solution, which basically means that it's either too simple (and I'm too stupid) or it's too difficult.



So I decided to read some theory and discovered that I had some pretty huge gaps in my math education. This problem is definitely about functions. You have a set of 1000 polygons on one side and a set of 1000 polygons on the other side. I have to prove that there is a bijective function between these two sets. Needles are just lines connecting the dots. However, all my attempts to construct such function ended miserably. I guess there has to be some clever theorem than can be applied to problems like this one but I would have to read a pretty thick book to find it.



Thanks for the hint.






functions







share|cite|improve this question











$endgroup$












  • $begingroup$
    How do the needles go through the papers, exactly? Does each needle pass through each paper at exactly one point, and, for any given needle, does it have to pass through the same point on each paper?
    $endgroup$
    – Tanner Swett
    Nov 13 '18 at 2:22










  • $begingroup$
    @TannerSwett Yes, you are right. Imagine a needle as a line perpendicular to two squares lying in two parallel planes.
    $endgroup$
    – Oldboy
    Nov 13 '18 at 6:01






  • 2




    $begingroup$
    On puzzling.SE a potential answer could be: You only need one needle that you reuse for 2000 wholes :).
    $endgroup$
    – Surb
    Nov 13 '18 at 15:41






  • 1




    $begingroup$
    @Surb I should have used 10.000 needles instead of 1.000. I would have got more upvotes :)
    $endgroup$
    – Oldboy
    Nov 13 '18 at 17:17










  • $begingroup$
    I'm confused; why does identity function does not work in this case ?
    $endgroup$
    – onurcanbektas
    Nov 14 '18 at 6:15
















26












$begingroup$


You have two identical perfectly square pieces of paper. The area of each paper is 1000 units.



On each paper, draw 1000 convex, non-overlapping polygons with all polygons having the same area (exactly 1 unit). Obviously, the polygons are covering both papers completely and edges of paper also serve as edges of some polygons). Polygons may have different shapes and number of sides and the drawing on the first paper is completely different from the drawing on the second paper.



Now put the first paper on top of the second and align paper edges perfectly. Prove that it is always possible to punch a hole in all 2000 polygons with 1000 needles (each needle goes through both papers).



What have I tried?



This problem came from my son who likes to torture his father with difficult problems brought back from his math school. My first try was to steal his clever analysis book while he was sleeping and find the right page in the answer section. Alas, this problem had no solution, which basically means that it's either too simple (and I'm too stupid) or it's too difficult.



So I decided to read some theory and discovered that I had some pretty huge gaps in my math education. This problem is definitely about functions. You have a set of 1000 polygons on one side and a set of 1000 polygons on the other side. I have to prove that there is a bijective function between these two sets. Needles are just lines connecting the dots. However, all my attempts to construct such function ended miserably. I guess there has to be some clever theorem than can be applied to problems like this one but I would have to read a pretty thick book to find it.



Thanks for the hint.






functions







share|cite|improve this question











$endgroup$












  • $begingroup$
    How do the needles go through the papers, exactly? Does each needle pass through each paper at exactly one point, and, for any given needle, does it have to pass through the same point on each paper?
    $endgroup$
    – Tanner Swett
    Nov 13 '18 at 2:22










  • $begingroup$
    @TannerSwett Yes, you are right. Imagine a needle as a line perpendicular to two squares lying in two parallel planes.
    $endgroup$
    – Oldboy
    Nov 13 '18 at 6:01






  • 2




    $begingroup$
    On puzzling.SE a potential answer could be: You only need one needle that you reuse for 2000 wholes :).
    $endgroup$
    – Surb
    Nov 13 '18 at 15:41






  • 1




    $begingroup$
    @Surb I should have used 10.000 needles instead of 1.000. I would have got more upvotes :)
    $endgroup$
    – Oldboy
    Nov 13 '18 at 17:17










  • $begingroup$
    I'm confused; why does identity function does not work in this case ?
    $endgroup$
    – onurcanbektas
    Nov 14 '18 at 6:15














26












26








26


13



$begingroup$


You have two identical perfectly square pieces of paper. The area of each paper is 1000 units.



On each paper, draw 1000 convex, non-overlapping polygons with all polygons having the same area (exactly 1 unit). Obviously, the polygons are covering both papers completely and edges of paper also serve as edges of some polygons). Polygons may have different shapes and number of sides and the drawing on the first paper is completely different from the drawing on the second paper.



Now put the first paper on top of the second and align paper edges perfectly. Prove that it is always possible to punch a hole in all 2000 polygons with 1000 needles (each needle goes through both papers).



What have I tried?



This problem came from my son who likes to torture his father with difficult problems brought back from his math school. My first try was to steal his clever analysis book while he was sleeping and find the right page in the answer section. Alas, this problem had no solution, which basically means that it's either too simple (and I'm too stupid) or it's too difficult.



So I decided to read some theory and discovered that I had some pretty huge gaps in my math education. This problem is definitely about functions. You have a set of 1000 polygons on one side and a set of 1000 polygons on the other side. I have to prove that there is a bijective function between these two sets. Needles are just lines connecting the dots. However, all my attempts to construct such function ended miserably. I guess there has to be some clever theorem than can be applied to problems like this one but I would have to read a pretty thick book to find it.



Thanks for the hint.






functions







share|cite|improve this question











$endgroup$




You have two identical perfectly square pieces of paper. The area of each paper is 1000 units.



On each paper, draw 1000 convex, non-overlapping polygons with all polygons having the same area (exactly 1 unit). Obviously, the polygons are covering both papers completely and edges of paper also serve as edges of some polygons). Polygons may have different shapes and number of sides and the drawing on the first paper is completely different from the drawing on the second paper.



Now put the first paper on top of the second and align paper edges perfectly. Prove that it is always possible to punch a hole in all 2000 polygons with 1000 needles (each needle goes through both papers).



What have I tried?



This problem came from my son who likes to torture his father with difficult problems brought back from his math school. My first try was to steal his clever analysis book while he was sleeping and find the right page in the answer section. Alas, this problem had no solution, which basically means that it's either too simple (and I'm too stupid) or it's too difficult.



So I decided to read some theory and discovered that I had some pretty huge gaps in my math education. This problem is definitely about functions. You have a set of 1000 polygons on one side and a set of 1000 polygons on the other side. I have to prove that there is a bijective function between these two sets. Needles are just lines connecting the dots. However, all my attempts to construct such function ended miserably. I guess there has to be some clever theorem than can be applied to problems like this one but I would have to read a pretty thick book to find it.



Thanks for the hint.






functions




functions






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited Nov 12 '18 at 22:25









amWhy

192k28225439




192k28225439










asked Nov 12 '18 at 22:20









OldboyOldboy

7,1241833




7,1241833












  • $begingroup$
    How do the needles go through the papers, exactly? Does each needle pass through each paper at exactly one point, and, for any given needle, does it have to pass through the same point on each paper?
    $endgroup$
    – Tanner Swett
    Nov 13 '18 at 2:22










  • $begingroup$
    @TannerSwett Yes, you are right. Imagine a needle as a line perpendicular to two squares lying in two parallel planes.
    $endgroup$
    – Oldboy
    Nov 13 '18 at 6:01






  • 2




    $begingroup$
    On puzzling.SE a potential answer could be: You only need one needle that you reuse for 2000 wholes :).
    $endgroup$
    – Surb
    Nov 13 '18 at 15:41






  • 1




    $begingroup$
    @Surb I should have used 10.000 needles instead of 1.000. I would have got more upvotes :)
    $endgroup$
    – Oldboy
    Nov 13 '18 at 17:17










  • $begingroup$
    I'm confused; why does identity function does not work in this case ?
    $endgroup$
    – onurcanbektas
    Nov 14 '18 at 6:15


















  • $begingroup$
    How do the needles go through the papers, exactly? Does each needle pass through each paper at exactly one point, and, for any given needle, does it have to pass through the same point on each paper?
    $endgroup$
    – Tanner Swett
    Nov 13 '18 at 2:22










  • $begingroup$
    @TannerSwett Yes, you are right. Imagine a needle as a line perpendicular to two squares lying in two parallel planes.
    $endgroup$
    – Oldboy
    Nov 13 '18 at 6:01






  • 2




    $begingroup$
    On puzzling.SE a potential answer could be: You only need one needle that you reuse for 2000 wholes :).
    $endgroup$
    – Surb
    Nov 13 '18 at 15:41






  • 1




    $begingroup$
    @Surb I should have used 10.000 needles instead of 1.000. I would have got more upvotes :)
    $endgroup$
    – Oldboy
    Nov 13 '18 at 17:17










  • $begingroup$
    I'm confused; why does identity function does not work in this case ?
    $endgroup$
    – onurcanbektas
    Nov 14 '18 at 6:15
















$begingroup$
How do the needles go through the papers, exactly? Does each needle pass through each paper at exactly one point, and, for any given needle, does it have to pass through the same point on each paper?
$endgroup$
– Tanner Swett
Nov 13 '18 at 2:22




$begingroup$
How do the needles go through the papers, exactly? Does each needle pass through each paper at exactly one point, and, for any given needle, does it have to pass through the same point on each paper?
$endgroup$
– Tanner Swett
Nov 13 '18 at 2:22












$begingroup$
@TannerSwett Yes, you are right. Imagine a needle as a line perpendicular to two squares lying in two parallel planes.
$endgroup$
– Oldboy
Nov 13 '18 at 6:01




$begingroup$
@TannerSwett Yes, you are right. Imagine a needle as a line perpendicular to two squares lying in two parallel planes.
$endgroup$
– Oldboy
Nov 13 '18 at 6:01




2




2




$begingroup$
On puzzling.SE a potential answer could be: You only need one needle that you reuse for 2000 wholes :).
$endgroup$
– Surb
Nov 13 '18 at 15:41




$begingroup$
On puzzling.SE a potential answer could be: You only need one needle that you reuse for 2000 wholes :).
$endgroup$
– Surb
Nov 13 '18 at 15:41




1




1




$begingroup$
@Surb I should have used 10.000 needles instead of 1.000. I would have got more upvotes :)
$endgroup$
– Oldboy
Nov 13 '18 at 17:17




$begingroup$
@Surb I should have used 10.000 needles instead of 1.000. I would have got more upvotes :)
$endgroup$
– Oldboy
Nov 13 '18 at 17:17












$begingroup$
I'm confused; why does identity function does not work in this case ?
$endgroup$
– onurcanbektas
Nov 14 '18 at 6:15




$begingroup$
I'm confused; why does identity function does not work in this case ?
$endgroup$
– onurcanbektas
Nov 14 '18 at 6:15










2 Answers
2






active

oldest

votes


















36












$begingroup$

The clever theorem that can be applied to questions like this one is Hall's theorem.



Construct a bipartite graph, with the vertices on one side being the polygons on the first sheet of paper, and the vertices on the other side being the polygons on the second sheet of paper. Draw an edge between two polygons whenever they overlap.



A perfect matching in this graph is a one-to-one pairing of the polygons on the two sheets such that any two polygons that are paired overlap somewhere. If we find a perfect matching, we can punch the holes: for every pair of polygons in the perfect matching, poke a needle through some part of their overlapping region.



Hall's theorem says that a perfect matching is guaranteed to exist if, for every set $S$ of vertices on one side, the set $N(S)$ of vertices adjacent to some vertex in $S$ satisfies $|N(S)| ge |S|$. In other words, if you pick any $k$ polygons on one sheet of paper, there will be at least $k$ polygons on the other sheet of paper adjcent to at least one of the ones you picked.



This follows from looking at the areas. An individual polygon has area $1$. So the $k$ polygons you chose on one sheet have total area $k$. On the other sheet, that same region needs at least $k$ polygons to cover.






share|cite|improve this answer









$endgroup$













  • $begingroup$
    Do you use the convexity of the polygons somewhere? Or can this assumption be dropped?
    $endgroup$
    – Janik
    Nov 13 '18 at 11:46










  • $begingroup$
    @Janik: Convexity is not required.
    $endgroup$
    – Henning Makholm
    Nov 13 '18 at 11:47










  • $begingroup$
    @HenningMakholm "On each paper, draw 1000 convex, non-overlapping polygons (...)"
    $endgroup$
    – Janik
    Nov 13 '18 at 11:49






  • 3




    $begingroup$
    @Janik: Yes, the polygons in the question happen to be convex, but this is not necessary for the result to hold.
    $endgroup$
    – Henning Makholm
    Nov 13 '18 at 11:52












  • $begingroup$
    @HenningMakholm Ah, I misunderstood what you were saying, sorry. Thanks for your clarification.
    $endgroup$
    – Janik
    Nov 13 '18 at 11:55



















1












$begingroup$

It is "self evident" that we cannot use fewer than 1000 needles, just to punch a hole in every polygon in a single sheet.



By the pigeon hole principle, if we use more than 1000 needles, then some polygons must have more than one hole in them.



Suppose that punching 1000 holes in 1000 polygons in the upper sheet does not achieve perfect coverage in the lower sheet: not all 1000 polygons receive a hole. That requires that one or more polygons to receive two holes. (Our friend, pigeon hole, again).



Is that possible? Yes it is. For that to happen, all we need is the situation that two needles (necessarily) going through different polygons in the top sheet pierce the same polygon in the bottom sheet.



However, is this unavoidable? No, it isn't. Two needles going through different top polygons are never forced to map to the same bottom polygon. For such a situation to be unavoidable, it would have to be that some lower layer polygon entirely covers two (or more) upper layer polygons. This is ruled out by the key constraint that all polygons have the same area. Therefore the situation is avoidable; no pair of needles have to share the same lower-layer polygon.






share|cite|improve this answer









$endgroup$













  • $begingroup$
    The statement "For such a situation to be unavoidable, it would have to be that some lower layer polygon entirely covers two (or more) upper layer polygons." is not quite true. For example, if polygons A, B, C were entirely covered by polygons P and Q, we'd also get a similar problem. The area constraint rules this out as well, but we do have to check a more general condition. (And then you need a result like Hall's theorem to convince you that this is the only kind of problem.)
    $endgroup$
    – Misha Lavrov
    Nov 14 '18 at 14:55










  • $begingroup$
    @MishaLavrov The straightforward generalization here is that N + k, k > 0 polygons in the upper layer cannot share N polygons in the lower layer. ABCD{E...} cannot be covered by PQR and so on. All those situations are ruled out by the area constraint. N polygons each of unit area cannot cover N + k polygons of unit area.
    $endgroup$
    – Kaz
    Nov 15 '18 at 7:24










  • $begingroup$
    Yes, exactly. Moreover, without Hall's theorem, you do not know that this is the only obstacle.
    $endgroup$
    – Misha Lavrov
    Nov 15 '18 at 15:07











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


















StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2995979%2fpunch-2000-holes-in-2000-polygons-with-1000-needles%23new-answer', 'question_page');
}
);

Post as a guest















Required, but never shown

























2 Answers
2






active

oldest

votes








2 Answers
2






active

oldest

votes









active

oldest

votes






active

oldest

votes









36












$begingroup$

The clever theorem that can be applied to questions like this one is Hall's theorem.



Construct a bipartite graph, with the vertices on one side being the polygons on the first sheet of paper, and the vertices on the other side being the polygons on the second sheet of paper. Draw an edge between two polygons whenever they overlap.



A perfect matching in this graph is a one-to-one pairing of the polygons on the two sheets such that any two polygons that are paired overlap somewhere. If we find a perfect matching, we can punch the holes: for every pair of polygons in the perfect matching, poke a needle through some part of their overlapping region.



Hall's theorem says that a perfect matching is guaranteed to exist if, for every set $S$ of vertices on one side, the set $N(S)$ of vertices adjacent to some vertex in $S$ satisfies $|N(S)| ge |S|$. In other words, if you pick any $k$ polygons on one sheet of paper, there will be at least $k$ polygons on the other sheet of paper adjcent to at least one of the ones you picked.



This follows from looking at the areas. An individual polygon has area $1$. So the $k$ polygons you chose on one sheet have total area $k$. On the other sheet, that same region needs at least $k$ polygons to cover.






share|cite|improve this answer









$endgroup$













  • $begingroup$
    Do you use the convexity of the polygons somewhere? Or can this assumption be dropped?
    $endgroup$
    – Janik
    Nov 13 '18 at 11:46










  • $begingroup$
    @Janik: Convexity is not required.
    $endgroup$
    – Henning Makholm
    Nov 13 '18 at 11:47










  • $begingroup$
    @HenningMakholm "On each paper, draw 1000 convex, non-overlapping polygons (...)"
    $endgroup$
    – Janik
    Nov 13 '18 at 11:49






  • 3




    $begingroup$
    @Janik: Yes, the polygons in the question happen to be convex, but this is not necessary for the result to hold.
    $endgroup$
    – Henning Makholm
    Nov 13 '18 at 11:52












  • $begingroup$
    @HenningMakholm Ah, I misunderstood what you were saying, sorry. Thanks for your clarification.
    $endgroup$
    – Janik
    Nov 13 '18 at 11:55
















36












$begingroup$

The clever theorem that can be applied to questions like this one is Hall's theorem.



Construct a bipartite graph, with the vertices on one side being the polygons on the first sheet of paper, and the vertices on the other side being the polygons on the second sheet of paper. Draw an edge between two polygons whenever they overlap.



A perfect matching in this graph is a one-to-one pairing of the polygons on the two sheets such that any two polygons that are paired overlap somewhere. If we find a perfect matching, we can punch the holes: for every pair of polygons in the perfect matching, poke a needle through some part of their overlapping region.



Hall's theorem says that a perfect matching is guaranteed to exist if, for every set $S$ of vertices on one side, the set $N(S)$ of vertices adjacent to some vertex in $S$ satisfies $|N(S)| ge |S|$. In other words, if you pick any $k$ polygons on one sheet of paper, there will be at least $k$ polygons on the other sheet of paper adjcent to at least one of the ones you picked.



This follows from looking at the areas. An individual polygon has area $1$. So the $k$ polygons you chose on one sheet have total area $k$. On the other sheet, that same region needs at least $k$ polygons to cover.






share|cite|improve this answer









$endgroup$













  • $begingroup$
    Do you use the convexity of the polygons somewhere? Or can this assumption be dropped?
    $endgroup$
    – Janik
    Nov 13 '18 at 11:46










  • $begingroup$
    @Janik: Convexity is not required.
    $endgroup$
    – Henning Makholm
    Nov 13 '18 at 11:47










  • $begingroup$
    @HenningMakholm "On each paper, draw 1000 convex, non-overlapping polygons (...)"
    $endgroup$
    – Janik
    Nov 13 '18 at 11:49






  • 3




    $begingroup$
    @Janik: Yes, the polygons in the question happen to be convex, but this is not necessary for the result to hold.
    $endgroup$
    – Henning Makholm
    Nov 13 '18 at 11:52












  • $begingroup$
    @HenningMakholm Ah, I misunderstood what you were saying, sorry. Thanks for your clarification.
    $endgroup$
    – Janik
    Nov 13 '18 at 11:55














36












36








36





$begingroup$

The clever theorem that can be applied to questions like this one is Hall's theorem.



Construct a bipartite graph, with the vertices on one side being the polygons on the first sheet of paper, and the vertices on the other side being the polygons on the second sheet of paper. Draw an edge between two polygons whenever they overlap.



A perfect matching in this graph is a one-to-one pairing of the polygons on the two sheets such that any two polygons that are paired overlap somewhere. If we find a perfect matching, we can punch the holes: for every pair of polygons in the perfect matching, poke a needle through some part of their overlapping region.



Hall's theorem says that a perfect matching is guaranteed to exist if, for every set $S$ of vertices on one side, the set $N(S)$ of vertices adjacent to some vertex in $S$ satisfies $|N(S)| ge |S|$. In other words, if you pick any $k$ polygons on one sheet of paper, there will be at least $k$ polygons on the other sheet of paper adjcent to at least one of the ones you picked.



This follows from looking at the areas. An individual polygon has area $1$. So the $k$ polygons you chose on one sheet have total area $k$. On the other sheet, that same region needs at least $k$ polygons to cover.






share|cite|improve this answer









$endgroup$



The clever theorem that can be applied to questions like this one is Hall's theorem.



Construct a bipartite graph, with the vertices on one side being the polygons on the first sheet of paper, and the vertices on the other side being the polygons on the second sheet of paper. Draw an edge between two polygons whenever they overlap.



A perfect matching in this graph is a one-to-one pairing of the polygons on the two sheets such that any two polygons that are paired overlap somewhere. If we find a perfect matching, we can punch the holes: for every pair of polygons in the perfect matching, poke a needle through some part of their overlapping region.



Hall's theorem says that a perfect matching is guaranteed to exist if, for every set $S$ of vertices on one side, the set $N(S)$ of vertices adjacent to some vertex in $S$ satisfies $|N(S)| ge |S|$. In other words, if you pick any $k$ polygons on one sheet of paper, there will be at least $k$ polygons on the other sheet of paper adjcent to at least one of the ones you picked.



This follows from looking at the areas. An individual polygon has area $1$. So the $k$ polygons you chose on one sheet have total area $k$. On the other sheet, that same region needs at least $k$ polygons to cover.







share|cite|improve this answer












share|cite|improve this answer



share|cite|improve this answer










answered Nov 12 '18 at 22:33









Misha LavrovMisha Lavrov

44.3k555106




44.3k555106












  • $begingroup$
    Do you use the convexity of the polygons somewhere? Or can this assumption be dropped?
    $endgroup$
    – Janik
    Nov 13 '18 at 11:46










  • $begingroup$
    @Janik: Convexity is not required.
    $endgroup$
    – Henning Makholm
    Nov 13 '18 at 11:47










  • $begingroup$
    @HenningMakholm "On each paper, draw 1000 convex, non-overlapping polygons (...)"
    $endgroup$
    – Janik
    Nov 13 '18 at 11:49






  • 3




    $begingroup$
    @Janik: Yes, the polygons in the question happen to be convex, but this is not necessary for the result to hold.
    $endgroup$
    – Henning Makholm
    Nov 13 '18 at 11:52












  • $begingroup$
    @HenningMakholm Ah, I misunderstood what you were saying, sorry. Thanks for your clarification.
    $endgroup$
    – Janik
    Nov 13 '18 at 11:55


















  • $begingroup$
    Do you use the convexity of the polygons somewhere? Or can this assumption be dropped?
    $endgroup$
    – Janik
    Nov 13 '18 at 11:46










  • $begingroup$
    @Janik: Convexity is not required.
    $endgroup$
    – Henning Makholm
    Nov 13 '18 at 11:47










  • $begingroup$
    @HenningMakholm "On each paper, draw 1000 convex, non-overlapping polygons (...)"
    $endgroup$
    – Janik
    Nov 13 '18 at 11:49






  • 3




    $begingroup$
    @Janik: Yes, the polygons in the question happen to be convex, but this is not necessary for the result to hold.
    $endgroup$
    – Henning Makholm
    Nov 13 '18 at 11:52












  • $begingroup$
    @HenningMakholm Ah, I misunderstood what you were saying, sorry. Thanks for your clarification.
    $endgroup$
    – Janik
    Nov 13 '18 at 11:55
















$begingroup$
Do you use the convexity of the polygons somewhere? Or can this assumption be dropped?
$endgroup$
– Janik
Nov 13 '18 at 11:46




$begingroup$
Do you use the convexity of the polygons somewhere? Or can this assumption be dropped?
$endgroup$
– Janik
Nov 13 '18 at 11:46












$begingroup$
@Janik: Convexity is not required.
$endgroup$
– Henning Makholm
Nov 13 '18 at 11:47




$begingroup$
@Janik: Convexity is not required.
$endgroup$
– Henning Makholm
Nov 13 '18 at 11:47












$begingroup$
@HenningMakholm "On each paper, draw 1000 convex, non-overlapping polygons (...)"
$endgroup$
– Janik
Nov 13 '18 at 11:49




$begingroup$
@HenningMakholm "On each paper, draw 1000 convex, non-overlapping polygons (...)"
$endgroup$
– Janik
Nov 13 '18 at 11:49




3




3




$begingroup$
@Janik: Yes, the polygons in the question happen to be convex, but this is not necessary for the result to hold.
$endgroup$
– Henning Makholm
Nov 13 '18 at 11:52






$begingroup$
@Janik: Yes, the polygons in the question happen to be convex, but this is not necessary for the result to hold.
$endgroup$
– Henning Makholm
Nov 13 '18 at 11:52














$begingroup$
@HenningMakholm Ah, I misunderstood what you were saying, sorry. Thanks for your clarification.
$endgroup$
– Janik
Nov 13 '18 at 11:55




$begingroup$
@HenningMakholm Ah, I misunderstood what you were saying, sorry. Thanks for your clarification.
$endgroup$
– Janik
Nov 13 '18 at 11:55











1












$begingroup$

It is "self evident" that we cannot use fewer than 1000 needles, just to punch a hole in every polygon in a single sheet.



By the pigeon hole principle, if we use more than 1000 needles, then some polygons must have more than one hole in them.



Suppose that punching 1000 holes in 1000 polygons in the upper sheet does not achieve perfect coverage in the lower sheet: not all 1000 polygons receive a hole. That requires that one or more polygons to receive two holes. (Our friend, pigeon hole, again).



Is that possible? Yes it is. For that to happen, all we need is the situation that two needles (necessarily) going through different polygons in the top sheet pierce the same polygon in the bottom sheet.



However, is this unavoidable? No, it isn't. Two needles going through different top polygons are never forced to map to the same bottom polygon. For such a situation to be unavoidable, it would have to be that some lower layer polygon entirely covers two (or more) upper layer polygons. This is ruled out by the key constraint that all polygons have the same area. Therefore the situation is avoidable; no pair of needles have to share the same lower-layer polygon.






share|cite|improve this answer









$endgroup$













  • $begingroup$
    The statement "For such a situation to be unavoidable, it would have to be that some lower layer polygon entirely covers two (or more) upper layer polygons." is not quite true. For example, if polygons A, B, C were entirely covered by polygons P and Q, we'd also get a similar problem. The area constraint rules this out as well, but we do have to check a more general condition. (And then you need a result like Hall's theorem to convince you that this is the only kind of problem.)
    $endgroup$
    – Misha Lavrov
    Nov 14 '18 at 14:55










  • $begingroup$
    @MishaLavrov The straightforward generalization here is that N + k, k > 0 polygons in the upper layer cannot share N polygons in the lower layer. ABCD{E...} cannot be covered by PQR and so on. All those situations are ruled out by the area constraint. N polygons each of unit area cannot cover N + k polygons of unit area.
    $endgroup$
    – Kaz
    Nov 15 '18 at 7:24










  • $begingroup$
    Yes, exactly. Moreover, without Hall's theorem, you do not know that this is the only obstacle.
    $endgroup$
    – Misha Lavrov
    Nov 15 '18 at 15:07
















1












$begingroup$

It is "self evident" that we cannot use fewer than 1000 needles, just to punch a hole in every polygon in a single sheet.



By the pigeon hole principle, if we use more than 1000 needles, then some polygons must have more than one hole in them.



Suppose that punching 1000 holes in 1000 polygons in the upper sheet does not achieve perfect coverage in the lower sheet: not all 1000 polygons receive a hole. That requires that one or more polygons to receive two holes. (Our friend, pigeon hole, again).



Is that possible? Yes it is. For that to happen, all we need is the situation that two needles (necessarily) going through different polygons in the top sheet pierce the same polygon in the bottom sheet.



However, is this unavoidable? No, it isn't. Two needles going through different top polygons are never forced to map to the same bottom polygon. For such a situation to be unavoidable, it would have to be that some lower layer polygon entirely covers two (or more) upper layer polygons. This is ruled out by the key constraint that all polygons have the same area. Therefore the situation is avoidable; no pair of needles have to share the same lower-layer polygon.






share|cite|improve this answer









$endgroup$













  • $begingroup$
    The statement "For such a situation to be unavoidable, it would have to be that some lower layer polygon entirely covers two (or more) upper layer polygons." is not quite true. For example, if polygons A, B, C were entirely covered by polygons P and Q, we'd also get a similar problem. The area constraint rules this out as well, but we do have to check a more general condition. (And then you need a result like Hall's theorem to convince you that this is the only kind of problem.)
    $endgroup$
    – Misha Lavrov
    Nov 14 '18 at 14:55










  • $begingroup$
    @MishaLavrov The straightforward generalization here is that N + k, k > 0 polygons in the upper layer cannot share N polygons in the lower layer. ABCD{E...} cannot be covered by PQR and so on. All those situations are ruled out by the area constraint. N polygons each of unit area cannot cover N + k polygons of unit area.
    $endgroup$
    – Kaz
    Nov 15 '18 at 7:24










  • $begingroup$
    Yes, exactly. Moreover, without Hall's theorem, you do not know that this is the only obstacle.
    $endgroup$
    – Misha Lavrov
    Nov 15 '18 at 15:07














1












1








1





$begingroup$

It is "self evident" that we cannot use fewer than 1000 needles, just to punch a hole in every polygon in a single sheet.



By the pigeon hole principle, if we use more than 1000 needles, then some polygons must have more than one hole in them.



Suppose that punching 1000 holes in 1000 polygons in the upper sheet does not achieve perfect coverage in the lower sheet: not all 1000 polygons receive a hole. That requires that one or more polygons to receive two holes. (Our friend, pigeon hole, again).



Is that possible? Yes it is. For that to happen, all we need is the situation that two needles (necessarily) going through different polygons in the top sheet pierce the same polygon in the bottom sheet.



However, is this unavoidable? No, it isn't. Two needles going through different top polygons are never forced to map to the same bottom polygon. For such a situation to be unavoidable, it would have to be that some lower layer polygon entirely covers two (or more) upper layer polygons. This is ruled out by the key constraint that all polygons have the same area. Therefore the situation is avoidable; no pair of needles have to share the same lower-layer polygon.






share|cite|improve this answer









$endgroup$



It is "self evident" that we cannot use fewer than 1000 needles, just to punch a hole in every polygon in a single sheet.



By the pigeon hole principle, if we use more than 1000 needles, then some polygons must have more than one hole in them.



Suppose that punching 1000 holes in 1000 polygons in the upper sheet does not achieve perfect coverage in the lower sheet: not all 1000 polygons receive a hole. That requires that one or more polygons to receive two holes. (Our friend, pigeon hole, again).



Is that possible? Yes it is. For that to happen, all we need is the situation that two needles (necessarily) going through different polygons in the top sheet pierce the same polygon in the bottom sheet.



However, is this unavoidable? No, it isn't. Two needles going through different top polygons are never forced to map to the same bottom polygon. For such a situation to be unavoidable, it would have to be that some lower layer polygon entirely covers two (or more) upper layer polygons. This is ruled out by the key constraint that all polygons have the same area. Therefore the situation is avoidable; no pair of needles have to share the same lower-layer polygon.







share|cite|improve this answer












share|cite|improve this answer



share|cite|improve this answer










answered Nov 14 '18 at 8:31









KazKaz

6,22511327




6,22511327












  • $begingroup$
    The statement "For such a situation to be unavoidable, it would have to be that some lower layer polygon entirely covers two (or more) upper layer polygons." is not quite true. For example, if polygons A, B, C were entirely covered by polygons P and Q, we'd also get a similar problem. The area constraint rules this out as well, but we do have to check a more general condition. (And then you need a result like Hall's theorem to convince you that this is the only kind of problem.)
    $endgroup$
    – Misha Lavrov
    Nov 14 '18 at 14:55










  • $begingroup$
    @MishaLavrov The straightforward generalization here is that N + k, k > 0 polygons in the upper layer cannot share N polygons in the lower layer. ABCD{E...} cannot be covered by PQR and so on. All those situations are ruled out by the area constraint. N polygons each of unit area cannot cover N + k polygons of unit area.
    $endgroup$
    – Kaz
    Nov 15 '18 at 7:24










  • $begingroup$
    Yes, exactly. Moreover, without Hall's theorem, you do not know that this is the only obstacle.
    $endgroup$
    – Misha Lavrov
    Nov 15 '18 at 15:07


















  • $begingroup$
    The statement "For such a situation to be unavoidable, it would have to be that some lower layer polygon entirely covers two (or more) upper layer polygons." is not quite true. For example, if polygons A, B, C were entirely covered by polygons P and Q, we'd also get a similar problem. The area constraint rules this out as well, but we do have to check a more general condition. (And then you need a result like Hall's theorem to convince you that this is the only kind of problem.)
    $endgroup$
    – Misha Lavrov
    Nov 14 '18 at 14:55










  • $begingroup$
    @MishaLavrov The straightforward generalization here is that N + k, k > 0 polygons in the upper layer cannot share N polygons in the lower layer. ABCD{E...} cannot be covered by PQR and so on. All those situations are ruled out by the area constraint. N polygons each of unit area cannot cover N + k polygons of unit area.
    $endgroup$
    – Kaz
    Nov 15 '18 at 7:24










  • $begingroup$
    Yes, exactly. Moreover, without Hall's theorem, you do not know that this is the only obstacle.
    $endgroup$
    – Misha Lavrov
    Nov 15 '18 at 15:07
















$begingroup$
The statement "For such a situation to be unavoidable, it would have to be that some lower layer polygon entirely covers two (or more) upper layer polygons." is not quite true. For example, if polygons A, B, C were entirely covered by polygons P and Q, we'd also get a similar problem. The area constraint rules this out as well, but we do have to check a more general condition. (And then you need a result like Hall's theorem to convince you that this is the only kind of problem.)
$endgroup$
– Misha Lavrov
Nov 14 '18 at 14:55




$begingroup$
The statement "For such a situation to be unavoidable, it would have to be that some lower layer polygon entirely covers two (or more) upper layer polygons." is not quite true. For example, if polygons A, B, C were entirely covered by polygons P and Q, we'd also get a similar problem. The area constraint rules this out as well, but we do have to check a more general condition. (And then you need a result like Hall's theorem to convince you that this is the only kind of problem.)
$endgroup$
– Misha Lavrov
Nov 14 '18 at 14:55












$begingroup$
@MishaLavrov The straightforward generalization here is that N + k, k > 0 polygons in the upper layer cannot share N polygons in the lower layer. ABCD{E...} cannot be covered by PQR and so on. All those situations are ruled out by the area constraint. N polygons each of unit area cannot cover N + k polygons of unit area.
$endgroup$
– Kaz
Nov 15 '18 at 7:24




$begingroup$
@MishaLavrov The straightforward generalization here is that N + k, k > 0 polygons in the upper layer cannot share N polygons in the lower layer. ABCD{E...} cannot be covered by PQR and so on. All those situations are ruled out by the area constraint. N polygons each of unit area cannot cover N + k polygons of unit area.
$endgroup$
– Kaz
Nov 15 '18 at 7:24












$begingroup$
Yes, exactly. Moreover, without Hall's theorem, you do not know that this is the only obstacle.
$endgroup$
– Misha Lavrov
Nov 15 '18 at 15:07




$begingroup$
Yes, exactly. Moreover, without Hall's theorem, you do not know that this is the only obstacle.
$endgroup$
– Misha Lavrov
Nov 15 '18 at 15:07


















draft saved

draft discarded




















































Thanks for contributing an answer to Mathematics Stack Exchange!


  • Please be sure to answer the question. Provide details and share your research!

But avoid …



  • Asking for help, clarification, or responding to other answers.

  • Making statements based on opinion; back them up with references or personal experience.


Use MathJax to format equations. MathJax reference.


To learn more, see our tips on writing great answers.




draft saved


draft discarded














StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2995979%2fpunch-2000-holes-in-2000-polygons-with-1000-needles%23new-answer', 'question_page');
}
);

Post as a guest















Required, but never shown





















































Required, but never shown














Required, but never shown












Required, but never shown







Required, but never shown

































Required, but never shown














Required, but never shown












Required, but never shown







Required, but never shown







-

Popular posts from this blog

Florida Star v. B. J. F.

Image
Florida Star v. B. J. F. From Wikipedia, the free encyclopedia Jump to navigation Jump to search United States Supreme Court case Florida Star v. B. J. F. Supreme Court of the United States Argued March 21, 1989 Decided June 21, 1989 Full case name The Florida Star v. B. J. F. Citations 491 U.S. 524 ( more ) 109 S. Ct. 2603; 105 L. Ed. 2d 443; 1989 U.S. LEXIS 3120; 57 U.S.L.W. 4816; 16 Media L. Rep. 1801 Prior history The Florida Star v. B.J.F., 530 So.2d 286 (1988) Supreme Court of Florida; Florida Star v. B.J.F., 499 So.2d 883 (1986) Fla. Dist. Court of Appeals Holding Florida Stat. § 794.03 is unconstitutional to the extent it makes the truthful reporting of information that was a matter of public record unlawful, as it violates the First Amendment. Court membership Chief Justice William Rehnquist Associate Justices William J. Brennan Jr.  · Byron White Thurgood Marshall  · Harry Blac...
Read more

Danny Elfman

Image
Danny Elfman From Wikipedia, the free encyclopedia Jump to navigation Jump to search Danny Elfman Elfman at the 2010 San Diego Comic-Con Born Daniel Robert Elfman ( 1953-05-29 ) May 29, 1953 (age 65) Los Angeles, California, U.S. Spouse(s) Bridget Fonda ( m.  2003) Children 1 Musical career Genres Rock [1] ska [2] new wave film music video game music Occupation(s) Composer, singer, songwriter, record producer Instruments Trombone guitar percussion vocals keyboards [3] Years active 1972–present Associated acts Oingo Boingo James Newton Howard Daniel Robert Elfman (born May 29, 1953) is an American composer, singer, songwriter, and record producer. Elfman first became known for being the lead singer and songwriter for the band Oingo Boingo from 1974 to 1995. He is well known for scoring films and television shows, particularly his frequent collabora...
Read more

Lugert, Oklahoma

Image
Unincorporated community in Oklahoma, United States Lugert, Oklahoma Unincorporated community Foundations from the town of Lugert at the bottom of Lake Altus-Lugert Lugert, Oklahoma Location within the state of Oklahoma Coordinates: 34°53′45″N 99°16′31″W  /  34.89583°N 99.27528°W  / 34.89583; -99.27528 Coordinates: 34°53′45″N 99°16′31″W  /  34.89583°N 99.27528°W  / 34.89583; -99.27528 Country United States State Oklahoma County Kiowa Time zone UTC-6 (Central (CST))  • Summer (DST) UTC-5 (CDT) GNIS feature ID 1100597 Lugert is an unincorporated community in Kiowa County, Oklahoma. [1] The town of Lugert was founded in 1901 on 80 acres (320,000 m 2 ). In the town, there was a general store that housed the Post office and sold dry goods, school supplies, groceries, harnesses, axes and much more. It was named for Frank Lugert, who had moved to the area in 1898. Lugert owned land where the town was sited and also owned the general st...
Read more