Mixing
Triangles defined on an infinite Go board by same-colored stones
Clash Royale CLAN TAG#URR8PPP
up vote
18
down vote
favorite
You start with an infinite Go board. On every point of the board you place one colored stone. There are $n>1$ different colors. Find all natural numbers $n$ that no matter how the stones are colored, three stones of the same color form the vertices of a right-angled triangle. The catheti (legs) of the right triangle must be on the lines of the board.
Any ideas how to solve this kind of problem and to which area of mathematics this question belongs?
combinatorics recreational-mathematics ramsey-theory
edited Sep 5 at 22:41
PJTraill
612518
asked Aug 29 at 21:31
C. Podolski
1269
 |Â
show 4 more comments
up vote
18
down vote
favorite
You start with an infinite Go board. On every point of the board you place one colored stone. There are $n>1$ different colors. Find all natural numbers $n$ that no matter how the stones are colored, three stones of the same color form the vertices of a right-angled triangle. The catheti (legs) of the right triangle must be on the lines of the board.
Any ideas how to solve this kind of problem and to which area of mathematics this question belongs?
combinatorics recreational-mathematics ramsey-theory
edited Sep 5 at 22:41
PJTraill
612518
asked Aug 29 at 21:31
C. Podolski
1269
2
Do you mean that no matter how the stones are placed, and given a color, we can always find at least one right triangle?
– John Douma
Aug 29 at 22:08
3
The correct field for this is combinatorics. Within combinatorics, the study of structure that arises in very large (or infinite sets) is called Ramsey theory. When we are specifically talking about infinite sets, the term infinitary combinatorics is also appropriate. I would refer to this problem as Ramsey Theory alone, as it does not share the same character of most of infinitary combinatorics, despite being technically a combinatorial theorem about infinite sets. Infinitary combinatorics is primarily about the combinatorial structure of ordinals.
– Stella Biderman
Aug 29 at 22:25
1
"Ramsey Theory," "Ramsey's Theorem" (which inspired the field), and "Infinitary combinatorics" all have good Wikipedia articles if you wish to learn more about the field.
– Stella Biderman
Aug 29 at 22:29
1
Note that the original question did not specify isosceles right triangles The edit has invalidated several good answers. It should have been asked as a separate question. It is unfortunate that you assigned the bounty to the edited version.
– Ross Millikan
Sep 1 at 15:30
2
I completely agree with Ross Millikan, I performed a rollback and removed the bounty. Chamaleon questions should be avoided, especially if they are bounty questions. Remarkably, you already asked the isosceles variant here, and you should have been honest about the problem being part of a contest.
– Jack D'Aurizio♦
Sep 2 at 14:15
 |Â
show 4 more comments
up vote
18
down vote
favorite
up vote
18
down vote
favorite
You start with an infinite Go board. On every point of the board you place one colored stone. There are $n>1$ different colors. Find all natural numbers $n$ that no matter how the stones are colored, three stones of the same color form the vertices of a right-angled triangle. The catheti (legs) of the right triangle must be on the lines of the board.
Any ideas how to solve this kind of problem and to which area of mathematics this question belongs?
combinatorics recreational-mathematics ramsey-theory
edited Sep 5 at 22:41
PJTraill
612518
asked Aug 29 at 21:31
C. Podolski
1269
You start with an infinite Go board. On every point of the board you place one colored stone. There are $n>1$ different colors. Find all natural numbers $n$ that no matter how the stones are colored, three stones of the same color form the vertices of a right-angled triangle. The catheti (legs) of the right triangle must be on the lines of the board.
Any ideas how to solve this kind of problem and to which area of mathematics this question belongs?
combinatorics recreational-mathematics ramsey-theory
edited Sep 5 at 22:41
PJTraill
612518
asked Aug 29 at 21:31
C. Podolski
1269
edited Sep 5 at 22:41
PJTraill
612518
edited Sep 5 at 22:41
PJTraill
612518
edited Sep 5 at 22:41
PJTraill
612518
612518
asked Aug 29 at 21:31
C. Podolski
1269
asked Aug 29 at 21:31
C. Podolski
1269
asked Aug 29 at 21:31
C. Podolski
1269
1269
2
Do you mean that no matter how the stones are placed, and given a color, we can always find at least one right triangle?
– John Douma
Aug 29 at 22:08
3
The correct field for this is combinatorics. Within combinatorics, the study of structure that arises in very large (or infinite sets) is called Ramsey theory. When we are specifically talking about infinite sets, the term infinitary combinatorics is also appropriate. I would refer to this problem as Ramsey Theory alone, as it does not share the same character of most of infinitary combinatorics, despite being technically a combinatorial theorem about infinite sets. Infinitary combinatorics is primarily about the combinatorial structure of ordinals.
– Stella Biderman
Aug 29 at 22:25
1
"Ramsey Theory," "Ramsey's Theorem" (which inspired the field), and "Infinitary combinatorics" all have good Wikipedia articles if you wish to learn more about the field.
– Stella Biderman
Aug 29 at 22:29
1
Note that the original question did not specify isosceles right triangles The edit has invalidated several good answers. It should have been asked as a separate question. It is unfortunate that you assigned the bounty to the edited version.
– Ross Millikan
Sep 1 at 15:30
2
I completely agree with Ross Millikan, I performed a rollback and removed the bounty. Chamaleon questions should be avoided, especially if they are bounty questions. Remarkably, you already asked the isosceles variant here, and you should have been honest about the problem being part of a contest.
– Jack D'Aurizio♦
Sep 2 at 14:15
 |Â
