were looking at infinity x infinity
How many moves does a knight need to get somewhere?
Sort:
n9531l1 wrote:
I just saw a thread about chess on an infinite plain and it reminded me of a problem that was posed some time ago in a different forum. On an infinite chessboard with a marked origin square having coordinates (0,0), what is the smallest number of moves a knight needs to go from the origin to square (x,y), for any given values of x and y? (If a regular board were placed on the infinite board with the a1 square at (0,0), then b4 would be at (1,3), a7 would be at (0,6), e1 would be at (4,0), etc.)
The challenge is to devise a function m(x,y) for the required number of knight moves.
For example, m(2,2)=4, since a knight needs at least four moves to get from a1 to c3, and m(1,1)=2 since a knight can go from a1 to b2 in two moves (remember, it's an infinite board).
I was able to devise a general formula for m(x,y). If someone can do the same, it will be interesting to see how our formulas compare.
The Premise is incorrect - rendering any resulting function moot.
The error lies in the assumption a starting point 0/0 exists on an infinite chessboard, along with several other a priori beliefs.
A cool mind thought experiment, but inserting terms as infinite makes for a sticky-wicket.
I’d would rather suggest a function for a closed system … much easier done. Then see if it can be applied to a +1 system.
Jul 5, 2021
0
#24
StormCentre3 wrote:
n9531l1 wrote:
I just saw a thread about chess on an infinite plain and it reminded me of a problem that was posed some time ago in a different forum. On an infinite chessboard with a marked origin square having coordinates (0,0), what is the smallest number of moves a knight needs to go from the origin to square (x,y), for any given values of x and y? (If a regular board were placed on the infinite board with the a1 square at (0,0), then b4 would be at (1,3), a7 would be at (0,6), e1 would be at (4,0), etc.)
The challenge is to devise a function m(x,y) for the required number of knight moves.
For example, m(2,2)=4, since a knight needs at least four moves to get from a1 to c3, and m(1,1)=2 since a knight can go from a1 to b2 in two moves (remember, it's an infinite board).
I was able to devise a general formula for m(x,y). If someone can do the same, it will be interesting to see how our formulas compare.
The Premise is incorrect - rendering any resulting function moot.
The error lies in the assumption a starting point 0/0 exists on an infinite chessboard, along with several other a priori beliefs.
A cool mind thought experiment, but inserting terms as infinite makes for a sticky-wicket.
I’d would rather suggest a function for a closed system … much easier done. Then see if it can be applied to a larger system.
Umm, you just define the plane as an infinite plane tiled with squares with integer coordinates. Then you just say you'll start at 0,0 because it's convenient. It's done all the time, for example when teaching little kids how to graph lines on the cartesian coordinate system.
In any case it's possible to write a function whose input in a coordinate and output is minimum number of moves for a knight to move there... whether it can be done cleanly / efficiently is another question.
Working with infinite numbers becomes a mathematicians license to create such things as the multi-verse and flying pigs.
Yes - all very convenient.
A Chess board is a Closed System. Is never “infinite”
Jul 5, 2021
0
#26
My first idea of how to approach it is there are a few sets of squares. For example the squares on the same diagonal that are 2 and 4 moves away from the knight are longer than the squares that surround them (harder to reach squares marked with black pawns below).
-
-
My first thought is defining different sets of squares, then writing a function for each.
Jul 5, 2021
0
#27
StormCentre3 wrote:
Working with infinite numbers becomes a mathematicians license to create such things as the multi-verse and flying pigs.
Yes - all very convenient.
It just depends on the application. Infinity isn't a bogyman in math. Practical applications have been around since at least calculus.
It is impractical to approach the problem straight away as a problem that includes infinite functions. Llamas approach is the simplest , most basic and hence the best as it’s workable. 8x8 squares and do the math. Make a proof. It is then easily tested for 16x16. If it fails- then something is wrong with the original premise. If it fits - cont to test towards infinity. But don’t try and start there !
Infinite concepts often are seen unnecessarily convoluting simple problems. They propose any number of solutions with the correct numbers.
StormCentre3 wrote:
The Premise is incorrect - rendering any resulting function moot.
Anyone bothered by the idea of an infinite chess board can make it an n by n board, where n can be as large as desired, say, a googol. Then there need be no concern about the formula being moot.
llama47 wrote:
In any case it's possible to write a function whose input is a coordinate and output is minimum number of moves for a knight to move there... whether it can be done cleanly / efficiently is another question.
Do you consider the BASIC program I gave you to calculate the number to be efficient enough?
PerpetuallyPinned wrote:
Is this what you're referring to?
No.
Mathematician Proves Huge Result on ‘Dangerous’ Problem
By KEVIN HARTNETT
December 11, 2019
Mathematicians regard the Collatz conjecture as a quagmire and warn each other to stay away. But now Terence Tao has made more progress than anyone in decades.
Experienced mathematicians warn up-and-comers to stay away from the Collatz conjecture. It’s a siren song, they say: Fall under its trance and you may never do meaningful work again.
The Collatz conjecture is quite possibly the simplest unsolved problem in mathematics — which is exactly what makes it so treacherously alluring.
“This is a really dangerous problem. People become obsessed with it and it really is impossible,” said Jeffrey Lagarias, a mathematician at the University of Michigan and an expert on the Collatz conjecture.
Earlier this year one of the top mathematicians in the world dared to confront the problem — and came away with one of the most significant results on the Collatz conjecture in decades.
On September 8, Terence Tao posted a proof showing that — at the very least — the Collatz conjecture is “almost” true for “almost” all numbers. While Tao’s result is not a full proof of the conjecture, it is a major advance on a problem that doesn’t give up its secrets easily.
The OP suggests a problem to be solved - similar the Collatz Conjecture. Within the original premise lies the notion of infinite. Quite difficult indeed to make such proofs.
The Collatz conjecture is a conjecture in mathematics that concerns sequences defined as follows: start with any positive integer n. Then each term is obtained from the previous term as follows: if the previous term is even, the next term is one half of the previous term. If the previous term is odd, the next term is 3 times the previous term plus 1. The conjecture is that no matter what value of n, the sequence will always reach 1.
The problem for the OP is to prove the Knights shortest route remains the same as the board increases in size. I propose this is not always the case - as seen on an 8x8.
StormCentre3 wrote:
The problem for the OP is to prove the Knights shortest route remains the same as the board increases in size.
That's not at all what needs to be proved. What needs to be proved is that for a square board centered on the knight's starting point, the length of the shortest knight path to any target square might change as the board size increases up to a point, but there is a finite board size beyond which no size increase can change the length of the shortest path. That's fairly easy to prove.
Let’s assume a formula is devised that works for an 8x8 board. It may well work for 16x16 and 32x32 …
There are two things to consider carefully-
this is a two dimensional problem. The shortest route is linear.
next- the nature of the knight move. For the Knight to reach a destination square, it can be such that closer squares require more moves to be made than further squares.
No trivial matter.
A question becomes of after a formula proves workable for 8x8 - what of a destination square on the perimeter of 9x9 ?
I think perhaps you might begin to see the inherent problem.
I don't see an inherent problem because I'm not interested in either of the formulas you suggested starting with. The task I proposed was to find a formula for a board sufficiently large that no increase in board size would change the length of the shortest path to a given target square. As I said, it's not hard to prove that there is such a finite board size.
are you looking at an 8x8 or an 8x10 board?
No.