18
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ Do you mean that no matter how the stones are placed, and given a color, we can always find at least one right triangle? $\endgroup$ – John Douma Aug 29 '18 at 22:08
  • 3
    $\begingroup$ 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. $\endgroup$ – Stella Biderman Aug 29 '18 at 22:25
  • 1
    $\begingroup$ "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. $\endgroup$ – Stella Biderman Aug 29 '18 at 22:29
  • 1
    $\begingroup$ 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. $\endgroup$ – Ross Millikan Sep 1 '18 at 15:30
  • 2
    $\begingroup$ 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. $\endgroup$ – Jack D'Aurizio Sep 2 '18 at 14:15
11
$\begingroup$

Consider a finite $m\times 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 $1\le 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 $m\times 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/n\ge 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 $2n\times 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 $m\times 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.

$\endgroup$
  • $\begingroup$ thank you for your answer. What would be if you are looking for isosceles right-angled triangle. $\endgroup$ – C. Podolski Sep 1 '18 at 15:18
  • 1
    $\begingroup$ @C.Podolski If you have a variant of your question, you should ask this as a new question. $\endgroup$ – Mike Earnest Sep 1 '18 at 15:30
  • $\begingroup$ ok tank you. I'll do it. $\endgroup$ – C. Podolski Sep 1 '18 at 15:58
26
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Henning Makholm Aug 29 '18 at 22:00
  • 1
    $\begingroup$ "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? $\endgroup$ – John Douma Aug 29 '18 at 22:06
  • 4
    $\begingroup$ @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. $\endgroup$ – Henning Makholm Aug 29 '18 at 22:12
  • 2
    $\begingroup$ @HenningMakholm I disagree. Mathematics is about making precise statements. I should not have to seek an interpretation that makes a statement seem reasonable. $\endgroup$ – John Douma Aug 29 '18 at 22:20
  • 4
    $\begingroup$ @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. $\endgroup$ – aschepler Aug 30 '18 at 2:51
10
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.