show 4 more comments
2
Do you mean that no matter how the stones are placed, and given a color, we can always find at least one right triangle?
– John Douma
Aug 29 at 22:08
3
The correct field for this is combinatorics. Within combinatorics, the study of structure that arises in very large (or infinite sets) is called Ramsey theory. When we are specifically talking about infinite sets, the term infinitary combinatorics is also appropriate. I would refer to this problem as Ramsey Theory alone, as it does not share the same character of most of infinitary combinatorics, despite being technically a combinatorial theorem about infinite sets. Infinitary combinatorics is primarily about the combinatorial structure of ordinals.
– Stella Biderman
Aug 29 at 22:25
1
"Ramsey Theory," "Ramsey's Theorem" (which inspired the field), and "Infinitary combinatorics" all have good Wikipedia articles if you wish to learn more about the field.
– Stella Biderman
Aug 29 at 22:29
1
Note that the original question did not specify isosceles right triangles The edit has invalidated several good answers. It should have been asked as a separate question. It is unfortunate that you assigned the bounty to the edited version.
– Ross Millikan
Sep 1 at 15:30
2
I completely agree with Ross Millikan, I performed a rollback and removed the bounty. Chamaleon questions should be avoided, especially if they are bounty questions. Remarkably, you already asked the isosceles variant here, and you should have been honest about the problem being part of a contest.
– Jack D'Aurizio♦
Sep 2 at 14:15
2
2
Do you mean that no matter how the stones are placed, and given a color, we can always find at least one right triangle?
– John Douma
Aug 29 at 22:08
Do you mean that no matter how the stones are placed, and given a color, we can always find at least one right triangle?
– John Douma
Aug 29 at 22:08
3
3
The correct field for this is combinatorics. Within combinatorics, the study of structure that arises in very large (or infinite sets) is called Ramsey theory. When we are specifically talking about infinite sets, the term infinitary combinatorics is also appropriate. I would refer to this problem as Ramsey Theory alone, as it does not share the same character of most of infinitary combinatorics, despite being technically a combinatorial theorem about infinite sets. Infinitary combinatorics is primarily about the combinatorial structure of ordinals.
– Stella Biderman
Aug 29 at 22:25
The correct field for this is combinatorics. Within combinatorics, the study of structure that arises in very large (or infinite sets) is called Ramsey theory. When we are specifically talking about infinite sets, the term infinitary combinatorics is also appropriate. I would refer to this problem as Ramsey Theory alone, as it does not share the same character of most of infinitary combinatorics, despite being technically a combinatorial theorem about infinite sets. Infinitary combinatorics is primarily about the combinatorial structure of ordinals.
– Stella Biderman
Aug 29 at 22:25
1
1
"Ramsey Theory," "Ramsey's Theorem" (which inspired the field), and "Infinitary combinatorics" all have good Wikipedia articles if you wish to learn more about the field.
– Stella Biderman
Aug 29 at 22:29
"Ramsey Theory," "Ramsey's Theorem" (which inspired the field), and "Infinitary combinatorics" all have good Wikipedia articles if you wish to learn more about the field.
– Stella Biderman
Aug 29 at 22:29
1
1
Note that the original question did not specify isosceles right triangles The edit has invalidated several good answers. It should have been asked as a separate question. It is unfortunate that you assigned the bounty to the edited version.
– Ross Millikan
Sep 1 at 15:30
Note that the original question did not specify isosceles right triangles The edit has invalidated several good answers. It should have been asked as a separate question. It is unfortunate that you assigned the bounty to the edited version.
– Ross Millikan
Sep 1 at 15:30
2
2
I completely agree with Ross Millikan, I performed a rollback and removed the bounty. Chamaleon questions should be avoided, especially if they are bounty questions. Remarkably, you already asked the isosceles variant here, and you should have been honest about the problem being part of a contest.
– Jack D'Aurizio♦
Sep 2 at 14:15
I completely agree with Ross Millikan, I performed a rollback and removed the bounty. Chamaleon questions should be avoided, especially if they are bounty questions. Remarkably, you already asked the isosceles variant here, and you should have been honest about the problem being part of a contest.
– Jack D'Aurizio♦
Sep 2 at 14:15
 |Â
