Mixing
Is it always possible to fit these pieces in a square?
up vote
8
down vote
favorite
Consider all possible pairs of squares that can fit in a row of length $n$ where every square has a width of 1. If I have a large square of width $n$, can all such pairs of squares fit in the large square simultaneously?
It's hard to explain without an example so here is the case when $n=4$:
To the left are all the pairs of squares and to the right is a way for them to fit in the $n$ by $n$ square. Note that the pairs are not allowed to be moved horizontally but can be moved vertically.
It becomes a little harder but still possible when $n=5$:
What I'm interested in is the general case. Is it possible to fit all pairs in the square for any $n$?
recreational-mathematics
edited 2 days ago
Jens
3,5672828
asked 2 days ago
Pazzaz
435
New contributor
Pazzaz is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
|
show 3 more comments
up vote
8
down vote
favorite
Consider all possible pairs of squares that can fit in a row of length $n$ where every square has a width of 1. If I have a large square of width $n$, can all such pairs of squares fit in the large square simultaneously?
It's hard to explain without an example so here is the case when $n=4$:
To the left are all the pairs of squares and to the right is a way for them to fit in the $n$ by $n$ square. Note that the pairs are not allowed to be moved horizontally but can be moved vertically.
It becomes a little harder but still possible when $n=5$:
What I'm interested in is the general case. Is it possible to fit all pairs in the square for any $n$?
recreational-mathematics
edited 2 days ago
Jens
3,5672828
asked 2 days ago
Pazzaz
435
New contributor
Pazzaz is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
What does "all possible pieces (disconnected or connected) of width 2 and height of 1 that could fit in the square" mean? Can you show us how to generate the pieces for a given square?
– John Douma
2 days ago
@JohnDouma Well a piece here simply consists of choosing two squares in a single row of length n. So the total number of pieces will be (n choose 2).
– Pazzaz
2 days ago
1
I think you have to specify the problem more accurately. A triangle can have width $2$ and height $1$, for example, and that seems to be different from what you mean (and that is without thinking about figures which are not convex). I think you mean figures constructed of two $1times 1$ squares in a particular kind of configuration (as in your comment). And these sub-figures need not be connected. I do think your intended question is interesting, and worth asking, but the way you have asked it is misleading.
– Mark Bennet
2 days ago
@MarkBennet I agree, I did leave out some important parts. I've edited the question some, it should be more clear now.
– Pazzaz
2 days ago
Well, if possible, there will always be $n^2-2binom n2=n$ leftover spaces.
– YiFan
2 days ago
|
show 3 more comments
up vote
8
down vote
favorite
up vote
8
down vote
favorite
Consider all possible pairs of squares that can fit in a row of length $n$ where every square has a width of 1. If I have a large square of width $n$, can all such pairs of squares fit in the large square simultaneously?
It's hard to explain without an example so here is the case when $n=4$:
To the left are all the pairs of squares and to the right is a way for them to fit in the $n$ by $n$ square. Note that the pairs are not allowed to be moved horizontally but can be moved vertically.
It becomes a little harder but still possible when $n=5$:
What I'm interested in is the general case. Is it possible to fit all pairs in the square for any $n$?
recreational-mathematics
edited 2 days ago
Jens
3,5672828
asked 2 days ago
Pazzaz
435
New contributor
Pazzaz is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
Consider all possible pairs of squares that can fit in a row of length $n$ where every square has a width of 1. If I have a large square of width $n$, can all such pairs of squares fit in the large square simultaneously?
It's hard to explain without an example so here is the case when $n=4$:
To the left are all the pairs of squares and to the right is a way for them to fit in the $n$ by $n$ square. Note that the pairs are not allowed to be moved horizontally but can be moved vertically.
It becomes a little harder but still possible when $n=5$:
What I'm interested in is the general case. Is it possible to fit all pairs in the square for any $n$?
recreational-mathematics
recreational-mathematics
edited 2 days ago
Jens
3,5672828
asked 2 days ago
Pazzaz
435
New contributor
Pazzaz is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited 2 days ago
Jens
3,5672828
asked 2 days ago
Pazzaz
435
New contributor
Pazzaz is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited 2 days ago
Jens
3,5672828
edited 2 days ago
Jens
3,5672828
edited 2 days ago
Jens
3,5672828
3,5672828
asked 2 days ago
Pazzaz
435
New contributor
Pazzaz is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 2 days ago
Pazzaz
435
asked 2 days ago
Pazzaz
435
435
New contributor
Pazzaz is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
Pazzaz is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
Pazzaz is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
What does "all possible pieces (disconnected or connected) of width 2 and height of 1 that could fit in the square" mean? Can you show us how to generate the pieces for a given square?
– John Douma
2 days ago
@JohnDouma Well a piece here simply consists of choosing two squares in a single row of length n. So the total number of pieces will be (n choose 2).
– Pazzaz
2 days ago
1
I think you have to specify the problem more accurately. A triangle can have width $2$ and height $1$, for example, and that seems to be different from what you mean (and that is without thinking about figures which are not convex). I think you mean figures constructed of two $1times 1$ squares in a particular kind of configuration (as in your comment). And these sub-figures need not be connected. I do think your intended question is interesting, and worth asking, but the way you have asked it is misleading.
– Mark Bennet
2 days ago
@MarkBennet I agree, I did leave out some important parts. I've edited the question some, it should be more clear now.
– Pazzaz
2 days ago
Well, if possible, there will always be $n^2-2binom n2=n$ leftover spaces.
– YiFan
2 days ago
|
show 3 more comments
What does "all possible pieces (disconnected or connected) of width 2 and height of 1 that could fit in the square" mean? Can you show us how to generate the pieces for a given square?
– John Douma
2 days ago
@JohnDouma Well a piece here simply consists of choosing two squares in a single row of length n. So the total number of pieces will be (n choose 2).
– Pazzaz
2 days ago
1
I think you have to specify the problem more accurately. A triangle can have width $2$ and height $1$, for example, and that seems to be different from what you mean (and that is without thinking about figures which are not convex). I think you mean figures constructed of two $1times 1$ squares in a particular kind of configuration (as in your comment). And these sub-figures need not be connected. I do think your intended question is interesting, and worth asking, but the way you have asked it is misleading.
– Mark Bennet
2 days ago
@MarkBennet I agree, I did leave out some important parts. I've edited the question some, it should be more clear now.
– Pazzaz
2 days ago
Well, if possible, there will always be $n^2-2binom n2=n$ leftover spaces.
– YiFan
2 days ago
What does "all possible pieces (disconnected or connected) of width 2 and height of 1 that could fit in the square" mean? Can you show us how to generate the pieces for a given square?
– John Douma
2 days ago
What does "all possible pieces (disconnected or connected) of width 2 and height of 1 that could fit in the square" mean? Can you show us how to generate the pieces for a given square?
– John Douma
2 days ago
@JohnDouma Well a piece here simply consists of choosing two squares in a single row of length n. So the total number of pieces will be (n choose 2).
– Pazzaz
2 days ago
@JohnDouma Well a piece here simply consists of choosing two squares in a single row of length n. So the total number of pieces will be (n choose 2).
– Pazzaz
2 days ago
1
1
I think you have to specify the problem more accurately. A triangle can have width $2$ and height $1$, for example, and that seems to be different from what you mean (and that is without thinking about figures which are not convex). I think you mean figures constructed of two $1times 1$ squares in a particular kind of configuration (as in your comment). And these sub-figures need not be connected. I do think your intended question is interesting, and worth asking, but the way you have asked it is misleading.
– Mark Bennet
2 days ago
I think you have to specify the problem more accurately. A triangle can have width $2$ and height $1$, for example, and that seems to be different from what you mean (and that is without thinking about figures which are not convex). I think you mean figures constructed of two $1times 1$ squares in a particular kind of configuration (as in your comment). And these sub-figures need not be connected. I do think your intended question is interesting, and worth asking, but the way you have asked it is misleading.
– Mark Bennet
2 days ago
@MarkBennet I agree, I did leave out some important parts. I've edited the question some, it should be more clear now.
– Pazzaz
2 days ago
@MarkBennet I agree, I did leave out some important parts. I've edited the question some, it should be more clear now.
– Pazzaz
2 days ago
Well, if possible, there will always be $n^2-2binom n2=n$ leftover spaces.
– YiFan
2 days ago
Well, if possible, there will always be $n^2-2binom n2=n$ leftover spaces.
– YiFan
2 days ago
|
show 3 more comments
2 Answers
2
active
oldest
votes
up vote
5
down vote
accepted
It is always possible, we can place the $binom{n}{2}$ pairs in a $n times n$ square when $n$ is odd and in a $(n-1) times n$ rectangle when $n$ is even.
This problem is equivalent to the edge coloring problem for complete graph $K_n$. Look at wiki for the geometric intuition underlying following construction.
Let $[n]$ be a short hand for ${ 0, ldots, n-1 }$.
Index the set of possible pairs by $(i,j) in [n]^2$ with $i < j$.
Label rows and columns of the large square using numbers from $[n]$.
When $n$ is odd, place the pair $(i,j)$ at row $k$ of the large square where $i + j equiv k pmod n$.
If two pairs $(i_1,j_1)$, $(i_2,j_2)$ on same row intersect, then
one of the following happens
$$i_1 = i_2 lor i_1 = j_2lor j_1 = i_2 lor j_1 = j_2$$
Since $i_1 + j_1 equiv i_2 + j_2 pmod n$, we find
$$(i_1,j_1) = (i_2,j_2) pmod n lor (i_1,j_1) = (j_2,i_2) pmod n$$
Since $i_1,i_2,j_1,j_2 in [n]$ and $i_1 < j_1$, $i_2 < j_2$, we can rule out the second case. From this, we can deduce distinct pairs on some row are disjoint. This generate
a desired packing of the $binom{n}{2}$ pairs into a $n times n$ square.
When $n$ is even, $n - 1$ is odd.
Place those pair $(i,j) in [n-1]^2$ into row $k$ where $i + j equiv k pmod {n-1}$.
Notice
- For each row $i in [n-1]$, the slot at column $2i pmod {n - 1}$ and $n-1$ is unused.
- For any column $j in [n-1]$, one and only slot at row $i in [n-1]$ is unused.
For those pair $(i,j) in [n]^2 setminus [n-1]^2$ with $i < j$, we have $j = n$.
We can place the pair on row $k$ where $2k = i pmod {n-1}$. This will fill all the unused slots in the first $n-1$ rows and generate a desired packing of the $binom{n}{2}$ pairs into a $(n-1) times n$ rectangle.
answered yesterday
achille hui
93.4k5127251
add a comment |
up vote
1
down vote
For 7×7, we have the following. X is an empty space, A through U are the 21 pairs of squares. For example, D D in the second row indicates that the {1,3} pair is used in that row, while the X in the seventh position means that spot is left empty.
A A B B C X C
D E D E F F X
G H X I H I G
J K K J X L L
X M N O O M N
P X Q R Q P R
S T U X S U T
.
answered 2 days ago
Oscar Lanzi
11.6k11935
1
It looks like for odd n, the empty spots are all in different columns. In other words, by rearranging the rows you can create a blank diagonal.
– Pazzaz
2 days ago
add a comment |
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
5
down vote
accepted
It is always possible, we can place the $binom{n}{2}$ pairs in a $n times n$ square when $n$ is odd and in a $(n-1) times n$ rectangle when $n$ is even.
This problem is equivalent to the edge coloring problem for complete graph $K_n$. Look at wiki for the geometric intuition underlying following construction.
Let $[n]$ be a short hand for ${ 0, ldots, n-1 }$.
Index the set of possible pairs by $(i,j) in [n]^2$ with $i < j$.
Label rows and columns of the large square using numbers from $[n]$.
When $n$ is odd, place the pair $(i,j)$ at row $k$ of the large square where $i + j equiv k pmod n$.
If two pairs $(i_1,j_1)$, $(i_2,j_2)$ on same row intersect, then
one of the following happens
$$i_1 = i_2 lor i_1 = j_2lor j_1 = i_2 lor j_1 = j_2$$
Since $i_1 + j_1 equiv i_2 + j_2 pmod n$, we find
$$(i_1,j_1) = (i_2,j_2) pmod n lor (i_1,j_1) = (j_2,i_2) pmod n$$
Since $i_1,i_2,j_1,j_2 in [n]$ and $i_1 < j_1$, $i_2 < j_2$, we can rule out the second case. From this, we can deduce distinct pairs on some row are disjoint. This generate
a desired packing of the $binom{n}{2}$ pairs into a $n times n$ square.
When $n$ is even, $n - 1$ is odd.
Place those pair $(i,j) in [n-1]^2$ into row $k$ where $i + j equiv k pmod {n-1}$.
Notice
- For each row $i in [n-1]$, the slot at column $2i pmod {n - 1}$ and $n-1$ is unused.
- For any column $j in [n-1]$, one and only slot at row $i in [n-1]$ is unused.
For those pair $(i,j) in [n]^2 setminus [n-1]^2$ with $i < j$, we have $j = n$.
We can place the pair on row $k$ where $2k = i pmod {n-1}$. This will fill all the unused slots in the first $n-1$ rows and generate a desired packing of the $binom{n}{2}$ pairs into a $(n-1) times n$ rectangle.
answered yesterday
achille hui
93.4k5127251
add a comment |
up vote
5
down vote
accepted
It is always possible, we can place the $binom{n}{2}$ pairs in a $n times n$ square when $n$ is odd and in a $(n-1) times n$ rectangle when $n$ is even.
This problem is equivalent to the edge coloring problem for complete graph $K_n$. Look at wiki for the geometric intuition underlying following construction.
Let $[n]$ be a short hand for ${ 0, ldots, n-1 }$.
Index the set of possible pairs by $(i,j) in [n]^2$ with $i < j$.
Label rows and columns of the large square using numbers from $[n]$.
When $n$ is odd, place the pair $(i,j)$ at row $k$ of the large square where $i + j equiv k pmod n$.
If two pairs $(i_1,j_1)$, $(i_2,j_2)$ on same row intersect, then
one of the following happens
$$i_1 = i_2 lor i_1 = j_2lor j_1 = i_2 lor j_1 = j_2$$
Since $i_1 + j_1 equiv i_2 + j_2 pmod n$, we find
$$(i_1,j_1) = (i_2,j_2) pmod n lor (i_1,j_1) = (j_2,i_2) pmod n$$
Since $i_1,i_2,j_1,j_2 in [n]$ and $i_1 < j_1$, $i_2 < j_2$, we can rule out the second case. From this, we can deduce distinct pairs on some row are disjoint. This generate
a desired packing of the $binom{n}{2}$ pairs into a $n times n$ square.
When $n$ is even, $n - 1$ is odd.
Place those pair $(i,j) in [n-1]^2$ into row $k$ where $i + j equiv k pmod {n-1}$.
Notice
- For each row $i in [n-1]$, the slot at column $2i pmod {n - 1}$ and $n-1$ is unused.
- For any column $j in [n-1]$, one and only slot at row $i in [n-1]$ is unused.
For those pair $(i,j) in [n]^2 setminus [n-1]^2$ with $i < j$, we have $j = n$.
We can place the pair on row $k$ where $2k = i pmod {n-1}$. This will fill all the unused slots in the first $n-1$ rows and generate a desired packing of the $binom{n}{2}$ pairs into a $(n-1) times n$ rectangle.
answered yesterday
achille hui
93.4k5127251
add a comment |
up vote
5
down vote
accepted
up vote
5
down vote
accepted
It is always possible, we can place the $binom{n}{2}$ pairs in a $n times n$ square when $n$ is odd and in a $(n-1) times n$ rectangle when $n$ is even.
This problem is equivalent to the edge coloring problem for complete graph $K_n$. Look at wiki for the geometric intuition underlying following construction.
Let $[n]$ be a short hand for ${ 0, ldots, n-1 }$.
Index the set of possible pairs by $(i,j) in [n]^2$ with $i < j$.
Label rows and columns of the large square using numbers from $[n]$.
When $n$ is odd, place the pair $(i,j)$ at row $k$ of the large square where $i + j equiv k pmod n$.
If two pairs $(i_1,j_1)$, $(i_2,j_2)$ on same row intersect, then
one of the following happens
$$i_1 = i_2 lor i_1 = j_2lor j_1 = i_2 lor j_1 = j_2$$
Since $i_1 + j_1 equiv i_2 + j_2 pmod n$, we find
$$(i_1,j_1) = (i_2,j_2) pmod n lor (i_1,j_1) = (j_2,i_2) pmod n$$
Since $i_1,i_2,j_1,j_2 in [n]$ and $i_1 < j_1$, $i_2 < j_2$, we can rule out the second case. From this, we can deduce distinct pairs on some row are disjoint. This generate
a desired packing of the $binom{n}{2}$ pairs into a $n times n$ square.
When $n$ is even, $n - 1$ is odd.
Place those pair $(i,j) in [n-1]^2$ into row $k$ where $i + j equiv k pmod {n-1}$.
Notice
- For each row $i in [n-1]$, the slot at column $2i pmod {n - 1}$ and $n-1$ is unused.
- For any column $j in [n-1]$, one and only slot at row $i in [n-1]$ is unused.
For those pair $(i,j) in [n]^2 setminus [n-1]^2$ with $i < j$, we have $j = n$.
We can place the pair on row $k$ where $2k = i pmod {n-1}$. This will fill all the unused slots in the first $n-1$ rows and generate a desired packing of the $binom{n}{2}$ pairs into a $(n-1) times n$ rectangle.
answered yesterday
achille hui
93.4k5127251
It is always possible, we can place the $binom{n}{2}$ pairs in a $n times n$ square when $n$ is odd and in a $(n-1) times n$ rectangle when $n$ is even.
This problem is equivalent to the edge coloring problem for complete graph $K_n$. Look at wiki for the geometric intuition underlying following construction.
Let $[n]$ be a short hand for ${ 0, ldots, n-1 }$.
Index the set of possible pairs by $(i,j) in [n]^2$ with $i < j$.
Label rows and columns of the large square using numbers from $[n]$.
When $n$ is odd, place the pair $(i,j)$ at row $k$ of the large square where $i + j equiv k pmod n$.
If two pairs $(i_1,j_1)$, $(i_2,j_2)$ on same row intersect, then
one of the following happens
$$i_1 = i_2 lor i_1 = j_2lor j_1 = i_2 lor j_1 = j_2$$
Since $i_1 + j_1 equiv i_2 + j_2 pmod n$, we find
$$(i_1,j_1) = (i_2,j_2) pmod n lor (i_1,j_1) = (j_2,i_2) pmod n$$
Since $i_1,i_2,j_1,j_2 in [n]$ and $i_1 < j_1$, $i_2 < j_2$, we can rule out the second case. From this, we can deduce distinct pairs on some row are disjoint. This generate
a desired packing of the $binom{n}{2}$ pairs into a $n times n$ square.
When $n$ is even, $n - 1$ is odd.
Place those pair $(i,j) in [n-1]^2$ into row $k$ where $i + j equiv k pmod {n-1}$.
Notice
- For each row $i in [n-1]$, the slot at column $2i pmod {n - 1}$ and $n-1$ is unused.
- For any column $j in [n-1]$, one and only slot at row $i in [n-1]$ is unused.
For those pair $(i,j) in [n]^2 setminus [n-1]^2$ with $i < j$, we have $j = n$.
We can place the pair on row $k$ where $2k = i pmod {n-1}$. This will fill all the unused slots in the first $n-1$ rows and generate a desired packing of the $binom{n}{2}$ pairs into a $(n-1) times n$ rectangle.
answered yesterday
achille hui
93.4k5127251
edited yesterday
answered yesterday
achille hui
93.4k5127251
answered yesterday
achille hui
93.4k5127251
answered yesterday
achille hui
93.4k5127251
93.4k5127251
add a comment |
add a comment |
up vote
1
down vote
For 7×7, we have the following. X is an empty space, A through U are the 21 pairs of squares. For example, D D in the second row indicates that the {1,3} pair is used in that row, while the X in the seventh position means that spot is left empty.
A A B B C X C
D E D E F F X
G H X I H I G
J K K J X L L
X M N O O M N
P X Q R Q P R
S T U X S U T
.
answered 2 days ago
Oscar Lanzi
11.6k11935
1
It looks like for odd n, the empty spots are all in different columns. In other words, by rearranging the rows you can create a blank diagonal.
– Pazzaz
2 days ago
add a comment |
up vote
1
down vote
For 7×7, we have the following. X is an empty space, A through U are the 21 pairs of squares. For example, D D in the second row indicates that the {1,3} pair is used in that row, while the X in the seventh position means that spot is left empty.
A A B B C X C
D E D E F F X
G H X I H I G
J K K J X L L
X M N O O M N
P X Q R Q P R
S T U X S U T
.
answered 2 days ago
Oscar Lanzi
11.6k11935
1
It looks like for odd n, the empty spots are all in different columns. In other words, by rearranging the rows you can create a blank diagonal.
– Pazzaz
2 days ago
add a comment |
up vote
1
down vote
up vote
1
down vote
For 7×7, we have the following. X is an empty space, A through U are the 21 pairs of squares. For example, D D in the second row indicates that the {1,3} pair is used in that row, while the X in the seventh position means that spot is left empty.
A A B B C X C
D E D E F F X
G H X I H I G
J K K J X L L
X M N O O M N
P X Q R Q P R
S T U X S U T
.
answered 2 days ago
Oscar Lanzi
11.6k11935
For 7×7, we have the following. X is an empty space, A through U are the 21 pairs of squares. For example, D D in the second row indicates that the {1,3} pair is used in that row, while the X in the seventh position means that spot is left empty.
A A B B C X C
D E D E F F X
G H X I H I G
J K K J X L L
X M N O O M N
P X Q R Q P R
S T U X S U T
.
answered 2 days ago
Oscar Lanzi
11.6k11935
edited 2 days ago
answered 2 days ago
Oscar Lanzi
11.6k11935
answered 2 days ago
Oscar Lanzi
11.6k11935
answered 2 days ago
Oscar Lanzi
11.6k11935
11.6k11935
1
It looks like for odd n, the empty spots are all in different columns. In other words, by rearranging the rows you can create a blank diagonal.
– Pazzaz
2 days ago
add a comment |
1
It looks like for odd n, the empty spots are all in different columns. In other words, by rearranging the rows you can create a blank diagonal.
– Pazzaz
2 days ago
1
1
It looks like for odd n, the empty spots are all in different columns. In other words, by rearranging the rows you can create a blank diagonal.
– Pazzaz
2 days ago
It looks like for odd n, the empty spots are all in different columns. In other words, by rearranging the rows you can create a blank diagonal.
– Pazzaz
2 days ago
add a comment |
Pazzaz is a new contributor. Be nice, and check out our Code of Conduct.
Pazzaz is a new contributor. Be nice, and check out our Code of Conduct.
Pazzaz is a new contributor. Be nice, and check out our Code of Conduct.
Pazzaz is a new contributor. Be nice, and check out our Code of Conduct.
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%2f3004135%2fis-it-always-possible-to-fit-these-pieces-in-a-square%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
What does "all possible pieces (disconnected or connected) of width 2 and height of 1 that could fit in the square" mean? Can you show us how to generate the pieces for a given square?
– John Douma
2 days ago
@JohnDouma Well a piece here simply consists of choosing two squares in a single row of length n. So the total number of pieces will be (n choose 2).
– Pazzaz
2 days ago
1
I think you have to specify the problem more accurately. A triangle can have width $2$ and height $1$, for example, and that seems to be different from what you mean (and that is without thinking about figures which are not convex). I think you mean figures constructed of two $1times 1$ squares in a particular kind of configuration (as in your comment). And these sub-figures need not be connected. I do think your intended question is interesting, and worth asking, but the way you have asked it is misleading.
– Mark Bennet
2 days ago
@MarkBennet I agree, I did leave out some important parts. I've edited the question some, it should be more clear now.
– Pazzaz
2 days ago
Well, if possible, there will always be $n^2-2binom n2=n$ leftover spaces.
– YiFan
2 days ago