Mixing
Can all convex $3n$-iamonds be tiled by $3$-iamonds?
Clash Royale CLAN TAG#URR8PPP
up vote
8
down vote
favorite
Background
A polyiamond is a plane figure constructed by joining together equilateral triangles of the same size along their edges.
The number of convex polyiamonds is given by A096004.
Based on enumerating examples up to $n=8$, it looks plausible that all $A096004(3n)$ convex $3n$-iamonds can be tiled by the $3$-iamond (i.e. the triamond).
Question
If the conjecture is true, I'm curious to see a proof (or even some heuristics). If the conjecture isn't true, I'd be curious to see a counterexample.
(It's perhaps worth noting that not all convex $2n$-iamonds can be tiled by the $2$-iamond.)
combinatorics discrete-geometry polyomino
asked Jul 16 at 20:03
Peter Kagey
1,36761952
add a comment |Â
up vote
8
down vote
favorite
Background
A polyiamond is a plane figure constructed by joining together equilateral triangles of the same size along their edges.
The number of convex polyiamonds is given by A096004.
Based on enumerating examples up to $n=8$, it looks plausible that all $A096004(3n)$ convex $3n$-iamonds can be tiled by the $3$-iamond (i.e. the triamond).
Question
If the conjecture is true, I'm curious to see a proof (or even some heuristics). If the conjecture isn't true, I'd be curious to see a counterexample.
(It's perhaps worth noting that not all convex $2n$-iamonds can be tiled by the $2$-iamond.)
combinatorics discrete-geometry polyomino
asked Jul 16 at 20:03
Peter Kagey
1,36761952
Do you have a reference for a counterexample to the analogous statement about the $2-$iamond?
– saulspatz
Jul 16 at 20:33
Yes, the triangular $4$-iamond will do the trick.
– Peter Kagey
Jul 16 at 20:35
Indeed. I was trying to make an example like that for $3-$iamonds, without success. I thought looking at a smaller counter example might help, but no such luck. Good problem.
– saulspatz
Jul 16 at 20:38
add a comment |Â
up vote
8
down vote
favorite
up vote
8
down vote
favorite
Background
A polyiamond is a plane figure constructed by joining together equilateral triangles of the same size along their edges.
The number of convex polyiamonds is given by A096004.
Based on enumerating examples up to $n=8$, it looks plausible that all $A096004(3n)$ convex $3n$-iamonds can be tiled by the $3$-iamond (i.e. the triamond).
Question
If the conjecture is true, I'm curious to see a proof (or even some heuristics). If the conjecture isn't true, I'd be curious to see a counterexample.
(It's perhaps worth noting that not all convex $2n$-iamonds can be tiled by the $2$-iamond.)
combinatorics discrete-geometry polyomino
asked Jul 16 at 20:03
Peter Kagey
1,36761952
Background
A polyiamond is a plane figure constructed by joining together equilateral triangles of the same size along their edges.
The number of convex polyiamonds is given by A096004.
Based on enumerating examples up to $n=8$, it looks plausible that all $A096004(3n)$ convex $3n$-iamonds can be tiled by the $3$-iamond (i.e. the triamond).
Question
If the conjecture is true, I'm curious to see a proof (or even some heuristics). If the conjecture isn't true, I'd be curious to see a counterexample.
(It's perhaps worth noting that not all convex $2n$-iamonds can be tiled by the $2$-iamond.)
combinatorics discrete-geometry polyomino
asked Jul 16 at 20:03
Peter Kagey
1,36761952
asked Jul 16 at 20:03
Peter Kagey
1,36761952
asked Jul 16 at 20:03
Peter Kagey
1,36761952
asked Jul 16 at 20:03
Peter Kagey
1,36761952
1,36761952
Do you have a reference for a counterexample to the analogous statement about the $2-$iamond?
– saulspatz
Jul 16 at 20:33
Yes, the triangular $4$-iamond will do the trick.
– Peter Kagey
Jul 16 at 20:35
Indeed. I was trying to make an example like that for $3-$iamonds, without success. I thought looking at a smaller counter example might help, but no such luck. Good problem.
– saulspatz
Jul 16 at 20:38
add a comment |Â
Do you have a reference for a counterexample to the analogous statement about the $2-$iamond?
– saulspatz
Jul 16 at 20:33
Yes, the triangular $4$-iamond will do the trick.
– Peter Kagey
Jul 16 at 20:35
Indeed. I was trying to make an example like that for $3-$iamonds, without success. I thought looking at a smaller counter example might help, but no such luck. Good problem.
– saulspatz
Jul 16 at 20:38
Do you have a reference for a counterexample to the analogous statement about the $2-$iamond?
– saulspatz
Jul 16 at 20:33
Do you have a reference for a counterexample to the analogous statement about the $2-$iamond?
– saulspatz
Jul 16 at 20:33
Yes, the triangular $4$-iamond will do the trick.
– Peter Kagey
Jul 16 at 20:35
Yes, the triangular $4$-iamond will do the trick.
– Peter Kagey
Jul 16 at 20:35
Indeed. I was trying to make an example like that for $3-$iamonds, without success. I thought looking at a smaller counter example might help, but no such luck. Good problem.
– saulspatz
Jul 16 at 20:38
Indeed. I was trying to make an example like that for $3-$iamonds, without success. I thought looking at a smaller counter example might help, but no such luck. Good problem.
– saulspatz
Jul 16 at 20:38
add a comment |Â
2 Answers
2
active
oldest
votes
up vote
3
down vote
accepted
Suppose we have a smallest counterexample.
Every way we slice it edge-to-edge horizontally between the rows of triangles we must get two halves which are not $3k$-iamonds (since otherwise both halves are smaller and can be tiled).
A single row of $3k$ triangles is trivial to tile, so wlog the counterexample must have at least two rows and the number of triangles in the first one must not be divisible by $3$.
If the top row has $2m$ triangles,where $m neq 0 pmod3$, wlog it's
<-- m -->
*---*---*
/ / /
*---*---*
Then convexity requires that the right edge continue to the bottom, so we have a parallelogram, possibly with a triangle sliced off the bottom-left.
How many rows tall is the parallelogram? We've already said that it must be more than one. If it's two, $4m$ is also not divisible by $3$,
so we require $4m-1$ to be divisible by $3$ (i.e. $m equiv 1 pmod3$) and we chop off the bottom-left triangle. But then we can tile the
left column thus and then tile along the rows:
*---*---*---*---*
/AA/ / / /
*---*---*---*---*
A/ / / /
*---*---*---*
If the height $h$ is more than two, the left edge can be at most two long, because otherwise the first three rows are equal and we contradict the "smaller counterexample".
Two subcases: left edge is one long, or two long.
One long: the first row is $2m$, the second is $2m-1$, the next is $2m-3$, the $i$th is $2m-(2i-1)$ for $i > 1$. Since we have more than two rows, neither $2m$ nor $4m-1$ is divisible by $3$, so $m equiv 2 pmod3$.
- Triangles in three rows: $4m-1 + 2m-3 = 6m - 4$ is not divisible by $3$, so we have more than three rows
- Triangles in four rows: $6m-4 + 2m-5 = 8m - 9$ is not divisible by $3$, so we have more than four rows
And since in any three rows excluding the first the number of triangles is divisible by $3$ (because $2m-(2i-1) + 2m-(2(i+1)-1) + 2m-(2(i+2)-1) = 6m-6i-3$), there is no height which gives a $3k$-iamond.
Left edge is two long: the first row is $2m$, the second is $2m$, the third is $2m-1$, the next is $2m-3$, etc.
- The first three rows contain $6m-1$ triangles, which is $2 pmod 3$
- The first four rows contain $8m-4$ triangles; $m=1 pmod 3 implies Delta = 1 pmod 3$; $m=2 pmod 3 implies Delta = 0 pmod 3$, so if $m=2$ then $h=4$
- The first five rows contain $10m-9$ triangles; $m=1 pmod 3 => Delta = 1 pmod 3$
By a similar argument to the previous subcase, this means there is no $h$ for which $m = 1 pmod 3$ gives a $3k$-iamond.
Therefore we have $m = 2 pmod 3$, $h = 4$. We can tile the first two columns as shown, and then tile along the rows. (Equivalently, we can slice into two convex $3k$-iamonds, contradicting minimality).
*---*---*---*---*---*
/DA/AA/ / / /
*---*---*---*---*---*
/DD/BB/ / / /
*---*---*---*---*---*
C/CB/ / / /
*---*---*---*---*
C/ / / /
*---*---*---*
If the top slice has $2m+1$ triangles, they can point "down" or "up":
*---*---*---*---* *---*---*---*
/ / / / vs / / / /
*---*---*---* *---*---*---*---*
In the case where they point "down", the convex $3k$-iamond must be a truncated triangle.
If it has two rows, then $2m+1 + 2m-1 = 4m$ must be divisible by $3$, so $m$ is divisible by $3$. (NB we could consider this case already covered, since there's an edge with an even number of triangles). Tile the two ends like this and then tile along the rows.
*---*---*---*---*---*---*---*
A/A / / / / /BB/
*---*---*---*---*---*---*
A/ / / / / B/
*---*---*---*---*---*
Otherwise $2m+1 + 2m-1 + 2m-3 = 6m-3$ is divisible by $3$, so it has three rows. The triangle on the left can be sliced off, and the rest tiled in 6-iamond columns.
*---*---*---*---*---*---*
A/AA/BB/ / / /
*---*---*---*---*---*
C/CB/ / / /
*---*---*---*---*
C/ / / /
*---*---*---*
That leaves the case where they point "up", and in fact every edge must have an odd number of triangles pointing "up" because otherwise one of the previously covered cases applies to a symmetry of the 3k-iamond.
Since all of the corners are $120^circ$, we're looking at hexagons and can characterise them by the lengths of three consecutive edges: $l, m, n$
with corresponding number of triangles $2l+1, 2m+1, 2n+1$. We already know that none of these is divisible by $3$ (for then we could slice into smaller $3k$-iamonds), so none of $l,m,n$ is $1 pmod 3$. Therefore they're all at least $2$, and we have at least four rows.
The first two rows have $2m+1 + 2m+3 = 4m+4 equiv m+1 pmod 3$, and similarly under rotation to put the others at the top, so to avoid being able to slice off two rows none of $l,m,n$ is $2 pmod 3$.
Therefore they're all $0 pmod 3$. Then the first three rows have $2m+1 + 2m+3 + 2m+5 = 6m+9 equiv 0 pmod 3$ triangles and can be sliced off, giving a contradiction.
All cases have been eliminated, and so there is no smallest counterexample.
answered Jul 17 at 15:33
Peter Taylor
7,78512239
add a comment |Â
up vote
1
down vote
Here is another argument to show that indeed, a convex polyiamond with $3n$ cells is tileable by 3-bars.
Any convex polyiamond is really a "hexagon" with side lengths $a$, $b$, $c$, $d$, $e$ and $f$, some of which may be 0 (so it may in fact be a pentagon, quadrangle, or triangle). This is because any convex polygon is the intersection of half-planes, and there are only 6 orientations of half-planes in a triangular grid.
Here is an example with $b = 0$:
- If both sides of any pair of opposite sides have length 3 or more, we can cut off a tileable strip (where each row has $6$ triangles, and is tileable by two bars), and get a smaller convex "hexagon".
- If both sides of any pair of sides with another side in between (for example $a$ and $c$) have length 3 or more, we can cut of a tileable "trapezium" (possibly with one side 0 to give a triangle), and get a smaller convex "hexagon".
A trapezium with 3 rows is tileable as shown in this figure (Peter Taylor also uses this idea in his analysis):
Suppose we have a "hexagon" that does not satisfy one of the two conditions above. Then at last 4 adjacent sides must have length 2 or shorter. But then, the figure must lie within a hexagon with all sides 2, and so the maximum area of such a figure is $24 = 3times 8$, and all such figures is tileable by enumeration (according to OP), and so any convex polyiamond can be partitioned into a set of strips, trapeziums, and a polyiamond with area 24 or less, all of which are tileable, and hence, so is the original polyiamond.
answered Jul 21 at 19:05
Herman Tulleken
786417
add a comment |Â
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
3
down vote
accepted
Suppose we have a smallest counterexample.
Every way we slice it edge-to-edge horizontally between the rows of triangles we must get two halves which are not $3k$-iamonds (since otherwise both halves are smaller and can be tiled).
A single row of $3k$ triangles is trivial to tile, so wlog the counterexample must have at least two rows and the number of triangles in the first one must not be divisible by $3$.
If the top row has $2m$ triangles,where $m neq 0 pmod3$, wlog it's
<-- m -->
*---*---*
/ / /
*---*---*
Then convexity requires that the right edge continue to the bottom, so we have a parallelogram, possibly with a triangle sliced off the bottom-left.
How many rows tall is the parallelogram? We've already said that it must be more than one. If it's two, $4m$ is also not divisible by $3$,
so we require $4m-1$ to be divisible by $3$ (i.e. $m equiv 1 pmod3$) and we chop off the bottom-left triangle. But then we can tile the
left column thus and then tile along the rows:
*---*---*---*---*
/AA/ / / /
*---*---*---*---*
A/ / / /
*---*---*---*
If the height $h$ is more than two, the left edge can be at most two long, because otherwise the first three rows are equal and we contradict the "smaller counterexample".
Two subcases: left edge is one long, or two long.
One long: the first row is $2m$, the second is $2m-1$, the next is $2m-3$, the $i$th is $2m-(2i-1)$ for $i > 1$. Since we have more than two rows, neither $2m$ nor $4m-1$ is divisible by $3$, so $m equiv 2 pmod3$.
- Triangles in three rows: $4m-1 + 2m-3 = 6m - 4$ is not divisible by $3$, so we have more than three rows
- Triangles in four rows: $6m-4 + 2m-5 = 8m - 9$ is not divisible by $3$, so we have more than four rows
And since in any three rows excluding the first the number of triangles is divisible by $3$ (because $2m-(2i-1) + 2m-(2(i+1)-1) + 2m-(2(i+2)-1) = 6m-6i-3$), there is no height which gives a $3k$-iamond.
Left edge is two long: the first row is $2m$, the second is $2m$, the third is $2m-1$, the next is $2m-3$, etc.
- The first three rows contain $6m-1$ triangles, which is $2 pmod 3$
- The first four rows contain $8m-4$ triangles; $m=1 pmod 3 implies Delta = 1 pmod 3$; $m=2 pmod 3 implies Delta = 0 pmod 3$, so if $m=2$ then $h=4$
- The first five rows contain $10m-9$ triangles; $m=1 pmod 3 => Delta = 1 pmod 3$
By a similar argument to the previous subcase, this means there is no $h$ for which $m = 1 pmod 3$ gives a $3k$-iamond.
Therefore we have $m = 2 pmod 3$, $h = 4$. We can tile the first two columns as shown, and then tile along the rows. (Equivalently, we can slice into two convex $3k$-iamonds, contradicting minimality).
*---*---*---*---*---*
/DA/AA/ / / /
*---*---*---*---*---*
/DD/BB/ / / /
*---*---*---*---*---*
C/CB/ / / /
*---*---*---*---*
C/ / / /
*---*---*---*
If the top slice has $2m+1$ triangles, they can point "down" or "up":
*---*---*---*---* *---*---*---*
/ / / / vs / / / /
*---*---*---* *---*---*---*---*
In the case where they point "down", the convex $3k$-iamond must be a truncated triangle.
If it has two rows, then $2m+1 + 2m-1 = 4m$ must be divisible by $3$, so $m$ is divisible by $3$. (NB we could consider this case already covered, since there's an edge with an even number of triangles). Tile the two ends like this and then tile along the rows.
*---*---*---*---*---*---*---*
A/A / / / / /BB/
*---*---*---*---*---*---*
A/ / / / / B/
*---*---*---*---*---*
Otherwise $2m+1 + 2m-1 + 2m-3 = 6m-3$ is divisible by $3$, so it has three rows. The triangle on the left can be sliced off, and the rest tiled in 6-iamond columns.
*---*---*---*---*---*---*
A/AA/BB/ / / /
*---*---*---*---*---*
C/CB/ / / /
*---*---*---*---*
C/ / / /
*---*---*---*
That leaves the case where they point "up", and in fact every edge must have an odd number of triangles pointing "up" because otherwise one of the previously covered cases applies to a symmetry of the 3k-iamond.
Since all of the corners are $120^circ$, we're looking at hexagons and can characterise them by the lengths of three consecutive edges: $l, m, n$
with corresponding number of triangles $2l+1, 2m+1, 2n+1$. We already know that none of these is divisible by $3$ (for then we could slice into smaller $3k$-iamonds), so none of $l,m,n$ is $1 pmod 3$. Therefore they're all at least $2$, and we have at least four rows.
The first two rows have $2m+1 + 2m+3 = 4m+4 equiv m+1 pmod 3$, and similarly under rotation to put the others at the top, so to avoid being able to slice off two rows none of $l,m,n$ is $2 pmod 3$.
Therefore they're all $0 pmod 3$. Then the first three rows have $2m+1 + 2m+3 + 2m+5 = 6m+9 equiv 0 pmod 3$ triangles and can be sliced off, giving a contradiction.
All cases have been eliminated, and so there is no smallest counterexample.
answered Jul 17 at 15:33
Peter Taylor
7,78512239
add a comment |Â
up vote
3
down vote
accepted
Suppose we have a smallest counterexample.
Every way we slice it edge-to-edge horizontally between the rows of triangles we must get two halves which are not $3k$-iamonds (since otherwise both halves are smaller and can be tiled).
A single row of $3k$ triangles is trivial to tile, so wlog the counterexample must have at least two rows and the number of triangles in the first one must not be divisible by $3$.
If the top row has $2m$ triangles,where $m neq 0 pmod3$, wlog it's
<-- m -->
*---*---*
/ / /
*---*---*
Then convexity requires that the right edge continue to the bottom, so we have a parallelogram, possibly with a triangle sliced off the bottom-left.
How many rows tall is the parallelogram? We've already said that it must be more than one. If it's two, $4m$ is also not divisible by $3$,
so we require $4m-1$ to be divisible by $3$ (i.e. $m equiv 1 pmod3$) and we chop off the bottom-left triangle. But then we can tile the
left column thus and then tile along the rows:
*---*---*---*---*
/AA/ / / /
*---*---*---*---*
A/ / / /
*---*---*---*
If the height $h$ is more than two, the left edge can be at most two long, because otherwise the first three rows are equal and we contradict the "smaller counterexample".
Two subcases: left edge is one long, or two long.
One long: the first row is $2m$, the second is $2m-1$, the next is $2m-3$, the $i$th is $2m-(2i-1)$ for $i > 1$. Since we have more than two rows, neither $2m$ nor $4m-1$ is divisible by $3$, so $m equiv 2 pmod3$.
- Triangles in three rows: $4m-1 + 2m-3 = 6m - 4$ is not divisible by $3$, so we have more than three rows
- Triangles in four rows: $6m-4 + 2m-5 = 8m - 9$ is not divisible by $3$, so we have more than four rows
And since in any three rows excluding the first the number of triangles is divisible by $3$ (because $2m-(2i-1) + 2m-(2(i+1)-1) + 2m-(2(i+2)-1) = 6m-6i-3$), there is no height which gives a $3k$-iamond.
Left edge is two long: the first row is $2m$, the second is $2m$, the third is $2m-1$, the next is $2m-3$, etc.
- The first three rows contain $6m-1$ triangles, which is $2 pmod 3$
- The first four rows contain $8m-4$ triangles; $m=1 pmod 3 implies Delta = 1 pmod 3$; $m=2 pmod 3 implies Delta = 0 pmod 3$, so if $m=2$ then $h=4$
- The first five rows contain $10m-9$ triangles; $m=1 pmod 3 => Delta = 1 pmod 3$
By a similar argument to the previous subcase, this means there is no $h$ for which $m = 1 pmod 3$ gives a $3k$-iamond.
Therefore we have $m = 2 pmod 3$, $h = 4$. We can tile the first two columns as shown, and then tile along the rows. (Equivalently, we can slice into two convex $3k$-iamonds, contradicting minimality).
*---*---*---*---*---*
/DA/AA/ / / /
*---*---*---*---*---*
/DD/BB/ / / /
*---*---*---*---*---*
C/CB/ / / /
*---*---*---*---*
C/ / / /
*---*---*---*
If the top slice has $2m+1$ triangles, they can point "down" or "up":
*---*---*---*---* *---*---*---*
/ / / / vs / / / /
*---*---*---* *---*---*---*---*
In the case where they point "down", the convex $3k$-iamond must be a truncated triangle.
If it has two rows, then $2m+1 + 2m-1 = 4m$ must be divisible by $3$, so $m$ is divisible by $3$. (NB we could consider this case already covered, since there's an edge with an even number of triangles). Tile the two ends like this and then tile along the rows.
*---*---*---*---*---*---*---*
A/A / / / / /BB/
*---*---*---*---*---*---*
A/ / / / / B/
*---*---*---*---*---*
Otherwise $2m+1 + 2m-1 + 2m-3 = 6m-3$ is divisible by $3$, so it has three rows. The triangle on the left can be sliced off, and the rest tiled in 6-iamond columns.
*---*---*---*---*---*---*
A/AA/BB/ / / /
*---*---*---*---*---*
C/CB/ / / /
*---*---*---*---*
C/ / / /
*---*---*---*
That leaves the case where they point "up", and in fact every edge must have an odd number of triangles pointing "up" because otherwise one of the previously covered cases applies to a symmetry of the 3k-iamond.
Since all of the corners are $120^circ$, we're looking at hexagons and can characterise them by the lengths of three consecutive edges: $l, m, n$
with corresponding number of triangles $2l+1, 2m+1, 2n+1$. We already know that none of these is divisible by $3$ (for then we could slice into smaller $3k$-iamonds), so none of $l,m,n$ is $1 pmod 3$. Therefore they're all at least $2$, and we have at least four rows.
The first two rows have $2m+1 + 2m+3 = 4m+4 equiv m+1 pmod 3$, and similarly under rotation to put the others at the top, so to avoid being able to slice off two rows none of $l,m,n$ is $2 pmod 3$.
Therefore they're all $0 pmod 3$. Then the first three rows have $2m+1 + 2m+3 + 2m+5 = 6m+9 equiv 0 pmod 3$ triangles and can be sliced off, giving a contradiction.
All cases have been eliminated, and so there is no smallest counterexample.
answered Jul 17 at 15:33
Peter Taylor
7,78512239
add a comment |Â
up vote
3
down vote
accepted
up vote
3
down vote
accepted
Suppose we have a smallest counterexample.
Every way we slice it edge-to-edge horizontally between the rows of triangles we must get two halves which are not $3k$-iamonds (since otherwise both halves are smaller and can be tiled).
A single row of $3k$ triangles is trivial to tile, so wlog the counterexample must have at least two rows and the number of triangles in the first one must not be divisible by $3$.
If the top row has $2m$ triangles,where $m neq 0 pmod3$, wlog it's
<-- m -->
*---*---*
/ / /
*---*---*
Then convexity requires that the right edge continue to the bottom, so we have a parallelogram, possibly with a triangle sliced off the bottom-left.
How many rows tall is the parallelogram? We've already said that it must be more than one. If it's two, $4m$ is also not divisible by $3$,
so we require $4m-1$ to be divisible by $3$ (i.e. $m equiv 1 pmod3$) and we chop off the bottom-left triangle. But then we can tile the
left column thus and then tile along the rows:
*---*---*---*---*
/AA/ / / /
*---*---*---*---*
A/ / / /
*---*---*---*
If the height $h$ is more than two, the left edge can be at most two long, because otherwise the first three rows are equal and we contradict the "smaller counterexample".
Two subcases: left edge is one long, or two long.
One long: the first row is $2m$, the second is $2m-1$, the next is $2m-3$, the $i$th is $2m-(2i-1)$ for $i > 1$. Since we have more than two rows, neither $2m$ nor $4m-1$ is divisible by $3$, so $m equiv 2 pmod3$.
- Triangles in three rows: $4m-1 + 2m-3 = 6m - 4$ is not divisible by $3$, so we have more than three rows
- Triangles in four rows: $6m-4 + 2m-5 = 8m - 9$ is not divisible by $3$, so we have more than four rows
And since in any three rows excluding the first the number of triangles is divisible by $3$ (because $2m-(2i-1) + 2m-(2(i+1)-1) + 2m-(2(i+2)-1) = 6m-6i-3$), there is no height which gives a $3k$-iamond.
Left edge is two long: the first row is $2m$, the second is $2m$, the third is $2m-1$, the next is $2m-3$, etc.
- The first three rows contain $6m-1$ triangles, which is $2 pmod 3$
- The first four rows contain $8m-4$ triangles; $m=1 pmod 3 implies Delta = 1 pmod 3$; $m=2 pmod 3 implies Delta = 0 pmod 3$, so if $m=2$ then $h=4$
- The first five rows contain $10m-9$ triangles; $m=1 pmod 3 => Delta = 1 pmod 3$
By a similar argument to the previous subcase, this means there is no $h$ for which $m = 1 pmod 3$ gives a $3k$-iamond.
Therefore we have $m = 2 pmod 3$, $h = 4$. We can tile the first two columns as shown, and then tile along the rows. (Equivalently, we can slice into two convex $3k$-iamonds, contradicting minimality).
*---*---*---*---*---*
/DA/AA/ / / /
*---*---*---*---*---*
/DD/BB/ / / /
*---*---*---*---*---*
C/CB/ / / /
*---*---*---*---*
C/ / / /
*---*---*---*
If the top slice has $2m+1$ triangles, they can point "down" or "up":
*---*---*---*---* *---*---*---*
/ / / / vs / / / /
*---*---*---* *---*---*---*---*
In the case where they point "down", the convex $3k$-iamond must be a truncated triangle.
If it has two rows, then $2m+1 + 2m-1 = 4m$ must be divisible by $3$, so $m$ is divisible by $3$. (NB we could consider this case already covered, since there's an edge with an even number of triangles). Tile the two ends like this and then tile along the rows.
*---*---*---*---*---*---*---*
A/A / / / / /BB/
*---*---*---*---*---*---*
A/ / / / / B/
*---*---*---*---*---*
Otherwise $2m+1 + 2m-1 + 2m-3 = 6m-3$ is divisible by $3$, so it has three rows. The triangle on the left can be sliced off, and the rest tiled in 6-iamond columns.
*---*---*---*---*---*---*
A/AA/BB/ / / /
*---*---*---*---*---*
C/CB/ / / /
*---*---*---*---*
C/ / / /
*---*---*---*
That leaves the case where they point "up", and in fact every edge must have an odd number of triangles pointing "up" because otherwise one of the previously covered cases applies to a symmetry of the 3k-iamond.
Since all of the corners are $120^circ$, we're looking at hexagons and can characterise them by the lengths of three consecutive edges: $l, m, n$
with corresponding number of triangles $2l+1, 2m+1, 2n+1$. We already know that none of these is divisible by $3$ (for then we could slice into smaller $3k$-iamonds), so none of $l,m,n$ is $1 pmod 3$. Therefore they're all at least $2$, and we have at least four rows.
The first two rows have $2m+1 + 2m+3 = 4m+4 equiv m+1 pmod 3$, and similarly under rotation to put the others at the top, so to avoid being able to slice off two rows none of $l,m,n$ is $2 pmod 3$.
Therefore they're all $0 pmod 3$. Then the first three rows have $2m+1 + 2m+3 + 2m+5 = 6m+9 equiv 0 pmod 3$ triangles and can be sliced off, giving a contradiction.
All cases have been eliminated, and so there is no smallest counterexample.
answered Jul 17 at 15:33
Peter Taylor
7,78512239
Suppose we have a smallest counterexample.
Every way we slice it edge-to-edge horizontally between the rows of triangles we must get two halves which are not $3k$-iamonds (since otherwise both halves are smaller and can be tiled).
A single row of $3k$ triangles is trivial to tile, so wlog the counterexample must have at least two rows and the number of triangles in the first one must not be divisible by $3$.
If the top row has $2m$ triangles,where $m neq 0 pmod3$, wlog it's
<-- m -->
*---*---*
/ / /
*---*---*
Then convexity requires that the right edge continue to the bottom, so we have a parallelogram, possibly with a triangle sliced off the bottom-left.
How many rows tall is the parallelogram? We've already said that it must be more than one. If it's two, $4m$ is also not divisible by $3$,
so we require $4m-1$ to be divisible by $3$ (i.e. $m equiv 1 pmod3$) and we chop off the bottom-left triangle. But then we can tile the
left column thus and then tile along the rows:
*---*---*---*---*
/AA/ / / /
*---*---*---*---*
A/ / / /
*---*---*---*
If the height $h$ is more than two, the left edge can be at most two long, because otherwise the first three rows are equal and we contradict the "smaller counterexample".
Two subcases: left edge is one long, or two long.
One long: the first row is $2m$, the second is $2m-1$, the next is $2m-3$, the $i$th is $2m-(2i-1)$ for $i > 1$. Since we have more than two rows, neither $2m$ nor $4m-1$ is divisible by $3$, so $m equiv 2 pmod3$.
- Triangles in three rows: $4m-1 + 2m-3 = 6m - 4$ is not divisible by $3$, so we have more than three rows
- Triangles in four rows: $6m-4 + 2m-5 = 8m - 9$ is not divisible by $3$, so we have more than four rows
And since in any three rows excluding the first the number of triangles is divisible by $3$ (because $2m-(2i-1) + 2m-(2(i+1)-1) + 2m-(2(i+2)-1) = 6m-6i-3$), there is no height which gives a $3k$-iamond.
Left edge is two long: the first row is $2m$, the second is $2m$, the third is $2m-1$, the next is $2m-3$, etc.
- The first three rows contain $6m-1$ triangles, which is $2 pmod 3$
- The first four rows contain $8m-4$ triangles; $m=1 pmod 3 implies Delta = 1 pmod 3$; $m=2 pmod 3 implies Delta = 0 pmod 3$, so if $m=2$ then $h=4$
- The first five rows contain $10m-9$ triangles; $m=1 pmod 3 => Delta = 1 pmod 3$
By a similar argument to the previous subcase, this means there is no $h$ for which $m = 1 pmod 3$ gives a $3k$-iamond.
Therefore we have $m = 2 pmod 3$, $h = 4$. We can tile the first two columns as shown, and then tile along the rows. (Equivalently, we can slice into two convex $3k$-iamonds, contradicting minimality).
*---*---*---*---*---*
/DA/AA/ / / /
*---*---*---*---*---*
/DD/BB/ / / /
*---*---*---*---*---*
C/CB/ / / /
*---*---*---*---*
C/ / / /
*---*---*---*
If the top slice has $2m+1$ triangles, they can point "down" or "up":
*---*---*---*---* *---*---*---*
/ / / / vs / / / /
*---*---*---* *---*---*---*---*
In the case where they point "down", the convex $3k$-iamond must be a truncated triangle.
If it has two rows, then $2m+1 + 2m-1 = 4m$ must be divisible by $3$, so $m$ is divisible by $3$. (NB we could consider this case already covered, since there's an edge with an even number of triangles). Tile the two ends like this and then tile along the rows.
*---*---*---*---*---*---*---*
A/A / / / / /BB/
*---*---*---*---*---*---*
A/ / / / / B/
*---*---*---*---*---*
Otherwise $2m+1 + 2m-1 + 2m-3 = 6m-3$ is divisible by $3$, so it has three rows. The triangle on the left can be sliced off, and the rest tiled in 6-iamond columns.
*---*---*---*---*---*---*
A/AA/BB/ / / /
*---*---*---*---*---*
C/CB/ / / /
*---*---*---*---*
C/ / / /
*---*---*---*
That leaves the case where they point "up", and in fact every edge must have an odd number of triangles pointing "up" because otherwise one of the previously covered cases applies to a symmetry of the 3k-iamond.
Since all of the corners are $120^circ$, we're looking at hexagons and can characterise them by the lengths of three consecutive edges: $l, m, n$
with corresponding number of triangles $2l+1, 2m+1, 2n+1$. We already know that none of these is divisible by $3$ (for then we could slice into smaller $3k$-iamonds), so none of $l,m,n$ is $1 pmod 3$. Therefore they're all at least $2$, and we have at least four rows.
The first two rows have $2m+1 + 2m+3 = 4m+4 equiv m+1 pmod 3$, and similarly under rotation to put the others at the top, so to avoid being able to slice off two rows none of $l,m,n$ is $2 pmod 3$.
Therefore they're all $0 pmod 3$. Then the first three rows have $2m+1 + 2m+3 + 2m+5 = 6m+9 equiv 0 pmod 3$ triangles and can be sliced off, giving a contradiction.
All cases have been eliminated, and so there is no smallest counterexample.
answered Jul 17 at 15:33
Peter Taylor
7,78512239
edited Jul 17 at 15:39
answered Jul 17 at 15:33
Peter Taylor
7,78512239
answered Jul 17 at 15:33
Peter Taylor
7,78512239
answered Jul 17 at 15:33
Peter Taylor
7,78512239
7,78512239
add a comment |Â
add a comment |Â
up vote
1
down vote
Here is another argument to show that indeed, a convex polyiamond with $3n$ cells is tileable by 3-bars.
Any convex polyiamond is really a "hexagon" with side lengths $a$, $b$, $c$, $d$, $e$ and $f$, some of which may be 0 (so it may in fact be a pentagon, quadrangle, or triangle). This is because any convex polygon is the intersection of half-planes, and there are only 6 orientations of half-planes in a triangular grid.
Here is an example with $b = 0$:
- If both sides of any pair of opposite sides have length 3 or more, we can cut off a tileable strip (where each row has $6$ triangles, and is tileable by two bars), and get a smaller convex "hexagon".
- If both sides of any pair of sides with another side in between (for example $a$ and $c$) have length 3 or more, we can cut of a tileable "trapezium" (possibly with one side 0 to give a triangle), and get a smaller convex "hexagon".
A trapezium with 3 rows is tileable as shown in this figure (Peter Taylor also uses this idea in his analysis):
Suppose we have a "hexagon" that does not satisfy one of the two conditions above. Then at last 4 adjacent sides must have length 2 or shorter. But then, the figure must lie within a hexagon with all sides 2, and so the maximum area of such a figure is $24 = 3times 8$, and all such figures is tileable by enumeration (according to OP), and so any convex polyiamond can be partitioned into a set of strips, trapeziums, and a polyiamond with area 24 or less, all of which are tileable, and hence, so is the original polyiamond.
answered Jul 21 at 19:05
Herman Tulleken
786417
add a comment |Â
up vote
1
down vote
Here is another argument to show that indeed, a convex polyiamond with $3n$ cells is tileable by 3-bars.
Any convex polyiamond is really a "hexagon" with side lengths $a$, $b$, $c$, $d$, $e$ and $f$, some of which may be 0 (so it may in fact be a pentagon, quadrangle, or triangle). This is because any convex polygon is the intersection of half-planes, and there are only 6 orientations of half-planes in a triangular grid.
Here is an example with $b = 0$:
- If both sides of any pair of opposite sides have length 3 or more, we can cut off a tileable strip (where each row has $6$ triangles, and is tileable by two bars), and get a smaller convex "hexagon".
- If both sides of any pair of sides with another side in between (for example $a$ and $c$) have length 3 or more, we can cut of a tileable "trapezium" (possibly with one side 0 to give a triangle), and get a smaller convex "hexagon".
A trapezium with 3 rows is tileable as shown in this figure (Peter Taylor also uses this idea in his analysis):
Suppose we have a "hexagon" that does not satisfy one of the two conditions above. Then at last 4 adjacent sides must have length 2 or shorter. But then, the figure must lie within a hexagon with all sides 2, and so the maximum area of such a figure is $24 = 3times 8$, and all such figures is tileable by enumeration (according to OP), and so any convex polyiamond can be partitioned into a set of strips, trapeziums, and a polyiamond with area 24 or less, all of which are tileable, and hence, so is the original polyiamond.
answered Jul 21 at 19:05
Herman Tulleken
786417
add a comment |Â
up vote
1
down vote
up vote
1
down vote
Here is another argument to show that indeed, a convex polyiamond with $3n$ cells is tileable by 3-bars.
Any convex polyiamond is really a "hexagon" with side lengths $a$, $b$, $c$, $d$, $e$ and $f$, some of which may be 0 (so it may in fact be a pentagon, quadrangle, or triangle). This is because any convex polygon is the intersection of half-planes, and there are only 6 orientations of half-planes in a triangular grid.
Here is an example with $b = 0$:
- If both sides of any pair of opposite sides have length 3 or more, we can cut off a tileable strip (where each row has $6$ triangles, and is tileable by two bars), and get a smaller convex "hexagon".
- If both sides of any pair of sides with another side in between (for example $a$ and $c$) have length 3 or more, we can cut of a tileable "trapezium" (possibly with one side 0 to give a triangle), and get a smaller convex "hexagon".
A trapezium with 3 rows is tileable as shown in this figure (Peter Taylor also uses this idea in his analysis):
Suppose we have a "hexagon" that does not satisfy one of the two conditions above. Then at last 4 adjacent sides must have length 2 or shorter. But then, the figure must lie within a hexagon with all sides 2, and so the maximum area of such a figure is $24 = 3times 8$, and all such figures is tileable by enumeration (according to OP), and so any convex polyiamond can be partitioned into a set of strips, trapeziums, and a polyiamond with area 24 or less, all of which are tileable, and hence, so is the original polyiamond.
answered Jul 21 at 19:05
Herman Tulleken
786417
Here is another argument to show that indeed, a convex polyiamond with $3n$ cells is tileable by 3-bars.
Any convex polyiamond is really a "hexagon" with side lengths $a$, $b$, $c$, $d$, $e$ and $f$, some of which may be 0 (so it may in fact be a pentagon, quadrangle, or triangle). This is because any convex polygon is the intersection of half-planes, and there are only 6 orientations of half-planes in a triangular grid.
Here is an example with $b = 0$:
- If both sides of any pair of opposite sides have length 3 or more, we can cut off a tileable strip (where each row has $6$ triangles, and is tileable by two bars), and get a smaller convex "hexagon".
- If both sides of any pair of sides with another side in between (for example $a$ and $c$) have length 3 or more, we can cut of a tileable "trapezium" (possibly with one side 0 to give a triangle), and get a smaller convex "hexagon".
A trapezium with 3 rows is tileable as shown in this figure (Peter Taylor also uses this idea in his analysis):
Suppose we have a "hexagon" that does not satisfy one of the two conditions above. Then at last 4 adjacent sides must have length 2 or shorter. But then, the figure must lie within a hexagon with all sides 2, and so the maximum area of such a figure is $24 = 3times 8$, and all such figures is tileable by enumeration (according to OP), and so any convex polyiamond can be partitioned into a set of strips, trapeziums, and a polyiamond with area 24 or less, all of which are tileable, and hence, so is the original polyiamond.
answered Jul 21 at 19:05
Herman Tulleken
786417
edited Jul 21 at 19:24
answered Jul 21 at 19:05
Herman Tulleken
786417
answered Jul 21 at 19:05
Herman Tulleken
786417
answered Jul 21 at 19:05
Herman Tulleken
786417
786417
add a comment |Â
add a comment |Â
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
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2853800%2fcan-all-convex-3n-iamonds-be-tiled-by-3-iamonds%23new-answer', 'question_page');
);
Post as a guest
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
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
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
Do you have a reference for a counterexample to the analogous statement about the $2-$iamond?
– saulspatz
Jul 16 at 20:33
Yes, the triangular $4$-iamond will do the trick.
– Peter Kagey
Jul 16 at 20:35
Indeed. I was trying to make an example like that for $3-$iamonds, without success. I thought looking at a smaller counter example might help, but no such luck. Good problem.
– saulspatz
Jul 16 at 20:38