show 4 more comments
3 Answers
3
active
oldest
votes
up vote
11
down vote
accepted
Consider a finite $mtimes m$ board where every intersection either has a stone, or does not. If there are at least $2m$ stones on this board, then I claim there will exist three stones which are arranged in an axis-aligned right triangle.
To prove this, number the stones from $1$ to $2m$. For each $1le k le 2m$, let $f(k)$ be the number of rows spanned by the stones numbered $1$ to $k$, plus the number of columns spanned by these stones. Note that $f(1)=2$, $f(2m)le 2m$, and $f(k)$ is a weakly increasing function. It cannot be strictly increasing; if it were strictly increasing, you would have $f(2m)ge 2m-1+f(1)=2m+1$, contradicting $f(2m)le 2m$. This means there must be some number $k$ for which $f(k)=f(k-1)$. But this means that stone number $k$ is the same row as a previous stone, and in the same column as a previous stone, so that these three stones form a right triangle.
In particular, if an $mtimes m$ board is filled with stones in $n$ colors, then some color will appear on at least $m^2/n$ of the stones, so if $m^2/nge 2m$, there will be a right triangle of stones in that color. Therefore, for all $n$, an infinite colored board will have a monochromatic coloring, and to find one, you only need to search in a $2ntimes 2n$ sub-square of stones.
This problem seems to fall under the topic of Ramsey theory.
As a side note, you can also prove that an $mtimes m$ board with only $2m-1$ stones contains an axis-aligned right triangle. This is tight, since you can place $2m-2$ stones without forming a triangle.
answered Aug 29 at 22:05
Mike Earnest
17.4k11749
thank you for your answer. What would be if you are looking for isosceles right-angled triangle.
– C. Podolski
Sep 1 at 15:18
1
@C.Podolski If you have a variant of your question, you should ask this as a new question.
– Mike Earnest
Sep 1 at 15:30
ok tank you. I'll do it.
– C. Podolski
Sep 1 at 15:58
add a comment |Â
up vote
26
down vote
Any finite number $n$ will produce a right triangle, in fact an infinite number of them. The secret is that we can strike out lots of rows or columns and still have an infinite board. Given an $n$, pick a row of the board. There is at least one color that has an infinite number of stones in the row, call it red. Now delete all the columns that do not have a red stone in the row we are considering. We still have an infinite board, but the row under consideration has only red stones. If there is a red stone anywhere else on the board it will make an infinite number of red right triangles. Strike out the row under consideration and we have the same problem with $n-1$ colors. We can keep eliminating colors one by one until we get to just one.
answered Aug 29 at 21:55
Ross Millikan
279k22188355
One crucial step in this argument is to decide from the beginning only to look for axis-aligned right triangles; otherwise the striking-out of rows or columns wouldn't be safe.
– Henning Makholm
Aug 29 at 22:00
1
"no matter how the stones colored, three stones of the same color build a right triangle" Doesn't this mean that any three stones of the same color build a right triangle?
– John Douma
Aug 29 at 22:06
4
@JohnDouma: Since it neither says "any three stones" nor "for some three stones", I think it is reasonable to refrain from interpreting the problem in a way that would make it completely trivial, when a different meaningful interpretation is available.
– Henning Makholm
Aug 29 at 22:12
2
@HenningMakholm I disagree. Mathematics is about making precise statements. I should not have to seek an interpretation that makes a statement seem reasonable.
– John Douma
Aug 29 at 22:20
4
@MichaelSeifert Note the end of the proof is an appeal to induction on $n$. Yes, for the board you describe, this algorithm will strike out all odd columns, fails to show there is any red right triangle (even though there were some), and then strikes out row zero. This leaves us with an infinite board where all the stones are blue - the base case $n=1$. For this board, it's obvious there are infinitely many blue right triangles with legs parallel to the axes, and those are also blue right triangles on the original board.
– aschepler
Aug 30 at 2:51
 |Â
