39
$\begingroup$

In chess, Knights moves to squares a distance $\sqrt5$ away. Bishops move distances $\sqrt2$, $\sqrt8$, $\sqrt{18}$, etc. Both pieces are restricted to non-integer distance moves.

Enter the Knishop, a most potent chess piece capable of moving to any squares at non-integer distance: $\sqrt2$, $\sqrt5$, $\sqrt8$, $\sqrt{10}$, $\sqrt{13}$, $\sqrt{18}$, ...

Given a chess board of unlimited extent, place three Knishops such that they can't capture each other, while any piece being added to the board can be captured in a single move.

$\endgroup$
  • 2
    $\begingroup$ Perhaps this is more suited to math.se? $\endgroup$ – Aryabhata Jan 3 '15 at 6:49
  • 2
    $\begingroup$ @Aryabhata - I was of the impression that if I know the answer to a math puzzle, this forum is the one to use. Conversely, math.se is more appropriate in case I am looking for the answer. Am I wrong on this? $\endgroup$ – Johannes Jan 3 '15 at 12:22
  • 6
    $\begingroup$ This is fine for Puzzling although it would probably work on math or chess too. $\endgroup$ – warspyking Jan 3 '15 at 14:37
  • 2
    $\begingroup$ @Johannes: On math.se (or any se site) you can ask a question you know the answer to. But if you are looking to puzzle folks and not give any solutions etc, this is probably the right site. I was only concerned about the depth of math you might need to know. $\endgroup$ – Aryabhata Jan 3 '15 at 19:33
  • 2
    $\begingroup$ @Johannes I am little confused about the problem formulation. You are talking about a knishop on a chessboard which we can represent as an integer lattice with the lattice points in the center of the squares for example. Knight moves $\sqrt{5}$ and bishop moves $n\sqrt{2}$ for any natural $n$ are well defined. But how can a knishop move $\sqrt{3}$ distance? If a knishop is occupying a square (let's say d4 in the middle of a standard board) then which square is $\sqrt{3}$ away? $\endgroup$ – Fixed Point Jan 4 '15 at 1:44
21
$\begingroup$

This question appears to be first settled in A. Kohnert and S. Kurz, A note on Erdős-Diophantine graphs and Diophantine carpets, Mathematica Balkanica, 21(1-2):1–5, 2007, available on arxiv.org.

A Diophantine figure is a set of points on the integer grid $\mathbb{Z}^2$ where all mutual Euclidean distances are integers. We also speak of Diophantine graphs. The vertices are points in $\mathbb{Z}^2$ (the coordinates) and the edges are labeled with the distance between the two adjacent vertices, which is integral. In this language a Diophantine figure is a complete Diophantine graph. ... Due to a famous theorem of Erdős and Anning there are complete Diophantine graphs which are not contained in larger ones. We call them Erdős-Diophantine graphs.

Note that a three-vertex Erdős-Diophantine graph is precisely what the question asks for: the three vertices are at mutually integer distances, but there is no point which is at an integer distance from all of them, or it would not be Erdős-Diophantine.

Kohnert and Kurz list seven Erdős-Diophantine triangles and state that they form a complete list for triangles having an edge of length $\le 5000$. (They appear to actually mean having all edges $\le 5000$).

$$(2066, 1803, 505)\\ (2549, 2307, 1492)\\ (3796, 2787, 2165)\\ (4083, 2425, 1706)\\ (4426, 2807, 2210)\\ (4920, 4177, 985)$$

A later paper of Kurz lists many more.

Taking the first listed example, we place knishops at $(0, 0),\; (384, 2030),\; (720, 1653)$.

$\endgroup$
  • $\begingroup$ Very nice! This appears to be more than adequate: there could have been points at integer distances from all three knishops but not corresponding to the centre of a square. $\endgroup$ – frodoskywalker Jan 5 '15 at 17:21
  • $\begingroup$ And unless I'm mistaken, their method was basically to run Meelo's algorithm for a longer time. (Possibly with some clever optimizations) $\endgroup$ – Lopsy Jan 5 '15 at 20:20
  • $\begingroup$ "Clever" optimizations might not be necessary; obvious optimizations would work equally well (those numbers are only about a factor of 3 beyond where my search ended after ~24 hours) - I'm sure just writing it in C++ from scratch (since Mathematica is slow) and having the check stop when it finds the first exception rather than generating a list would be more than sufficient to find such solutions. It's pretty surprising and interesting to me that these solutions actually exist! $\endgroup$ – Milo Brandt Jan 5 '15 at 23:24
16
$\begingroup$

This is not a solution, but it is much too long to be a comment. If a solution exists, this post gives the theoretical machinery to verify it and to narrow the search. However, I have checked a considerable number of cases without finding a solution, which suggests that there may be none, or that if there is, it will be hard to find. But at least now we can make people sad when they find an incorrect solution. :)


