Knight's Tour: Are there other similar problems?

 Posts: 3189
 Joined: Wed Apr 30, 2008 12:28 pm
Re: Knight's Tour: Are there other similar problems?
I have a couple of Dover reprints of mathematical puzzles and games, (I think by Henry Dudeney) which I will look at soon. Also Sam Loyd did a number of chessrelated puzzles, as did already mentioned Martin Gardner of course.
Re: Knight's Tour: Are there other similar problems?
All
Sorry, I did not post this in Chess as I thought it might upset some people, who wanted to discuss "pure chess". As I said newbie .
But enjoying the thread.
Graham
Sorry, I did not post this in Chess as I thought it might upset some people, who wanted to discuss "pure chess". As I said newbie .
But enjoying the thread.
Graham
 Christopher Kreuzer
 Posts: 7447
 Joined: Fri Aug 06, 2010 2:34 am
 Location: London
Re: Knight's Tour: Are there other similar problems?
Some might say this really isn't anything to do with chess... The book Rob pointed out above looks very interesting. I noticed on Amazon another book in a similar vein:Rob Thompson wrote:https://www.amazon.co.uk/AcrossBoardM ... 0691154988 is a book detailing knights tourns on n*m boards, as well of boards with different topologies (spheres, toroids, Klein bottles etc.). I recall the maths being not entirely trivial as presented, but that was a few years ago and I've developed considerably as a mathematician since then so that may not be an accurate perception.
http://www.amazon.co.uk/MathematicsChe ... 0486294323
Anyone able to recommend that one or say any more about either book or recommend other books of this nature (I know about the excellent Smullyan books already, but not much more than that)?

 Posts: 2456
 Joined: Tue May 24, 2011 10:58 am