show 9 more comments
up vote
10
down vote
Call a stone h-unique if no other stone on the same row has the same colour, call it v-unique if no other stone on the same column has the same colour.
Clearly, every row contains at most $n-1$ h-unique stones and every column at most $n-1$ v-unique stones. Hence in a rectangle of $n$ rows and $n^2-n+1$ columns, there are at most $n^2-n$ h-unique stones. Hence there is a column of this rectangle that does not have a h-unique stone. One stone in this column is not v-unique. This stone, plus a stone witnessing its non-h-uniqeness, plus a stone witnessing its non-v-uniqueness, form a right triangle of same-colour stones as desired.
answered Aug 29 at 22:11
Hagen von Eitzen
266k21259480
add a comment |Â
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
11
down vote
accepted
Consider a finite $mtimes m$ board where every intersection either has a stone, or does not. If there are at least $2m$ stones on this board, then I claim there will exist three stones which are arranged in an axis-aligned right triangle.
To prove this, number the stones from $1$ to $2m$. For each $1le k le 2m$, let $f(k)$ be the number of rows spanned by the stones numbered $1$ to $k$, plus the number of columns spanned by these stones. Note that $f(1)=2$, $f(2m)le 2m$, and $f(k)$ is a weakly increasing function. It cannot be strictly increasing; if it were strictly increasing, you would have $f(2m)ge 2m-1+f(1)=2m+1$, contradicting $f(2m)le 2m$. This means there must be some number $k$ for which $f(k)=f(k-1)$. But this means that stone number $k$ is the same row as a previous stone, and in the same column as a previous stone, so that these three stones form a right triangle.
In particular, if an $mtimes m$ board is filled with stones in $n$ colors, then some color will appear on at least $m^2/n$ of the stones, so if $m^2/nge 2m$, there will be a right triangle of stones in that color. Therefore, for all $n$, an infinite colored board will have a monochromatic coloring, and to find one, you only need to search in a $2ntimes 2n$ sub-square of stones.
This problem seems to fall under the topic of Ramsey theory.
As a side note, you can also prove that an $mtimes m$ board with only $2m-1$ stones contains an axis-aligned right triangle. This is tight, since you can place $2m-2$ stones without forming a triangle.
answered Aug 29 at 22:05
Mike Earnest
17.4k11749
thank you for your answer. What would be if you are looking for isosceles right-angled triangle.
– C. Podolski
Sep 1 at 15:18
1
@C.Podolski If you have a variant of your question, you should ask this as a new question.
– Mike Earnest
Sep 1 at 15:30
ok tank you. I'll do it.
– C. Podolski
Sep 1 at 15:58
add a comment |Â
up vote
11
down vote
accepted
Consider a finite $mtimes m$ board where every intersection either has a stone, or does not. If there are at least $2m$ stones on this board, then I claim there will exist three stones which are arranged in an axis-aligned right triangle.
To prove this, number the stones from $1$ to $2m$. For each $1le k le 2m$, let $f(k)$ be the number of rows spanned by the stones numbered $1$ to $k$, plus the number of columns spanned by these stones. Note that $f(1)=2$, $f(2m)le 2m$, and $f(k)$ is a weakly increasing function. It cannot be strictly increasing; if it were strictly increasing, you would have $f(2m)ge 2m-1+f(1)=2m+1$, contradicting $f(2m)le 2m$. This means there must be some number $k$ for which $f(k)=f(k-1)$. But this means that stone number $k$ is the same row as a previous stone, and in the same column as a previous stone, so that these three stones form a right triangle.
In particular, if an $mtimes m$ board is filled with stones in $n$ colors, then some color will appear on at least $m^2/n$ of the stones, so if $m^2/nge 2m$, there will be a right triangle of stones in that color. Therefore, for all $n$, an infinite colored board will have a monochromatic coloring, and to find one, you only need to search in a $2ntimes 2n$ sub-square of stones.
This problem seems to fall under the topic of Ramsey theory.
As a side note, you can also prove that an $mtimes m$ board with only $2m-1$ stones contains an axis-aligned right triangle. This is tight, since you can place $2m-2$ stones without forming a triangle.
answered Aug 29 at 22:05
Mike Earnest
17.4k11749
thank you for your answer. What would be if you are looking for isosceles right-angled triangle.
– C. Podolski
Sep 1 at 15:18
1
@C.Podolski If you have a variant of your question, you should ask this as a new question.
– Mike Earnest
Sep 1 at 15:30
ok tank you. I'll do it.
– C. Podolski
Sep 1 at 15:58
add a comment |Â
up vote
11
down vote
accepted
up vote
11
down vote
accepted
Consider a finite $mtimes m$ board where every intersection either has a stone, or does not. If there are at least $2m$ stones on this board, then I claim there will exist three stones which are arranged in an axis-aligned right triangle.
To prove this, number the stones from $1$ to $2m$. For each $1le k le 2m$, let $f(k)$ be the number of rows spanned by the stones numbered $1$ to $k$, plus the number of columns spanned by these stones. Note that $f(1)=2$, $f(2m)le 2m$, and $f(k)$ is a weakly increasing function. It cannot be strictly increasing; if it were strictly increasing, you would have $f(2m)ge 2m-1+f(1)=2m+1$, contradicting $f(2m)le 2m$. This means there must be some number $k$ for which $f(k)=f(k-1)$. But this means that stone number $k$ is the same row as a previous stone, and in the same column as a previous stone, so that these three stones form a right triangle.
In particular, if an $mtimes m$ board is filled with stones in $n$ colors, then some color will appear on at least $m^2/n$ of the stones, so if $m^2/nge 2m$, there will be a right triangle of stones in that color. Therefore, for all $n$, an infinite colored board will have a monochromatic coloring, and to find one, you only need to search in a $2ntimes 2n$ sub-square of stones.
This problem seems to fall under the topic of Ramsey theory.
As a side note, you can also prove that an $mtimes m$ board with only $2m-1$ stones contains an axis-aligned right triangle. This is tight, since you can place $2m-2$ stones without forming a triangle.
answered Aug 29 at 22:05
Mike Earnest
17.4k11749
Consider a finite $mtimes m$ board where every intersection either has a stone, or does not. If there are at least $2m$ stones on this board, then I claim there will exist three stones which are arranged in an axis-aligned right triangle.
To prove this, number the stones from $1$ to $2m$. For each $1le k le 2m$, let $f(k)$ be the number of rows spanned by the stones numbered $1$ to $k$, plus the number of columns spanned by these stones. Note that $f(1)=2$, $f(2m)le 2m$, and $f(k)$ is a weakly increasing function. It cannot be strictly increasing; if it were strictly increasing, you would have $f(2m)ge 2m-1+f(1)=2m+1$, contradicting $f(2m)le 2m$. This means there must be some number $k$ for which $f(k)=f(k-1)$. But this means that stone number $k$ is the same row as a previous stone, and in the same column as a previous stone, so that these three stones form a right triangle.
In particular, if an $mtimes m$ board is filled with stones in $n$ colors, then some color will appear on at least $m^2/n$ of the stones, so if $m^2/nge 2m$, there will be a right triangle of stones in that color. Therefore, for all $n$, an infinite colored board will have a monochromatic coloring, and to find one, you only need to search in a $2ntimes 2n$ sub-square of stones.
This problem seems to fall under the topic of Ramsey theory.
As a side note, you can also prove that an $mtimes m$ board with only $2m-1$ stones contains an axis-aligned right triangle. This is tight, since you can place $2m-2$ stones without forming a triangle.
answered Aug 29 at 22:05
Mike Earnest
17.4k11749
edited Aug 29 at 22:29
answered Aug 29 at 22:05
Mike Earnest
17.4k11749
answered Aug 29 at 22:05
Mike Earnest
17.4k11749
answered Aug 29 at 22:05
Mike Earnest
17.4k11749
17.4k11749
thank you for your answer. What would be if you are looking for isosceles right-angled triangle.
– C. Podolski
Sep 1 at 15:18
1
@C.Podolski If you have a variant of your question, you should ask this as a new question.
– Mike Earnest
Sep 1 at 15:30
ok tank you. I'll do it.
– C. Podolski
Sep 1 at 15:58
add a comment |Â
thank you for your answer. What would be if you are looking for isosceles right-angled triangle.
– C. Podolski
Sep 1 at 15:18
1
@C.Podolski If you have a variant of your question, you should ask this as a new question.
– Mike Earnest
Sep 1 at 15:30
ok tank you. I'll do it.
– C. Podolski
Sep 1 at 15:58
thank you for your answer. What would be if you are looking for isosceles right-angled triangle.
– C. Podolski
Sep 1 at 15:18
thank you for your answer. What would be if you are looking for isosceles right-angled triangle.
– C. Podolski
Sep 1 at 15:18
1
1
@C.Podolski If you have a variant of your question, you should ask this as a new question.
– Mike Earnest
Sep 1 at 15:30
@C.Podolski If you have a variant of your question, you should ask this as a new question.
– Mike Earnest
Sep 1 at 15:30
ok tank you. I'll do it.
– C. Podolski
Sep 1 at 15:58
ok tank you. I'll do it.
– C. Podolski
Sep 1 at 15:58
add a comment |Â
up vote
26
down vote
Any finite number $n$ will produce a right triangle, in fact an infinite number of them. The secret is that we can strike out lots of rows or columns and still have an infinite board. Given an $n$, pick a row of the board. There is at least one color that has an infinite number of stones in the row, call it red. Now delete all the columns that do not have a red stone in the row we are considering. We still have an infinite board, but the row under consideration has only red stones. If there is a red stone anywhere else on the board it will make an infinite number of red right triangles. Strike out the row under consideration and we have the same problem with $n-1$ colors. We can keep eliminating colors one by one until we get to just one.
answered Aug 29 at 21:55
Ross Millikan
279k22188355
One crucial step in this argument is to decide from the beginning only to look for axis-aligned right triangles; otherwise the striking-out of rows or columns wouldn't be safe.
– Henning Makholm
Aug 29 at 22:00
1
"no matter how the stones colored, three stones of the same color build a right triangle" Doesn't this mean that any three stones of the same color build a right triangle?
– John Douma
Aug 29 at 22:06
4
@JohnDouma: Since it neither says "any three stones" nor "for some three stones", I think it is reasonable to refrain from interpreting the problem in a way that would make it completely trivial, when a different meaningful interpretation is available.
– Henning Makholm
Aug 29 at 22:12
2
@HenningMakholm I disagree. Mathematics is about making precise statements. I should not have to seek an interpretation that makes a statement seem reasonable.
– John Douma
Aug 29 at 22:20
4
@MichaelSeifert Note the end of the proof is an appeal to induction on $n$. Yes, for the board you describe, this algorithm will strike out all odd columns, fails to show there is any red right triangle (even though there were some), and then strikes out row zero. This leaves us with an infinite board where all the stones are blue - the base case $n=1$. For this board, it's obvious there are infinitely many blue right triangles with legs parallel to the axes, and those are also blue right triangles on the original board.
– aschepler
Aug 30 at 2:51
 |Â