The knishops clearly must form a non-degenerate triangle with integer side lengths and points on the integer lattice (i.e. both $(x,y)$ coordinates are integers). These two conditions are equivalent to demanding that the knishops be the vertices of a Heronian triangle. Moreover, by the condition that every square must be reachable by one of the knishops, we can exclude any solution where two knishops have the same $x$ or $y$ coordinate - in particular, if we had the knishops at $(0,0)$, $(x,0$) and $(x',y')$, then the reflection of the last point over the line between the first two, $(x',-y')$, would have integer distances to each point and thus be uncovered. Reflecting over one of the legs of a right triangle yields a similar problem, meaning the distances between the knishops must not form a Pythagorean triple. We could take this argument further to notice that we need that the reflection of one knishop over the line between the other two must not lie on a lattice point, since the distance between the knishop and its reflection is an integer (due to Pick's theorem), and obviously so is the distance from each other knishop to the reflection - thus, if it were a lattice point, it would not be covered.

Simply applying that the Heronian triangle must be drawn on an integer lattice with no two points with the same $x$ or $y$ coordinates and going down the list of Heronian triangles on Wikipedia yields that the first suitable Heronian triangle is the one with side lengths $5$, $29$, $30$. This gives coordinates for the knishops of $(0,0)$, $(3,4)$, and $(21,-20)$. If we wanted to check for uncovered squares, we could set up three equations in integers $d_1,d_2,d_3$ being the distances of a hypothetical uncovered position $(x,y)$: $$d_1^2=x^2+y^2$$ $$d_2^2=(x-3)^2+(y-4)^2$$ $$d_3^2=(x-21)^2+(y+20)^2$$ and wish to show that the only integer $(x,y)$ with an integer solution to the above are the positions of the knishops - that is, every other square is covered. However, we can note that by the triangle inequality, we have: $$|d_1-d_2|\leq 5$$ $$|d_1-d_3|\leq 29$$ meaning that there are only finitely many choices of $a,b$ such that it is possible that $d_2=d_1+a$ and $d_3=d_1+b$ - in particular, we choose $a$ as an integer in $[-5,5]$ and $b$ as an integer in $[-29,29]$ yielding $649$ possible choices. However, this is finite and means that if we find every solution to $$d_1^2=x^2+y^2$$ $$(d_1+a)^2=(x-3)^2+(y-4)^2$$ $$(d_1+b)^2=(x-21)^2+(y+20)^2$$ which is a system of $3$ independent polynomials in $3$ variables (being the intersection of $3$ hyperboloids) and hence has finitely many solutions. Thus, we can generate, using Mathematica (or your favorite software; numerical solutions suffice, since we only wish to show that something is not an integer, and rather crude bounds suffice for that), every single solution to the above equations for integer $a$ and $b$ in the proper ranges. This yields a list of uncovered squares, like $(-15,-20)$. Mathematica code follows:

CheckPair[x1_, y1_, x2_, y2_] := Module[{z, d1, d2},
d1 = Norm[{x1, y1}];
d2 = Norm[{x2, y2}];
If[! (IntegerQ[d1] && IntegerQ[d2]), Return[False]];
z = Solve[{d^2 == x^2 + y^2, (d + a)^2 == (x - x1)^2 + (y - y1)^2, (d + b)^2 == (x - x2)^2 + (y - y2)^2}, {d, x, y}];
DeleteDuplicates[ Select[{Floor[x + .5], Floor[y + .5]} /. Join @@ (Join @@ Table[N[z /. {a -> m, b -> n}], {m, -d1, d1}, {n, -d2, d2}]), IntegerQ[Norm[#]] && IntegerQ[Norm[# - {x1, y1}]] && IntegerQ[Norm[# - {x2, y2}]] &]]];

where the function CheckPair takes as input the positions of two knishops relative the other (i.e. it assumes one is at $(0,0)$) and outputs a list of exceptions (or false if the input is invalid). I used this, along with a simple brute force search to figure out how to draw each triangle on a lattice, to check up to the triple $(5,51,52)$ on the list of Heronian triangles on Wikipedia. I did not find any solutions.


I have continued my computations by writing code to generate Heronian triples. I've left it running for several hours, and not found anything, but the computation becomes very slow after a point. Even filtering by the criteria in the first paragraph seems insufficient to make the brute force search feasible; additional insight will be required.

$\endgroup$
  • $\begingroup$ This is very useful work. But judging by Johannes' previous questions, I expect there's a much neater answer one way or another. $\endgroup$ – Callidus Jan 4 '15 at 6:04
  • $\begingroup$ This approach seems to be the one described in the paper I link, without any additional insight (although possibly with a more efficient implementation). $\endgroup$ – Peter Taylor Jan 5 '15 at 12:25
5
$\begingroup$

Knishops can't take pieces in their row or column, because those are all integer distances. They can't all be in a line because that entire line will be free for other pieces to sit. If two of them are in a line, the other one will have a square on that line which it can't take and thus other pieces can sit there.

Thus each of the pieces must be a pythagorean triangle away from others - not the same column or line, but an integer distance. They can't be at linear multiples of the same pythagorean triangle, because later linear multiples will also be unreachable by the Knishops.

There are probably infinitely many such solutions, but here's one:

One piece is at square 0,0 (for convenience). The next piece is at square 20, 48 (which is four times 5, 12 --> 13). The third piece is at square 9, -12 (which is three times 3, 4 --> 5, but below the x-axis). So the distance from 1st to 2nd is 52; from 1st to 3rd is 15; and from 2nd to 3rd is the distance of 20-9, 48+12 which is 11,60 --> 61.

One thing I have not proved is that there are no squares anywhere else on the board that are unreachable by my three knishops. I'll add that if I can.

$\endgroup$
  • 1
    $\begingroup$ Provide a picture? $\endgroup$ – warspyking Jan 3 '15 at 14:39
  • 6
    $\begingroup$ The points $(-36,48)$, $(-5,-12)$, $(-55,-132)$, $(779,660)$, $(90,-120)$, $(360,-480)$, and $(-1521,2028)$ are not covered. Every other point is. (I used the triangle inequality to bound the difference between the distance of the first knishop to $(x,y)$ and the distances from the other knishops to $(x,y)$, reducing this to looking for integer solutions to $3255$ systems of polynomial equations in three variables. Similar methods establish that non-collinear kniships cover all but finitely many points. I suspect that no solution exists, but that it is incredibly hard to prove so) $\endgroup$ – Milo Brandt Jan 3 '15 at 17:42
  • $\begingroup$ @Meelo Thanks for that - saves me trying to prove something that isn't true! $\endgroup$ – Callidus Jan 4 '15 at 6:02
1
$\begingroup$

I've been slightly discouraged by the other answers (TL;DR), but here are my thoughts:

I'm thinking that they would have to be placed on paths of perfect right triangles (i.e. $l=3,w=4,\because\sqrt{3^2+4^2}=5$) I'd imagine that there are an infinite amount of these triangles.

Here are some of the movesets that knishops cannot move along:

  • $\pm(3x,4x)$
  • $\pm(0,x)$
  • $\pm(5x,12x)$
  • $\pm(6x,8x)$
  • $\pm(9x,12x)$

Since there are an infinite number of these triangles, there are, as a result, an infinite number of places that the knishops cannot move to; it is therefore impossible to place three bishops that they can capture every other piece on the infinite board but not each other; such a set up would require that the knishops fall into each other's 'out-of-reach spots' if you will; then, each knishop would have an infinite number of 'out-of-reach spots', so, as a result, there exist at least one $(x,y)$ coordinate that falls out of reach of all three knishops.

After thoroughly reading the other answers, I fear that my intuition is correct; proving it, however, will be harder.

Conjecture: Let $K$ be the set of knishops on the board; each knishop is a coordinate pair, as $(x,y)$. Then, our conjecture becomes, in order to prove that the alleged setup is indeed impossible: $\exists x,y\in\mathbb{Z}:\sqrt{x^2+y^2}\in\mathbb{Z}$ and that $\not\exists w,z\in\mathbb{Z}\land\sqrt{w^2+z^2}\notin\mathbb{Z}:(x\cdot w,y\cdot z)\notin K$. This states that there does not exists a path on which a knishop can travel to $(x,y)$ by means of having a line $\overline{wz}$ whose length is not an integer (which would entail the knishop being able to travel along it).

$Proof.$

Let us prove this by making a contradiction when assuming the negative of the conjecture; that is, $\not\exists x,y\in\mathbb{Z}:\sqrt{x^2+y^2}\in\mathbb{Z}\land\exists w,z\in\mathbb{Z}\land\sqrt{w^2+z^2}\in\mathbb{Z}:(x\cdot w,y\cdot z)\in K$, in other words, assuming the setup is possible.

Then, by our presumed false negative conjecture, the coordinates $(xw,yz)$ would be those of a knishop in $K$. $(x,y)$ would be the coordinates of a piece on our infinite board regardless. Proving that $\sqrt{w^2+z^2}\notin\mathbb{Z}$ would be sufficient to prove our conjecture.

[WIP]

$\endgroup$
  • 2
    $\begingroup$ This is incorrect. They cannot move any integer distance, which means they can't reach any squares in their column/row. Which means if they're all in the same row, none of the squares in that row can be reached. $\endgroup$ – BlueRaja - Danny Pflughoeft Jan 3 '15 at 7:41
  • $\begingroup$ @BlueRaja-DannyPflughoeft Sorry, misread the question. $\endgroup$ – Conor O'Brien Jan 3 '15 at 8:06
  • 1
    $\begingroup$ I do not understand your proof - though I see that it may still be a work in progress. It would be wise to use less symbols and more words - clarity is always a worthier goal than rigor. (Also, you don't appear to be using the hypothesis that there are at most $3$ knishops; I presume that it is possible with $4$, though I don't want to interrupt my brute force search to check, but if not, it is possible with some finite number of knishops). Also, those triangles are the legs of Pythagorean triples - on which, plenty is known (see Wikipedia for how to generate them) $\endgroup$ – Milo Brandt Jan 3 '15 at 21:42
  • $\begingroup$ @Meelo Thanks for the input; I will try to remove symbols when they aren't necessary. $\endgroup$ – Conor O'Brien Jan 3 '15 at 21:46

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.