Mixing
Generating, or counting the sides of, “square-like” polygons (with all congruent sides, and all angles...
$begingroup$
What are some of the polygons that have all congruent sides and all angles $90^circ$ or $270^circ$? Is there a pattern for generating these, or a formula for the number of sides? These don't have to be convex (as the $270^circ$ angle shows).
Also, the shapes can only have 2 line segments extending from each vertex.
I know a square is one, and a plus sign-like shape, but I am looking for something more general, like a pattern.
geometry
edited Jan 13 at 0:27
Blue
48.4k870154
asked Jan 12 at 17:28
mathboy1296mathboy1296
235
$endgroup$
add a comment |
$begingroup$
What are some of the polygons that have all congruent sides and all angles $90^circ$ or $270^circ$? Is there a pattern for generating these, or a formula for the number of sides? These don't have to be convex (as the $270^circ$ angle shows).
Also, the shapes can only have 2 line segments extending from each vertex.
I know a square is one, and a plus sign-like shape, but I am looking for something more general, like a pattern.
geometry
edited Jan 13 at 0:27
Blue
48.4k870154
asked Jan 12 at 17:28
mathboy1296mathboy1296
235
$endgroup$
1
$begingroup$
Can vertices coincide? E.g. do you allow a polygon whose corners angles are 90-90-90-270-90-90-90-270? Or one where two convex corners touch?
$endgroup$
– Henning Makholm
Jan 12 at 17:33
1
$begingroup$
If I understand you correctly, these are a subset of the polyominoes. If you really want all the sides to be congruent, it will be a very small subset. I can think offhand of one with 9 sides and one with 12.
$endgroup$
– MJD
Jan 12 at 17:34
$begingroup$
@HenningMakholm I don't think it counts as a polygon if it self-intersects.
$endgroup$
– Frpzzd
Jan 12 at 17:41
$begingroup$
For "sides" read "squares". They have 20 and 24 sides respectively. There is also one with 13 squares and 20 sides.
$endgroup$
– MJD
Jan 12 at 17:41
$begingroup$
Thanks for an interesting and fun question!
$endgroup$
– timtfj
Jan 15 at 1:53
add a comment |
$begingroup$
What are some of the polygons that have all congruent sides and all angles $90^circ$ or $270^circ$? Is there a pattern for generating these, or a formula for the number of sides? These don't have to be convex (as the $270^circ$ angle shows).
Also, the shapes can only have 2 line segments extending from each vertex.
I know a square is one, and a plus sign-like shape, but I am looking for something more general, like a pattern.
geometry
edited Jan 13 at 0:27
Blue
48.4k870154
asked Jan 12 at 17:28
mathboy1296mathboy1296
235
$endgroup$
What are some of the polygons that have all congruent sides and all angles $90^circ$ or $270^circ$? Is there a pattern for generating these, or a formula for the number of sides? These don't have to be convex (as the $270^circ$ angle shows).
Also, the shapes can only have 2 line segments extending from each vertex.
I know a square is one, and a plus sign-like shape, but I am looking for something more general, like a pattern.
geometry
geometry
edited Jan 13 at 0:27
Blue
48.4k870154
asked Jan 12 at 17:28
mathboy1296mathboy1296
235
edited Jan 13 at 0:27
Blue
48.4k870154
asked Jan 12 at 17:28
mathboy1296mathboy1296
235
edited Jan 13 at 0:27
Blue
48.4k870154
edited Jan 13 at 0:27
Blue
48.4k870154
edited Jan 13 at 0:27
Blue
48.4k870154
48.4k870154
asked Jan 12 at 17:28
mathboy1296mathboy1296
235
asked Jan 12 at 17:28
mathboy1296mathboy1296
235
asked Jan 12 at 17:28
mathboy1296mathboy1296
235
235
1
$begingroup$
Can vertices coincide? E.g. do you allow a polygon whose corners angles are 90-90-90-270-90-90-90-270? Or one where two convex corners touch?
$endgroup$
– Henning Makholm
Jan 12 at 17:33
1
$begingroup$
If I understand you correctly, these are a subset of the polyominoes. If you really want all the sides to be congruent, it will be a very small subset. I can think offhand of one with 9 sides and one with 12.
$endgroup$
– MJD
Jan 12 at 17:34
$begingroup$
@HenningMakholm I don't think it counts as a polygon if it self-intersects.
$endgroup$
– Frpzzd
Jan 12 at 17:41
$begingroup$
For "sides" read "squares". They have 20 and 24 sides respectively. There is also one with 13 squares and 20 sides.
$endgroup$
– MJD
Jan 12 at 17:41
$begingroup$
Thanks for an interesting and fun question!
$endgroup$
– timtfj
Jan 15 at 1:53
add a comment |
1
$begingroup$
Can vertices coincide? E.g. do you allow a polygon whose corners angles are 90-90-90-270-90-90-90-270? Or one where two convex corners touch?
$endgroup$
– Henning Makholm
Jan 12 at 17:33
1
$begingroup$
If I understand you correctly, these are a subset of the polyominoes. If you really want all the sides to be congruent, it will be a very small subset. I can think offhand of one with 9 sides and one with 12.
$endgroup$
– MJD
Jan 12 at 17:34
$begingroup$
@HenningMakholm I don't think it counts as a polygon if it self-intersects.
$endgroup$
– Frpzzd
Jan 12 at 17:41
$begingroup$
For "sides" read "squares". They have 20 and 24 sides respectively. There is also one with 13 squares and 20 sides.
$endgroup$
– MJD
Jan 12 at 17:41
$begingroup$
Thanks for an interesting and fun question!
$endgroup$
– timtfj
Jan 15 at 1:53
1
1
$begingroup$
Can vertices coincide? E.g. do you allow a polygon whose corners angles are 90-90-90-270-90-90-90-270? Or one where two convex corners touch?
$endgroup$
– Henning Makholm
Jan 12 at 17:33
$begingroup$
Can vertices coincide? E.g. do you allow a polygon whose corners angles are 90-90-90-270-90-90-90-270? Or one where two convex corners touch?
$endgroup$
– Henning Makholm
Jan 12 at 17:33
1
1
$begingroup$
If I understand you correctly, these are a subset of the polyominoes. If you really want all the sides to be congruent, it will be a very small subset. I can think offhand of one with 9 sides and one with 12.
$endgroup$
– MJD
Jan 12 at 17:34
$begingroup$
If I understand you correctly, these are a subset of the polyominoes. If you really want all the sides to be congruent, it will be a very small subset. I can think offhand of one with 9 sides and one with 12.
$endgroup$
– MJD
Jan 12 at 17:34
$begingroup$
@HenningMakholm I don't think it counts as a polygon if it self-intersects.
$endgroup$
– Frpzzd
Jan 12 at 17:41
$begingroup$
@HenningMakholm I don't think it counts as a polygon if it self-intersects.
$endgroup$
– Frpzzd
Jan 12 at 17:41
$begingroup$
For "sides" read "squares". They have 20 and 24 sides respectively. There is also one with 13 squares and 20 sides.
$endgroup$
– MJD
Jan 12 at 17:41
$begingroup$
For "sides" read "squares". They have 20 and 24 sides respectively. There is also one with 13 squares and 20 sides.
$endgroup$
– MJD
Jan 12 at 17:41
$begingroup$
Thanks for an interesting and fun question!
$endgroup$
– timtfj
Jan 15 at 1:53
$begingroup$
Thanks for an interesting and fun question!
$endgroup$
– timtfj
Jan 15 at 1:53
add a comment |
4 Answers
4
active
oldest
votes
$begingroup$
Edit: I've added a proof that the $8$-sided polygon can't exist.
Number of edges
Not an actual formula for the number of edges, but a proof that:
The number of edges is always a multiple of $4$.
Travelling anticlockwise around the perimeter of the polygon, assign to each edge one of {up, down, left, right} according to the direction of travel along that edge.
It's clear that vertical and horizontal edges must alternate, since two vertical/horizontal edges in succession either make a longer edge or place one edge on top of the other, neither of which is alllowed.
Let $U, D, L, R$ be the number of edges with the directions up, down, left and right respectively.
In order to return to our starting point both vertically and horizontally, we require $$U=D$$ and $$L=R.$$
There are $U+D$ vertical edges and $L+R$ horizontal edges. But every horizontal edge is preceded by a vertical adge and vice versa, so $$U+D=L+R.$$
Together, these requirements imply
$$U=D=L=R=k.$$
The total number of edges is
$$U+D+L+R=4k,$$
and therefore a multiple of $4$.
Constructing the polygons
This is now looking like a combinatorics problem. For a given integer $k$, we must generate permutations of the four edge directions such that:
- each direction occurs $k$ times.
- vertical and horizontal directions alternate.
- no section of the path (considering the whole path as a loop) may contain the same number of up, down, left and right edges.
The last of of these is to prevent the path from returning to a previously visited point before it's complete.
I think these requirements guarantee that every permutation generates a valid polygon, and that all valid polygons are generated (with a lot of repeats).
Number of vertices of each type
Consider the exterior angle at each vertex as we follow an anticlockwise path. This is $90°$ for a vertex where we turn left, and $-90°$ for one where we turn right. We need to have made one full rotation when we return to the starting point: that is, the sum of all the exterior angles must be $360°$.
There must therefore be four more vertices where we turn left than ones where we turn right: or in terms of the internal angles, $4$ more $90°$ vertices than $270°$ ones.
For the case where there are $4k$ vertices, let $n$ be the number of $270°$ vertices. Then there are $n+4$ $90°$ vertices, giving $2n+4$ vertices altogether. So we have
$$2n+4=4k,$$
from which
$$n=2(k-1)$$
Therefore
A $4k$-sided polygon of this type has $2(k-1)$ $270°$ vertices and $2(k+1)$ $90°$ vertices.
Impossibility of the 8-sided polygon
Suppose one of these polygons has $8$ sides. From the above, it has six $90°$ vertices and two $270°$ vertices. How are these arranged as we travel round the polygon?
First note that three vertices of the same type in succession—corresponding to three left or right turns—takes us round a small square. This is only OK if the small square is the entire polygon. So for $k>1$, no more than two vertices of the same type may occur in succession.
So each of the two $270°$ vertices can be followed by at most two $90°$ ones. But this only allows the polygon to have four $90°$ vertices, and it needs to have six.
Therefore
The 8-sided polygon cannot exist.
A similar argument shows that
The only $12$-sided polygon is the cross shape.
For this one we have $k=3$, giving $8$ vertices of one type and $4$ of the other. Denoting the two types as $L$ for a left turn ($90°$) and $R$ for a right turn ($270°$), the only possible sequence is $RLLRLLRLLRLL$, which generates the cross shape. Every $R$ has to be followed by $LL$, to avoid having three $L$'s in succession.
answered Jan 12 at 23:04
timtfjtimtfj
2,278420
$endgroup$
$begingroup$
Together with the simple square and the diagonal arrangement of overlapping crosses in Frpzzd's answer, this is enough to show that polygons of $4k$ sides are possible for $k=1$ and for all $kgeq 3$. But it's bedtime and I'm having trouble posting, so I'll leave that for now.
$endgroup$
– timtfj
Jan 15 at 1:37
$begingroup$
Only for those values of $k$, that is. Every positive $k$ except $2$.
$endgroup$
– timtfj
Jan 15 at 1:49
add a comment |
$begingroup$
Here are a few interesting infinite families of polygons satisfying your requirements. One way to generalize your "plus-sign" example is to attach many of these together to form a long chain of them, like this:
The $n$th polygon in this sequence of polygons has $8n+4$ sides. You can also attach the plus-signs to each other like this:
The $n$th polygon in this sequence will have $4n+8$ sides, if you choose the ordinary "plus-sign" polygon as the first member of the sequence. You can also combine polygons from either of these families to create monstrosities like this:
This reasoning will lead to @HenningMakholm's conclusion that any shape created can be made by attaching these "plus-sign" polygons to each other.
answered Jan 12 at 17:56
FrpzzdFrpzzd
22.9k841109
$endgroup$
1
$begingroup$
Is there any way to generalize both of these families (in terms of a number of sides formula)? Oscar Lanzi had 4n+4. Is that the most general that these polyominos can get to?
$endgroup$
– mathboy1296
Jan 12 at 18:57
$begingroup$
Actually Imistyped. I get only 8n+4. Will edit my answer.
$endgroup$
– Oscar Lanzi
Jan 14 at 0:57
add a comment |
$begingroup$
I think the polygons you can make in this way are exactly:
A square
Any connected shape without holes that can be made by selecting some of the white squares on an infinite checkerboard and placing a "plus sign" centered on each selected square. (The arms of neighboring plus signs will overlap).
answered Jan 12 at 17:52
Henning MakholmHenning Makholm
240k17305542
$endgroup$
add a comment |
$begingroup$
There are infinitely many of them. You can generate an infinite subset by building on a single square.
Start with the one square. Attach four more, congruent squares one on each side, getting your "plus sign". Note that this figure has four 270° corners located at the corners of the first square. Place another square play each of these concavoties, filling in the space around that point, then add four more squares on the outernost edges of the +sign you had. You now have a figure containing 20 sides and vertices, with eight of the vertices concave. Note that these concave vertices had been the 90° corners of the previous + sign.
You can keep going. At each stage put a square in each concave corner and then squares on the outer edges of the latest figure to get the next figure. After $n$ iterations there are $4(2n+1)$ sides, the same number of vertices, and $4n$ of these vertices having 270° angles.
As mentioned, this is only a subset of the possibilities. Others will likely post more.
answered Jan 12 at 17:46
Oscar LanziOscar Lanzi
12.7k12136
$endgroup$
$begingroup$
I don't think you can get all instances of $4(n+1)$: it is not possible to have $8$ sides. All multiples of $4$ from $12$ upwards can be realized by diagonal sequences of pluses, though.
$endgroup$
– Henning Makholm
Jan 14 at 0:32
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
});
}
});
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3071149%2fgenerating-or-counting-the-sides-of-square-like-polygons-with-all-congruent%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
4 Answers
4
active
oldest
votes
4 Answers
4
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Edit: I've added a proof that the $8$-sided polygon can't exist.
Number of edges
Not an actual formula for the number of edges, but a proof that:
The number of edges is always a multiple of $4$.
Travelling anticlockwise around the perimeter of the polygon, assign to each edge one of {up, down, left, right} according to the direction of travel along that edge.
It's clear that vertical and horizontal edges must alternate, since two vertical/horizontal edges in succession either make a longer edge or place one edge on top of the other, neither of which is alllowed.
Let $U, D, L, R$ be the number of edges with the directions up, down, left and right respectively.
In order to return to our starting point both vertically and horizontally, we require $$U=D$$ and $$L=R.$$
There are $U+D$ vertical edges and $L+R$ horizontal edges. But every horizontal edge is preceded by a vertical adge and vice versa, so $$U+D=L+R.$$
Together, these requirements imply
$$U=D=L=R=k.$$
The total number of edges is
$$U+D+L+R=4k,$$
and therefore a multiple of $4$.
Constructing the polygons
This is now looking like a combinatorics problem. For a given integer $k$, we must generate permutations of the four edge directions such that:
- each direction occurs $k$ times.
- vertical and horizontal directions alternate.
- no section of the path (considering the whole path as a loop) may contain the same number of up, down, left and right edges.
The last of of these is to prevent the path from returning to a previously visited point before it's complete.
I think these requirements guarantee that every permutation generates a valid polygon, and that all valid polygons are generated (with a lot of repeats).
Number of vertices of each type
Consider the exterior angle at each vertex as we follow an anticlockwise path. This is $90°$ for a vertex where we turn left, and $-90°$ for one where we turn right. We need to have made one full rotation when we return to the starting point: that is, the sum of all the exterior angles must be $360°$.
There must therefore be four more vertices where we turn left than ones where we turn right: or in terms of the internal angles, $4$ more $90°$ vertices than $270°$ ones.
For the case where there are $4k$ vertices, let $n$ be the number of $270°$ vertices. Then there are $n+4$ $90°$ vertices, giving $2n+4$ vertices altogether. So we have
$$2n+4=4k,$$
from which
$$n=2(k-1)$$
Therefore
A $4k$-sided polygon of this type has $2(k-1)$ $270°$ vertices and $2(k+1)$ $90°$ vertices.
Impossibility of the 8-sided polygon
Suppose one of these polygons has $8$ sides. From the above, it has six $90°$ vertices and two $270°$ vertices. How are these arranged as we travel round the polygon?
First note that three vertices of the same type in succession—corresponding to three left or right turns—takes us round a small square. This is only OK if the small square is the entire polygon. So for $k>1$, no more than two vertices of the same type may occur in succession.
So each of the two $270°$ vertices can be followed by at most two $90°$ ones. But this only allows the polygon to have four $90°$ vertices, and it needs to have six.
Therefore
The 8-sided polygon cannot exist.
A similar argument shows that
The only $12$-sided polygon is the cross shape.
For this one we have $k=3$, giving $8$ vertices of one type and $4$ of the other. Denoting the two types as $L$ for a left turn ($90°$) and $R$ for a right turn ($270°$), the only possible sequence is $RLLRLLRLLRLL$, which generates the cross shape. Every $R$ has to be followed by $LL$, to avoid having three $L$'s in succession.
answered Jan 12 at 23:04
timtfjtimtfj
2,278420
$endgroup$
$begingroup$
Together with the simple square and the diagonal arrangement of overlapping crosses in Frpzzd's answer, this is enough to show that polygons of $4k$ sides are possible for $k=1$ and for all $kgeq 3$. But it's bedtime and I'm having trouble posting, so I'll leave that for now.
$endgroup$
– timtfj
Jan 15 at 1:37
$begingroup$
Only for those values of $k$, that is. Every positive $k$ except $2$.
$endgroup$
– timtfj
Jan 15 at 1:49
add a comment |
$begingroup$
Edit: I've added a proof that the $8$-sided polygon can't exist.
Number of edges
Not an actual formula for the number of edges, but a proof that:
The number of edges is always a multiple of $4$.
Travelling anticlockwise around the perimeter of the polygon, assign to each edge one of {up, down, left, right} according to the direction of travel along that edge.
It's clear that vertical and horizontal edges must alternate, since two vertical/horizontal edges in succession either make a longer edge or place one edge on top of the other, neither of which is alllowed.
Let $U, D, L, R$ be the number of edges with the directions up, down, left and right respectively.
In order to return to our starting point both vertically and horizontally, we require $$U=D$$ and $$L=R.$$
There are $U+D$ vertical edges and $L+R$ horizontal edges. But every horizontal edge is preceded by a vertical adge and vice versa, so $$U+D=L+R.$$
Together, these requirements imply
$$U=D=L=R=k.$$
The total number of edges is
$$U+D+L+R=4k,$$
and therefore a multiple of $4$.
Constructing the polygons
This is now looking like a combinatorics problem. For a given integer $k$, we must generate permutations of the four edge directions such that:
- each direction occurs $k$ times.
- vertical and horizontal directions alternate.
- no section of the path (considering the whole path as a loop) may contain the same number of up, down, left and right edges.
The last of of these is to prevent the path from returning to a previously visited point before it's complete.
I think these requirements guarantee that every permutation generates a valid polygon, and that all valid polygons are generated (with a lot of repeats).
Number of vertices of each type
Consider the exterior angle at each vertex as we follow an anticlockwise path. This is $90°$ for a vertex where we turn left, and $-90°$ for one where we turn right. We need to have made one full rotation when we return to the starting point: that is, the sum of all the exterior angles must be $360°$.
There must therefore be four more vertices where we turn left than ones where we turn right: or in terms of the internal angles, $4$ more $90°$ vertices than $270°$ ones.
For the case where there are $4k$ vertices, let $n$ be the number of $270°$ vertices. Then there are $n+4$ $90°$ vertices, giving $2n+4$ vertices altogether. So we have
$$2n+4=4k,$$
from which
$$n=2(k-1)$$
Therefore
A $4k$-sided polygon of this type has $2(k-1)$ $270°$ vertices and $2(k+1)$ $90°$ vertices.
Impossibility of the 8-sided polygon
Suppose one of these polygons has $8$ sides. From the above, it has six $90°$ vertices and two $270°$ vertices. How are these arranged as we travel round the polygon?
First note that three vertices of the same type in succession—corresponding to three left or right turns—takes us round a small square. This is only OK if the small square is the entire polygon. So for $k>1$, no more than two vertices of the same type may occur in succession.
So each of the two $270°$ vertices can be followed by at most two $90°$ ones. But this only allows the polygon to have four $90°$ vertices, and it needs to have six.
Therefore
The 8-sided polygon cannot exist.
A similar argument shows that
The only $12$-sided polygon is the cross shape.
For this one we have $k=3$, giving $8$ vertices of one type and $4$ of the other. Denoting the two types as $L$ for a left turn ($90°$) and $R$ for a right turn ($270°$), the only possible sequence is $RLLRLLRLLRLL$, which generates the cross shape. Every $R$ has to be followed by $LL$, to avoid having three $L$'s in succession.
answered Jan 12 at 23:04
timtfjtimtfj
2,278420
$endgroup$
$begingroup$
Together with the simple square and the diagonal arrangement of overlapping crosses in Frpzzd's answer, this is enough to show that polygons of $4k$ sides are possible for $k=1$ and for all $kgeq 3$. But it's bedtime and I'm having trouble posting, so I'll leave that for now.
$endgroup$
– timtfj
Jan 15 at 1:37
$begingroup$
Only for those values of $k$, that is. Every positive $k$ except $2$.
$endgroup$
– timtfj
Jan 15 at 1:49
add a comment |
$begingroup$
Edit: I've added a proof that the $8$-sided polygon can't exist.
Number of edges
Not an actual formula for the number of edges, but a proof that:
The number of edges is always a multiple of $4$.
Travelling anticlockwise around the perimeter of the polygon, assign to each edge one of {up, down, left, right} according to the direction of travel along that edge.
It's clear that vertical and horizontal edges must alternate, since two vertical/horizontal edges in succession either make a longer edge or place one edge on top of the other, neither of which is alllowed.
Let $U, D, L, R$ be the number of edges with the directions up, down, left and right respectively.
In order to return to our starting point both vertically and horizontally, we require $$U=D$$ and $$L=R.$$
There are $U+D$ vertical edges and $L+R$ horizontal edges. But every horizontal edge is preceded by a vertical adge and vice versa, so $$U+D=L+R.$$
Together, these requirements imply
$$U=D=L=R=k.$$
The total number of edges is
$$U+D+L+R=4k,$$
and therefore a multiple of $4$.
Constructing the polygons
This is now looking like a combinatorics problem. For a given integer $k$, we must generate permutations of the four edge directions such that:
- each direction occurs $k$ times.
- vertical and horizontal directions alternate.
- no section of the path (considering the whole path as a loop) may contain the same number of up, down, left and right edges.
The last of of these is to prevent the path from returning to a previously visited point before it's complete.
I think these requirements guarantee that every permutation generates a valid polygon, and that all valid polygons are generated (with a lot of repeats).
Number of vertices of each type
Consider the exterior angle at each vertex as we follow an anticlockwise path. This is $90°$ for a vertex where we turn left, and $-90°$ for one where we turn right. We need to have made one full rotation when we return to the starting point: that is, the sum of all the exterior angles must be $360°$.
There must therefore be four more vertices where we turn left than ones where we turn right: or in terms of the internal angles, $4$ more $90°$ vertices than $270°$ ones.
For the case where there are $4k$ vertices, let $n$ be the number of $270°$ vertices. Then there are $n+4$ $90°$ vertices, giving $2n+4$ vertices altogether. So we have
$$2n+4=4k,$$
from which
$$n=2(k-1)$$
Therefore
A $4k$-sided polygon of this type has $2(k-1)$ $270°$ vertices and $2(k+1)$ $90°$ vertices.
Impossibility of the 8-sided polygon
Suppose one of these polygons has $8$ sides. From the above, it has six $90°$ vertices and two $270°$ vertices. How are these arranged as we travel round the polygon?
First note that three vertices of the same type in succession—corresponding to three left or right turns—takes us round a small square. This is only OK if the small square is the entire polygon. So for $k>1$, no more than two vertices of the same type may occur in succession.
So each of the two $270°$ vertices can be followed by at most two $90°$ ones. But this only allows the polygon to have four $90°$ vertices, and it needs to have six.
Therefore
The 8-sided polygon cannot exist.
A similar argument shows that
The only $12$-sided polygon is the cross shape.
For this one we have $k=3$, giving $8$ vertices of one type and $4$ of the other. Denoting the two types as $L$ for a left turn ($90°$) and $R$ for a right turn ($270°$), the only possible sequence is $RLLRLLRLLRLL$, which generates the cross shape. Every $R$ has to be followed by $LL$, to avoid having three $L$'s in succession.
answered Jan 12 at 23:04
timtfjtimtfj
2,278420
$endgroup$
Edit: I've added a proof that the $8$-sided polygon can't exist.
Number of edges
Not an actual formula for the number of edges, but a proof that:
The number of edges is always a multiple of $4$.
Travelling anticlockwise around the perimeter of the polygon, assign to each edge one of {up, down, left, right} according to the direction of travel along that edge.
It's clear that vertical and horizontal edges must alternate, since two vertical/horizontal edges in succession either make a longer edge or place one edge on top of the other, neither of which is alllowed.
Let $U, D, L, R$ be the number of edges with the directions up, down, left and right respectively.
In order to return to our starting point both vertically and horizontally, we require $$U=D$$ and $$L=R.$$
There are $U+D$ vertical edges and $L+R$ horizontal edges. But every horizontal edge is preceded by a vertical adge and vice versa, so $$U+D=L+R.$$
Together, these requirements imply
$$U=D=L=R=k.$$
The total number of edges is
$$U+D+L+R=4k,$$
and therefore a multiple of $4$.
Constructing the polygons
This is now looking like a combinatorics problem. For a given integer $k$, we must generate permutations of the four edge directions such that:
- each direction occurs $k$ times.
- vertical and horizontal directions alternate.
- no section of the path (considering the whole path as a loop) may contain the same number of up, down, left and right edges.
The last of of these is to prevent the path from returning to a previously visited point before it's complete.
I think these requirements guarantee that every permutation generates a valid polygon, and that all valid polygons are generated (with a lot of repeats).
Number of vertices of each type
Consider the exterior angle at each vertex as we follow an anticlockwise path. This is $90°$ for a vertex where we turn left, and $-90°$ for one where we turn right. We need to have made one full rotation when we return to the starting point: that is, the sum of all the exterior angles must be $360°$.
There must therefore be four more vertices where we turn left than ones where we turn right: or in terms of the internal angles, $4$ more $90°$ vertices than $270°$ ones.
For the case where there are $4k$ vertices, let $n$ be the number of $270°$ vertices. Then there are $n+4$ $90°$ vertices, giving $2n+4$ vertices altogether. So we have
$$2n+4=4k,$$
from which
$$n=2(k-1)$$
Therefore
A $4k$-sided polygon of this type has $2(k-1)$ $270°$ vertices and $2(k+1)$ $90°$ vertices.
Impossibility of the 8-sided polygon
Suppose one of these polygons has $8$ sides. From the above, it has six $90°$ vertices and two $270°$ vertices. How are these arranged as we travel round the polygon?
First note that three vertices of the same type in succession—corresponding to three left or right turns—takes us round a small square. This is only OK if the small square is the entire polygon. So for $k>1$, no more than two vertices of the same type may occur in succession.
So each of the two $270°$ vertices can be followed by at most two $90°$ ones. But this only allows the polygon to have four $90°$ vertices, and it needs to have six.
Therefore
The 8-sided polygon cannot exist.
A similar argument shows that
The only $12$-sided polygon is the cross shape.
For this one we have $k=3$, giving $8$ vertices of one type and $4$ of the other. Denoting the two types as $L$ for a left turn ($90°$) and $R$ for a right turn ($270°$), the only possible sequence is $RLLRLLRLLRLL$, which generates the cross shape. Every $R$ has to be followed by $LL$, to avoid having three $L$'s in succession.
answered Jan 12 at 23:04
timtfjtimtfj
2,278420
edited Jan 15 at 1:23
answered Jan 12 at 23:04
timtfjtimtfj
2,278420
answered Jan 12 at 23:04
timtfjtimtfj
2,278420
answered Jan 12 at 23:04
timtfjtimtfj
2,278420
2,278420
$begingroup$
Together with the simple square and the diagonal arrangement of overlapping crosses in Frpzzd's answer, this is enough to show that polygons of $4k$ sides are possible for $k=1$ and for all $kgeq 3$. But it's bedtime and I'm having trouble posting, so I'll leave that for now.
$endgroup$
– timtfj
Jan 15 at 1:37
$begingroup$
Only for those values of $k$, that is. Every positive $k$ except $2$.
$endgroup$
– timtfj
Jan 15 at 1:49
add a comment |
$begingroup$
Together with the simple square and the diagonal arrangement of overlapping crosses in Frpzzd's answer, this is enough to show that polygons of $4k$ sides are possible for $k=1$ and for all $kgeq 3$. But it's bedtime and I'm having trouble posting, so I'll leave that for now.
$endgroup$
– timtfj
Jan 15 at 1:37
$begingroup$
Only for those values of $k$, that is. Every positive $k$ except $2$.
$endgroup$
– timtfj
Jan 15 at 1:49
$begingroup$
Together with the simple square and the diagonal arrangement of overlapping crosses in Frpzzd's answer, this is enough to show that polygons of $4k$ sides are possible for $k=1$ and for all $kgeq 3$. But it's bedtime and I'm having trouble posting, so I'll leave that for now.
$endgroup$
– timtfj
Jan 15 at 1:37
$begingroup$
Together with the simple square and the diagonal arrangement of overlapping crosses in Frpzzd's answer, this is enough to show that polygons of $4k$ sides are possible for $k=1$ and for all $kgeq 3$. But it's bedtime and I'm having trouble posting, so I'll leave that for now.
$endgroup$
– timtfj
Jan 15 at 1:37
$begingroup$
Only for those values of $k$, that is. Every positive $k$ except $2$.
$endgroup$
– timtfj
Jan 15 at 1:49
$begingroup$
Only for those values of $k$, that is. Every positive $k$ except $2$.
$endgroup$
– timtfj
Jan 15 at 1:49
add a comment |
$begingroup$
Here are a few interesting infinite families of polygons satisfying your requirements. One way to generalize your "plus-sign" example is to attach many of these together to form a long chain of them, like this:
The $n$th polygon in this sequence of polygons has $8n+4$ sides. You can also attach the plus-signs to each other like this:
The $n$th polygon in this sequence will have $4n+8$ sides, if you choose the ordinary "plus-sign" polygon as the first member of the sequence. You can also combine polygons from either of these families to create monstrosities like this:
This reasoning will lead to @HenningMakholm's conclusion that any shape created can be made by attaching these "plus-sign" polygons to each other.
answered Jan 12 at 17:56
FrpzzdFrpzzd
22.9k841109
$endgroup$
1
$begingroup$
Is there any way to generalize both of these families (in terms of a number of sides formula)? Oscar Lanzi had 4n+4. Is that the most general that these polyominos can get to?
$endgroup$
– mathboy1296
Jan 12 at 18:57
$begingroup$
Actually Imistyped. I get only 8n+4. Will edit my answer.
$endgroup$
– Oscar Lanzi
Jan 14 at 0:57
add a comment |
$begingroup$
Here are a few interesting infinite families of polygons satisfying your requirements. One way to generalize your "plus-sign" example is to attach many of these together to form a long chain of them, like this:
The $n$th polygon in this sequence of polygons has $8n+4$ sides. You can also attach the plus-signs to each other like this:
The $n$th polygon in this sequence will have $4n+8$ sides, if you choose the ordinary "plus-sign" polygon as the first member of the sequence. You can also combine polygons from either of these families to create monstrosities like this:
This reasoning will lead to @HenningMakholm's conclusion that any shape created can be made by attaching these "plus-sign" polygons to each other.
answered Jan 12 at 17:56
FrpzzdFrpzzd
22.9k841109
$endgroup$
1
$begingroup$
Is there any way to generalize both of these families (in terms of a number of sides formula)? Oscar Lanzi had 4n+4. Is that the most general that these polyominos can get to?
$endgroup$
– mathboy1296
Jan 12 at 18:57
$begingroup$
Actually Imistyped. I get only 8n+4. Will edit my answer.
$endgroup$
– Oscar Lanzi
Jan 14 at 0:57
add a comment |
$begingroup$
Here are a few interesting infinite families of polygons satisfying your requirements. One way to generalize your "plus-sign" example is to attach many of these together to form a long chain of them, like this:
The $n$th polygon in this sequence of polygons has $8n+4$ sides. You can also attach the plus-signs to each other like this:
The $n$th polygon in this sequence will have $4n+8$ sides, if you choose the ordinary "plus-sign" polygon as the first member of the sequence. You can also combine polygons from either of these families to create monstrosities like this:
This reasoning will lead to @HenningMakholm's conclusion that any shape created can be made by attaching these "plus-sign" polygons to each other.
answered Jan 12 at 17:56
FrpzzdFrpzzd
22.9k841109
$endgroup$
Here are a few interesting infinite families of polygons satisfying your requirements. One way to generalize your "plus-sign" example is to attach many of these together to form a long chain of them, like this:
The $n$th polygon in this sequence of polygons has $8n+4$ sides. You can also attach the plus-signs to each other like this:
The $n$th polygon in this sequence will have $4n+8$ sides, if you choose the ordinary "plus-sign" polygon as the first member of the sequence. You can also combine polygons from either of these families to create monstrosities like this:
This reasoning will lead to @HenningMakholm's conclusion that any shape created can be made by attaching these "plus-sign" polygons to each other.
answered Jan 12 at 17:56
FrpzzdFrpzzd
22.9k841109
answered Jan 12 at 17:56
FrpzzdFrpzzd
22.9k841109
answered Jan 12 at 17:56
FrpzzdFrpzzd
22.9k841109
answered Jan 12 at 17:56
FrpzzdFrpzzd
22.9k841109
22.9k841109
1
$begingroup$
Is there any way to generalize both of these families (in terms of a number of sides formula)? Oscar Lanzi had 4n+4. Is that the most general that these polyominos can get to?
$endgroup$
– mathboy1296
Jan 12 at 18:57
$begingroup$
Actually Imistyped. I get only 8n+4. Will edit my answer.
$endgroup$
– Oscar Lanzi
Jan 14 at 0:57
add a comment |
1
$begingroup$
Is there any way to generalize both of these families (in terms of a number of sides formula)? Oscar Lanzi had 4n+4. Is that the most general that these polyominos can get to?
$endgroup$
– mathboy1296
Jan 12 at 18:57
$begingroup$
Actually Imistyped. I get only 8n+4. Will edit my answer.
$endgroup$
– Oscar Lanzi
Jan 14 at 0:57
1
1
$begingroup$
Is there any way to generalize both of these families (in terms of a number of sides formula)? Oscar Lanzi had 4n+4. Is that the most general that these polyominos can get to?
$endgroup$
– mathboy1296
Jan 12 at 18:57
$begingroup$
Is there any way to generalize both of these families (in terms of a number of sides formula)? Oscar Lanzi had 4n+4. Is that the most general that these polyominos can get to?
$endgroup$
– mathboy1296
Jan 12 at 18:57
$begingroup$
Actually Imistyped. I get only 8n+4. Will edit my answer.
$endgroup$
– Oscar Lanzi
Jan 14 at 0:57
$begingroup$
Actually Imistyped. I get only 8n+4. Will edit my answer.
$endgroup$
– Oscar Lanzi
Jan 14 at 0:57
add a comment |
$begingroup$
I think the polygons you can make in this way are exactly:
A square
Any connected shape without holes that can be made by selecting some of the white squares on an infinite checkerboard and placing a "plus sign" centered on each selected square. (The arms of neighboring plus signs will overlap).
answered Jan 12 at 17:52
Henning MakholmHenning Makholm
240k17305542
$endgroup$
add a comment |
$begingroup$
I think the polygons you can make in this way are exactly:
A square
Any connected shape without holes that can be made by selecting some of the white squares on an infinite checkerboard and placing a "plus sign" centered on each selected square. (The arms of neighboring plus signs will overlap).
answered Jan 12 at 17:52
Henning MakholmHenning Makholm
240k17305542
$endgroup$
add a comment |
$begingroup$
I think the polygons you can make in this way are exactly:
A square
Any connected shape without holes that can be made by selecting some of the white squares on an infinite checkerboard and placing a "plus sign" centered on each selected square. (The arms of neighboring plus signs will overlap).
answered Jan 12 at 17:52
Henning MakholmHenning Makholm
240k17305542
$endgroup$
I think the polygons you can make in this way are exactly:
A square
Any connected shape without holes that can be made by selecting some of the white squares on an infinite checkerboard and placing a "plus sign" centered on each selected square. (The arms of neighboring plus signs will overlap).
answered Jan 12 at 17:52
Henning MakholmHenning Makholm
240k17305542
answered Jan 12 at 17:52
Henning MakholmHenning Makholm
240k17305542
answered Jan 12 at 17:52
Henning MakholmHenning Makholm
240k17305542
answered Jan 12 at 17:52
Henning MakholmHenning Makholm
240k17305542
240k17305542
add a comment |
add a comment |
$begingroup$
There are infinitely many of them. You can generate an infinite subset by building on a single square.
Start with the one square. Attach four more, congruent squares one on each side, getting your "plus sign". Note that this figure has four 270° corners located at the corners of the first square. Place another square play each of these concavoties, filling in the space around that point, then add four more squares on the outernost edges of the +sign you had. You now have a figure containing 20 sides and vertices, with eight of the vertices concave. Note that these concave vertices had been the 90° corners of the previous + sign.
You can keep going. At each stage put a square in each concave corner and then squares on the outer edges of the latest figure to get the next figure. After $n$ iterations there are $4(2n+1)$ sides, the same number of vertices, and $4n$ of these vertices having 270° angles.
As mentioned, this is only a subset of the possibilities. Others will likely post more.
answered Jan 12 at 17:46
Oscar LanziOscar Lanzi
12.7k12136
$endgroup$
$begingroup$
I don't think you can get all instances of $4(n+1)$: it is not possible to have $8$ sides. All multiples of $4$ from $12$ upwards can be realized by diagonal sequences of pluses, though.
$endgroup$
– Henning Makholm
Jan 14 at 0:32
add a comment |
$begingroup$
There are infinitely many of them. You can generate an infinite subset by building on a single square.
Start with the one square. Attach four more, congruent squares one on each side, getting your "plus sign". Note that this figure has four 270° corners located at the corners of the first square. Place another square play each of these concavoties, filling in the space around that point, then add four more squares on the outernost edges of the +sign you had. You now have a figure containing 20 sides and vertices, with eight of the vertices concave. Note that these concave vertices had been the 90° corners of the previous + sign.
You can keep going. At each stage put a square in each concave corner and then squares on the outer edges of the latest figure to get the next figure. After $n$ iterations there are $4(2n+1)$ sides, the same number of vertices, and $4n$ of these vertices having 270° angles.
As mentioned, this is only a subset of the possibilities. Others will likely post more.
answered Jan 12 at 17:46
Oscar LanziOscar Lanzi
12.7k12136
$endgroup$
$begingroup$
I don't think you can get all instances of $4(n+1)$: it is not possible to have $8$ sides. All multiples of $4$ from $12$ upwards can be realized by diagonal sequences of pluses, though.
$endgroup$
– Henning Makholm
Jan 14 at 0:32
add a comment |
$begingroup$
There are infinitely many of them. You can generate an infinite subset by building on a single square.
Start with the one square. Attach four more, congruent squares one on each side, getting your "plus sign". Note that this figure has four 270° corners located at the corners of the first square. Place another square play each of these concavoties, filling in the space around that point, then add four more squares on the outernost edges of the +sign you had. You now have a figure containing 20 sides and vertices, with eight of the vertices concave. Note that these concave vertices had been the 90° corners of the previous + sign.
You can keep going. At each stage put a square in each concave corner and then squares on the outer edges of the latest figure to get the next figure. After $n$ iterations there are $4(2n+1)$ sides, the same number of vertices, and $4n$ of these vertices having 270° angles.
As mentioned, this is only a subset of the possibilities. Others will likely post more.
answered Jan 12 at 17:46
Oscar LanziOscar Lanzi
12.7k12136
$endgroup$
There are infinitely many of them. You can generate an infinite subset by building on a single square.
Start with the one square. Attach four more, congruent squares one on each side, getting your "plus sign". Note that this figure has four 270° corners located at the corners of the first square. Place another square play each of these concavoties, filling in the space around that point, then add four more squares on the outernost edges of the +sign you had. You now have a figure containing 20 sides and vertices, with eight of the vertices concave. Note that these concave vertices had been the 90° corners of the previous + sign.
You can keep going. At each stage put a square in each concave corner and then squares on the outer edges of the latest figure to get the next figure. After $n$ iterations there are $4(2n+1)$ sides, the same number of vertices, and $4n$ of these vertices having 270° angles.
As mentioned, this is only a subset of the possibilities. Others will likely post more.
answered Jan 12 at 17:46
Oscar LanziOscar Lanzi
12.7k12136
edited Jan 14 at 0:57
answered Jan 12 at 17:46
Oscar LanziOscar Lanzi
12.7k12136
answered Jan 12 at 17:46
Oscar LanziOscar Lanzi
12.7k12136
answered Jan 12 at 17:46
Oscar LanziOscar Lanzi
12.7k12136
12.7k12136
$begingroup$
I don't think you can get all instances of $4(n+1)$: it is not possible to have $8$ sides. All multiples of $4$ from $12$ upwards can be realized by diagonal sequences of pluses, though.
$endgroup$
– Henning Makholm
Jan 14 at 0:32
add a comment |
$begingroup$
I don't think you can get all instances of $4(n+1)$: it is not possible to have $8$ sides. All multiples of $4$ from $12$ upwards can be realized by diagonal sequences of pluses, though.
$endgroup$
– Henning Makholm
Jan 14 at 0:32
$begingroup$
I don't think you can get all instances of $4(n+1)$: it is not possible to have $8$ sides. All multiples of $4$ from $12$ upwards can be realized by diagonal sequences of pluses, though.
$endgroup$
– Henning Makholm
Jan 14 at 0:32
$begingroup$
I don't think you can get all instances of $4(n+1)$: it is not possible to have $8$ sides. All multiples of $4$ from $12$ upwards can be realized by diagonal sequences of pluses, though.
$endgroup$
– Henning Makholm
Jan 14 at 0:32
add a comment |
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.
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3071149%2fgenerating-or-counting-the-sides-of-square-like-polygons-with-all-congruent%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
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
Required, but never shown
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
Required, but never shown
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
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
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
1
$begingroup$
Can vertices coincide? E.g. do you allow a polygon whose corners angles are 90-90-90-270-90-90-90-270? Or one where two convex corners touch?
$endgroup$
– Henning Makholm
Jan 12 at 17:33
1
$begingroup$
If I understand you correctly, these are a subset of the polyominoes. If you really want all the sides to be congruent, it will be a very small subset. I can think offhand of one with 9 sides and one with 12.
$endgroup$
– MJD
Jan 12 at 17:34
$begingroup$
@HenningMakholm I don't think it counts as a polygon if it self-intersects.
$endgroup$
– Frpzzd
Jan 12 at 17:41
$begingroup$
For "sides" read "squares". They have 20 and 24 sides respectively. There is also one with 13 squares and 20 sides.
$endgroup$
– MJD
Jan 12 at 17:41
$begingroup$
Thanks for an interesting and fun question!
$endgroup$
– timtfj
Jan 15 at 1:53