show 9 more comments
up vote
26
down vote
Any finite number $n$ will produce a right triangle, in fact an infinite number of them. The secret is that we can strike out lots of rows or columns and still have an infinite board. Given an $n$, pick a row of the board. There is at least one color that has an infinite number of stones in the row, call it red. Now delete all the columns that do not have a red stone in the row we are considering. We still have an infinite board, but the row under consideration has only red stones. If there is a red stone anywhere else on the board it will make an infinite number of red right triangles. Strike out the row under consideration and we have the same problem with $n-1$ colors. We can keep eliminating colors one by one until we get to just one.
answered Aug 29 at 21:55
Ross Millikan
279k22188355
One crucial step in this argument is to decide from the beginning only to look for axis-aligned right triangles; otherwise the striking-out of rows or columns wouldn't be safe.
– Henning Makholm
Aug 29 at 22:00
1
"no matter how the stones colored, three stones of the same color build a right triangle" Doesn't this mean that any three stones of the same color build a right triangle?
– John Douma
Aug 29 at 22:06
4
@JohnDouma: Since it neither says "any three stones" nor "for some three stones", I think it is reasonable to refrain from interpreting the problem in a way that would make it completely trivial, when a different meaningful interpretation is available.
– Henning Makholm
Aug 29 at 22:12
2
@HenningMakholm I disagree. Mathematics is about making precise statements. I should not have to seek an interpretation that makes a statement seem reasonable.
– John Douma
Aug 29 at 22:20
4
@MichaelSeifert Note the end of the proof is an appeal to induction on $n$. Yes, for the board you describe, this algorithm will strike out all odd columns, fails to show there is any red right triangle (even though there were some), and then strikes out row zero. This leaves us with an infinite board where all the stones are blue - the base case $n=1$. For this board, it's obvious there are infinitely many blue right triangles with legs parallel to the axes, and those are also blue right triangles on the original board.
– aschepler
Aug 30 at 2:51
 |Â