Re: Knight's Tour: Are there other similar problems?
You can't really refute ideas like the ones Brouwer suggested because in the end its just another way to build the formal system It is a terribly limiting way to behave though. All sorts of wonderful ideas either have to be cut out or become terribly hard to prove. Never that likely to appeal.
Well if N dimensional boards of artbitary size/topology are non chess, and they do gets just a bit difficult to play quite quickly!, then lets generalise the pieces instead. After all camels (3,1 leapers) can make for fun chess.
A knight is a 2,1 leaper, a (step mover) bishop a 1,1 etc. What about working out which N,M leapers will be able to fully tour an X by Y board. 1,0 leapers are of course an easy start And anything with an even sum almost as obviously can't. The rest?
(There may well be a solution to this already, I don't know.).
Well if N dimensional boards of artbitary size/topology are non chess, and they do gets just a bit difficult to play quite quickly!, then lets generalise the pieces instead. After all camels (3,1 leapers) can make for fun chess.
A knight is a 2,1 leaper, a (step mover) bishop a 1,1 etc. What about working out which N,M leapers will be able to fully tour an X by Y board. 1,0 leapers are of course an easy start And anything with an even sum almost as obviously can't. The rest?
(There may well be a solution to this already, I don't know.).

 Posts: 296
 Joined: Thu Oct 15, 2009 9:58 am
 Location: KingstonuponThames
 Contact:
Re: Knight's Tour: Are there other similar problems?
It requires hard work and patience to create new puzzles around chess and mathematics  especially to make them suitable for a school audience. CSC is developing material for educational purposes for younger age groups. We are familiar with all that's published but this is not enough. So if the creative amongst you can come up with genuine maths/chess puzzles, we would be very interested.

 Posts: 3862
 Joined: Tue May 17, 2011 2:02 pm
Re: Knight's Tour: Are there other similar problems?
Hi Martin, I did not say "refute ideas like... (Brouwer's)".MartinCarpenter wrote:You can't really refute ideas like the ones Brouwer suggested because in the end its just another way to build the formal system It is a terribly limiting way to behave though. All sorts of wonderful ideas either have to be cut out or become terribly hard to prove. Never that likely to appeal. Well...
I used 'position'  Hilbert (the Formalist) and others tried to refute Brouwer's (the Intuitionist) position.
Brouwer's position regarding mathemetical logic was, in a nutshell, a threevalued logic  similar to Scottish law, where, a verdict is innocent/guilty/unproven  rather than a twovalued logic  similar to English law only innocent/guilty.
It could be said that the rise of quantum theory in physics, at about the time Brouwer was formulating his mathematical ideas, in some way supports the idea that the twovalued logic (used almost exclusively in maths at least since Euclid) does not reflect the state of physical reality but a threevalued one  allowing for indeterminacy  does. Brouwer warned that in mathematics those who built their structures on the old logic risked creating imaginary ones that had no real basis in a more objective mathematical reality.
As you wrote, "all sorts of wonderful ideas either have to be cut out..." Those "wonderful ideas" were to him not real mathematical entities but exotic dreams. In his mathematics less was more  more satisfying of reality.
Of course, such a view is, as you wrote, "never that likely to appeal." To the many that is.
He had his followers and an 'Intuitionist' school arose and may not yet be completely dead.
But all that is not chess so...
Back to chess (in which there are intuitionists & formalists)
Working forwards from (a list of mathematicians who have studied chess) 
http://en.wikipedia.org/wiki/Chess_and_mathematics
We find near the end in the external links 
http://www.velucchi.it/mathchess
Where this can be found (middle slightly to the right)  among other interesting things 
http://www.velucchi.it/mathchess/knight.htm
Which brings us back to the N's tour where, thanks to Professor Kendall, we started.
Not quite 
I think Professor Kendall would support this appeal as his article in "theconversation" seems aimed towards teaching.John Foley wrote:It requires hard work and patience to create new puzzles around chess and mathematics  especially to make them suitable for a school audience. CSC is developing material for educational purposes for younger age groups. We are familiar with all that's published but this is not enough. So if the creative amongst you can come up with genuine maths/chess puzzles, we would be very interested.
To find a for(u)m that accommodates the mess, that is the task of the artist now. (Samuel Beckett)

 Posts: 2456
 Joined: Tue May 24, 2011 10:58 am
Re: Knight's Tour: Are there other similar problems?
Position then. In the end its a subjective judgement about what constitutes 'real' maths and people do like their toys I'd be surprised if it has died completely because its still an interesting enough theoretical exercise seeing how much you can do with one hand tied behind your back.
As for puzzles, I'm not sure. The one I can think of is contructing systematic mating net techniques, not maths as such that, but it is methodological problem solving I guess not unrelated to computer programming/algorithm work.
Some very easy of course  although actually K&R isn't a terrible problem if they've not been taught it before. K&B&N rather scary of course!
Also some reasonably nice problems with fairy pieces. 2 Kings vs 1 say, or combining a knight with a 3,1 leaper and maybe a bishop, etc. I spent a bit of time at school toying with this sort of thing. As I remember you maybe can mate with a piece combining a knight and 3,1 leaper into one piece but it isn't trivial. Print the pieces out like western shogi pieces to keep track of what they can do.
(You may need the bishop or some step moves thrown in too.).
As for puzzles, I'm not sure. The one I can think of is contructing systematic mating net techniques, not maths as such that, but it is methodological problem solving I guess not unrelated to computer programming/algorithm work.
Some very easy of course  although actually K&R isn't a terrible problem if they've not been taught it before. K&B&N rather scary of course!
Also some reasonably nice problems with fairy pieces. 2 Kings vs 1 say, or combining a knight with a 3,1 leaper and maybe a bishop, etc. I spent a bit of time at school toying with this sort of thing. As I remember you maybe can mate with a piece combining a knight and 3,1 leaper into one piece but it isn't trivial. Print the pieces out like western shogi pieces to keep track of what they can do.
(You may need the bishop or some step moves thrown in too.).

 Posts: 3862
 Joined: Tue May 17, 2011 2:02 pm
Re: Knight's Tour: Are there other similar problems?
MartinCarpenter>...I'd be surprised if it (Intuitionism) has died completely because its still an interesting enough theoretical exercise seeing how much you can do with one hand tied behind your back.<
Of course, it's not just a 'theoretical exercise' if in reality (of both physics and mathematics) we are all just onearmed bandits with imaginary other hands.
Of course, it's not just a 'theoretical exercise' if in reality (of both physics and mathematics) we are all just onearmed bandits with imaginary other hands.
To find a for(u)m that accommodates the mess, that is the task of the artist now. (Samuel Beckett)

 Posts: 1345
 Joined: Fri Jun 01, 2007 6:31 pm
Re: Knight's Tour: Are there other similar problems?
Well John after June 30th this year it should be easier. Try these.John Foley wrote:It requires hard work and patience to create new puzzles around chess and mathematics  especially to make them suitable for a school audience.
Show that:
 Each game can only have a finite number of moves, even with player collusion, whereas before 1 July there could be an infinite number of moves.
 The longest possible games will have approx 8800 moves but no more than 8850.
 There will be only a finite number of different games possible.
 In the longest possible games, of which there are many, they will be drawn or Black will win. (ed. not sure about this last one now)
I calculated these a bit quickly whilst in the gym, so may be mistaken about some or all of the above !

 Posts: 9085
 Joined: Sat May 30, 2009 5:18 pm
 Location: Oldbury, Worcestershire
 Contact:
Re: Knight's Tour: Are there other similar problems?
A simple puzzle I like to use when teaching primary school children how a Knight moves.
A Knight starts on a1. It moves to h8. Does it need to make an odd number of moves, or an even number of moves? What about the a1a8 journey?
You only need to know one characteristic of the Knight move to work out the answer to both.
A Knight starts on a1. It moves to h8. Does it need to make an odd number of moves, or an even number of moves? What about the a1a8 journey?
You only need to know one characteristic of the Knight move to work out the answer to both.

 Posts: 1240
 Joined: Sun Feb 24, 2008 4:43 pm
 Location: Croydon
 Contact:
Re: Knight's Tour: Are there other similar problems?
In reply to John Foley rather than Graham's original post:
We use 'how many squares on a chessboard' as a year 9 investigation (one has to include 2 by 2 etc squares);
We use the 8 queens problem on open evenings;
I use the number of grains of rice on a chess board (1, 2, 4, 8 etc) as part of my Royal Institution year 9 maths masterclass; It can also an example of geometric sequence in the sixth form.
There is the "remove opposite corners or a chess board  can you now place 31 dominoes each covering 2 adjacent squares" problem which is provides a way to discuss proof with older secondary school pupils
The following appeared in the British Maths Olympiad in 2008: "Consider a standard 8 Ã— 8 chessboard consisting of 64 small squares coloured in the usual pattern, so 32 are black and 32 are white. A zigzag path across the board is a collection of eight white squares, one in each row, which meet at their corners. How many zigzag paths are there?" http://www.bmoc.maths.org/home/bmo12009.pdf
We use 'how many squares on a chessboard' as a year 9 investigation (one has to include 2 by 2 etc squares);
We use the 8 queens problem on open evenings;
I use the number of grains of rice on a chess board (1, 2, 4, 8 etc) as part of my Royal Institution year 9 maths masterclass; It can also an example of geometric sequence in the sixth form.
There is the "remove opposite corners or a chess board  can you now place 31 dominoes each covering 2 adjacent squares" problem which is provides a way to discuss proof with older secondary school pupils
The following appeared in the British Maths Olympiad in 2008: "Consider a standard 8 Ã— 8 chessboard consisting of 64 small squares coloured in the usual pattern, so 32 are black and 32 are white. A zigzag path across the board is a collection of eight white squares, one in each row, which meet at their corners. How many zigzag paths are there?" http://www.bmoc.maths.org/home/bmo12009.pdf

 Posts: 1345
 Joined: Fri Jun 01, 2007 6:31 pm
Re: Knight's Tour: Are there other similar problems?
JMcK re infinite or finite number of primes
http://www.johndcook.com/blog/2016/10/3 ... nyprimes/
Hello John: Maybe you'll like this oneJohn McKenna wrote: EMW>"Euclid would not be happy you dismiss his proof..."
JMcK <I am not the only one. For it is a proof NOT universally acknowledged... for it must be in want of a contradiction.In 1923 L. E. J. Brouwer 'dismissed' such proofs as unsound and proposed a different basis for mathematical logic. Not a position that has ever been very popular but one that has not been refuted. At least not to my knowledge that is. Being a bit of a maverick I quite like his ideas.
http://www.johndcook.com/blog/2016/10/3 ... nyprimes/

 Posts: 5300
 Joined: Sat Jan 02, 2010 1:28 pm
Re: Knight's Tour: Are there other similar problems?
Isn't this just the normal proof in a very thin disguise?E Michael White wrote: http://www.johndcook.com/blog/2016/10/3 ... nyprimes/

 Posts: 3862
 Joined: Tue May 17, 2011 2:02 pm
Re: Knight's Tour: Are there other similar problems?
E Michael, thank you, I like the brevity of the proof you provided in the above link, but have to agree with Nick  it is another proof by contradiction.
Here's one without 
http://math.stackexchange.com/questions ... tradiction
Here's one without 
http://math.stackexchange.com/questions ... tradiction
To find a for(u)m that accommodates the mess, that is the task of the artist now. (Samuel Beckett)
 Michael Farthing
 Posts: 1847
 Joined: Fri Apr 04, 2014 1:28 pm
 Location: Morecambe, Europe
Re: Knight's Tour: Are there other similar problems?
OK John let us reword the standard proof slightly to deal with your sensibilities:
Consider the list of all known primes and take their product plus one. This is not divisible by any known prime and therefore is either prime itself, or divisible by some other prime which is as yet undiscovered. Hence a prime number always exists that has not yet been discovered.
No contradiction there! We have not claimed to be working with a complete set of primes.
Of course, I am of the view that deductive proof is invalid and that the only correct method of proof is by establishing a contradiction: not a widely held view but, IMHO, as reasonable as Nick's and your position (which in your case I suspect is probably purely mischievous  using that word with its gentler, tolerant and, dare I say it, affectionate* meaning).
*This does not imply any let up in our battles: a bit like Peppino and Don Camillo.
Consider the list of all known primes and take their product plus one. This is not divisible by any known prime and therefore is either prime itself, or divisible by some other prime which is as yet undiscovered. Hence a prime number always exists that has not yet been discovered.
No contradiction there! We have not claimed to be working with a complete set of primes.
Of course, I am of the view that deductive proof is invalid and that the only correct method of proof is by establishing a contradiction: not a widely held view but, IMHO, as reasonable as Nick's and your position (which in your case I suspect is probably purely mischievous  using that word with its gentler, tolerant and, dare I say it, affectionate* meaning).
*This does not imply any let up in our battles: a bit like Peppino and Don Camillo.
Rejoiner