show 9 more comments
up vote
26
down vote
up vote
26
down vote
Any finite number $n$ will produce a right triangle, in fact an infinite number of them. The secret is that we can strike out lots of rows or columns and still have an infinite board. Given an $n$, pick a row of the board. There is at least one color that has an infinite number of stones in the row, call it red. Now delete all the columns that do not have a red stone in the row we are considering. We still have an infinite board, but the row under consideration has only red stones. If there is a red stone anywhere else on the board it will make an infinite number of red right triangles. Strike out the row under consideration and we have the same problem with $n-1$ colors. We can keep eliminating colors one by one until we get to just one.
answered Aug 29 at 21:55
Ross Millikan
279k22188355
Any finite number $n$ will produce a right triangle, in fact an infinite number of them. The secret is that we can strike out lots of rows or columns and still have an infinite board. Given an $n$, pick a row of the board. There is at least one color that has an infinite number of stones in the row, call it red. Now delete all the columns that do not have a red stone in the row we are considering. We still have an infinite board, but the row under consideration has only red stones. If there is a red stone anywhere else on the board it will make an infinite number of red right triangles. Strike out the row under consideration and we have the same problem with $n-1$ colors. We can keep eliminating colors one by one until we get to just one.
answered Aug 29 at 21:55
Ross Millikan
279k22188355
answered Aug 29 at 21:55
Ross Millikan
279k22188355
answered Aug 29 at 21:55
Ross Millikan
279k22188355
answered Aug 29 at 21:55
Ross Millikan
279k22188355
279k22188355
One crucial step in this argument is to decide from the beginning only to look for axis-aligned right triangles; otherwise the striking-out of rows or columns wouldn't be safe.
– Henning Makholm
Aug 29 at 22:00
1
"no matter how the stones colored, three stones of the same color build a right triangle" Doesn't this mean that any three stones of the same color build a right triangle?
– John Douma
Aug 29 at 22:06
4
@JohnDouma: Since it neither says "any three stones" nor "for some three stones", I think it is reasonable to refrain from interpreting the problem in a way that would make it completely trivial, when a different meaningful interpretation is available.
– Henning Makholm
Aug 29 at 22:12
2
@HenningMakholm I disagree. Mathematics is about making precise statements. I should not have to seek an interpretation that makes a statement seem reasonable.
– John Douma
Aug 29 at 22:20
4
@MichaelSeifert Note the end of the proof is an appeal to induction on $n$. Yes, for the board you describe, this algorithm will strike out all odd columns, fails to show there is any red right triangle (even though there were some), and then strikes out row zero. This leaves us with an infinite board where all the stones are blue - the base case $n=1$. For this board, it's obvious there are infinitely many blue right triangles with legs parallel to the axes, and those are also blue right triangles on the original board.
– aschepler
Aug 30 at 2:51
 |Â
show 9 more comments
One crucial step in this argument is to decide from the beginning only to look for axis-aligned right triangles; otherwise the striking-out of rows or columns wouldn't be safe.
– Henning Makholm
Aug 29 at 22:00
1
"no matter how the stones colored, three stones of the same color build a right triangle" Doesn't this mean that any three stones of the same color build a right triangle?
– John Douma
Aug 29 at 22:06
4
@JohnDouma: Since it neither says "any three stones" nor "for some three stones", I think it is reasonable to refrain from interpreting the problem in a way that would make it completely trivial, when a different meaningful interpretation is available.
– Henning Makholm
Aug 29 at 22:12
2
@HenningMakholm I disagree. Mathematics is about making precise statements. I should not have to seek an interpretation that makes a statement seem reasonable.
– John Douma
Aug 29 at 22:20
4
@MichaelSeifert Note the end of the proof is an appeal to induction on $n$. Yes, for the board you describe, this algorithm will strike out all odd columns, fails to show there is any red right triangle (even though there were some), and then strikes out row zero. This leaves us with an infinite board where all the stones are blue - the base case $n=1$. For this board, it's obvious there are infinitely many blue right triangles with legs parallel to the axes, and those are also blue right triangles on the original board.
– aschepler
Aug 30 at 2:51
One crucial step in this argument is to decide from the beginning only to look for axis-aligned right triangles; otherwise the striking-out of rows or columns wouldn't be safe.
– Henning Makholm
Aug 29 at 22:00
One crucial step in this argument is to decide from the beginning only to look for axis-aligned right triangles; otherwise the striking-out of rows or columns wouldn't be safe.
– Henning Makholm
Aug 29 at 22:00
1
1
"no matter how the stones colored, three stones of the same color build a right triangle" Doesn't this mean that any three stones of the same color build a right triangle?
– John Douma
Aug 29 at 22:06
"no matter how the stones colored, three stones of the same color build a right triangle" Doesn't this mean that any three stones of the same color build a right triangle?
– John Douma
Aug 29 at 22:06
4
4
@JohnDouma: Since it neither says "any three stones" nor "for some three stones", I think it is reasonable to refrain from interpreting the problem in a way that would make it completely trivial, when a different meaningful interpretation is available.
– Henning Makholm
Aug 29 at 22:12
@JohnDouma: Since it neither says "any three stones" nor "for some three stones", I think it is reasonable to refrain from interpreting the problem in a way that would make it completely trivial, when a different meaningful interpretation is available.
– Henning Makholm
Aug 29 at 22:12
2
2
@HenningMakholm I disagree. Mathematics is about making precise statements. I should not have to seek an interpretation that makes a statement seem reasonable.
– John Douma
Aug 29 at 22:20
@HenningMakholm I disagree. Mathematics is about making precise statements. I should not have to seek an interpretation that makes a statement seem reasonable.
– John Douma
Aug 29 at 22:20
4
4
@MichaelSeifert Note the end of the proof is an appeal to induction on $n$. Yes, for the board you describe, this algorithm will strike out all odd columns, fails to show there is any red right triangle (even though there were some), and then strikes out row zero. This leaves us with an infinite board where all the stones are blue - the base case $n=1$. For this board, it's obvious there are infinitely many blue right triangles with legs parallel to the axes, and those are also blue right triangles on the original board.
– aschepler
Aug 30 at 2:51
@MichaelSeifert Note the end of the proof is an appeal to induction on $n$. Yes, for the board you describe, this algorithm will strike out all odd columns, fails to show there is any red right triangle (even though there were some), and then strikes out row zero. This leaves us with an infinite board where all the stones are blue - the base case $n=1$. For this board, it's obvious there are infinitely many blue right triangles with legs parallel to the axes, and those are also blue right triangles on the original board.
– aschepler
Aug 30 at 2:51
 |Â
show 9 more comments
up vote
10
down vote
Call a stone h-unique if no other stone on the same row has the same colour, call it v-unique if no other stone on the same column has the same colour.
Clearly, every row contains at most $n-1$ h-unique stones and every column at most $n-1$ v-unique stones. Hence in a rectangle of $n$ rows and $n^2-n+1$ columns, there are at most $n^2-n$ h-unique stones. Hence there is a column of this rectangle that does not have a h-unique stone. One stone in this column is not v-unique. This stone, plus a stone witnessing its non-h-uniqeness, plus a stone witnessing its non-v-uniqueness, form a right triangle of same-colour stones as desired.
answered Aug 29 at 22:11
Hagen von Eitzen
266k21259480
add a comment |Â
up vote
10
down vote
Call a stone h-unique if no other stone on the same row has the same colour, call it v-unique if no other stone on the same column has the same colour.
Clearly, every row contains at most $n-1$ h-unique stones and every column at most $n-1$ v-unique stones. Hence in a rectangle of $n$ rows and $n^2-n+1$ columns, there are at most $n^2-n$ h-unique stones. Hence there is a column of this rectangle that does not have a h-unique stone. One stone in this column is not v-unique. This stone, plus a stone witnessing its non-h-uniqeness, plus a stone witnessing its non-v-uniqueness, form a right triangle of same-colour stones as desired.
answered Aug 29 at 22:11
Hagen von Eitzen
266k21259480
add a comment |Â
up vote
10
down vote
up vote
10
down vote
Call a stone h-unique if no other stone on the same row has the same colour, call it v-unique if no other stone on the same column has the same colour.
Clearly, every row contains at most $n-1$ h-unique stones and every column at most $n-1$ v-unique stones. Hence in a rectangle of $n$ rows and $n^2-n+1$ columns, there are at most $n^2-n$ h-unique stones. Hence there is a column of this rectangle that does not have a h-unique stone. One stone in this column is not v-unique. This stone, plus a stone witnessing its non-h-uniqeness, plus a stone witnessing its non-v-uniqueness, form a right triangle of same-colour stones as desired.
answered Aug 29 at 22:11
Hagen von Eitzen
266k21259480
Call a stone h-unique if no other stone on the same row has the same colour, call it v-unique if no other stone on the same column has the same colour.
Clearly, every row contains at most $n-1$ h-unique stones and every column at most $n-1$ v-unique stones. Hence in a rectangle of $n$ rows and $n^2-n+1$ columns, there are at most $n^2-n$ h-unique stones. Hence there is a column of this rectangle that does not have a h-unique stone. One stone in this column is not v-unique. This stone, plus a stone witnessing its non-h-uniqeness, plus a stone witnessing its non-v-uniqueness, form a right triangle of same-colour stones as desired.
answered Aug 29 at 22:11
Hagen von Eitzen
266k21259480
answered Aug 29 at 22:11
Hagen von Eitzen
266k21259480
answered Aug 29 at 22:11
Hagen von Eitzen
266k21259480
answered Aug 29 at 22:11
Hagen von Eitzen
266k21259480
266k21259480
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%2f2898846%2ftriangles-defined-on-an-infinite-go-board-by-same-colored-stones%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
2
Do you mean that no matter how the stones are placed, and given a color, we can always find at least one right triangle?
– John Douma
Aug 29 at 22:08
3
The correct field for this is combinatorics. Within combinatorics, the study of structure that arises in very large (or infinite sets) is called Ramsey theory. When we are specifically talking about infinite sets, the term infinitary combinatorics is also appropriate. I would refer to this problem as Ramsey Theory alone, as it does not share the same character of most of infinitary combinatorics, despite being technically a combinatorial theorem about infinite sets. Infinitary combinatorics is primarily about the combinatorial structure of ordinals.
– Stella Biderman
Aug 29 at 22:25
1
"Ramsey Theory," "Ramsey's Theorem" (which inspired the field), and "Infinitary combinatorics" all have good Wikipedia articles if you wish to learn more about the field.
– Stella Biderman
Aug 29 at 22:29
1
Note that the original question did not specify isosceles right triangles The edit has invalidated several good answers. It should have been asked as a separate question. It is unfortunate that you assigned the bounty to the edited version.
– Ross Millikan
Sep 1 at 15:30
2
I completely agree with Ross Millikan, I performed a rollback and removed the bounty. Chamaleon questions should be avoided, especially if they are bounty questions. Remarkably, you already asked the isosceles variant here, and you should have been honest about the problem being part of a contest.
– Jack D'Aurizio♦
Sep 2 at 14:15