Knight's Tour: Are there other similar problems?

A section to discuss matters not related to Chess in particular.
Kevin Thurlow
Posts: 2096
Joined: Wed Apr 30, 2008 12:28 pm

Re: Knight's Tour: Are there other similar problems?

Post by Kevin Thurlow » Mon Feb 17, 2014 12:07 pm

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 chess-related puzzles, as did already mentioned Martin Gardner of course.

gxkendall
Posts: 5
Joined: Sat Feb 15, 2014 12:58 pm

Re: Knight's Tour: Are there other similar problems?

Post by gxkendall » Mon Feb 17, 2014 12:17 pm

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

User avatar
Christopher Kreuzer
Posts: 6563
Joined: Fri Aug 06, 2010 2:34 am
Location: London

Re: Knight's Tour: Are there other similar problems?

Post by Christopher Kreuzer » Mon Feb 17, 2014 12:28 pm

Rob Thompson wrote:https://www.amazon.co.uk/Across-Board-M ... 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.
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:

http://www.amazon.co.uk/Mathematics-Che ... 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)?

MartinCarpenter
Posts: 2321
Joined: Tue May 24, 2011 10:58 am

Re: Knight's Tour: Are there other similar problems?

Post by MartinCarpenter » Mon Feb 17, 2014 12:59 pm

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.).

John Foley
Posts: 262
Joined: Thu Oct 15, 2009 9:58 am
Location: Kingston-under-Thames
Contact:

Re: Knight's Tour: Are there other similar problems?

Post by John Foley » Mon Feb 17, 2014 2:24 pm

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.

John McKenna
Posts: 3328
Joined: Tue May 17, 2011 2:02 pm

Re: Knight's Tour: Are there other similar problems?

Post by John McKenna » Mon Feb 17, 2014 3:04 pm

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...
Hi Martin, I did not say "refute ideas like... (Brouwer's)".

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 three-valued logic - similar to Scottish law, where, a verdict is innocent/guilty/unproven - rather than a two-valued 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 two-valued logic (used almost exclusively in maths at least since Euclid) does not reflect the state of physical reality but a three-valued 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 -
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.
I think Professor Kendall would support this appeal as his article in "theconversation" seems aimed towards teaching.
To find a for(u)m that accommodates the mess, that is the task of the artist now. (Samuel Beckett)

MartinCarpenter
Posts: 2321
Joined: Tue May 24, 2011 10:58 am

Re: Knight's Tour: Are there other similar problems?

Post by MartinCarpenter » Mon Feb 17, 2014 3:59 pm

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.).

John McKenna
Posts: 3328
Joined: Tue May 17, 2011 2:02 pm

Re: Knight's Tour: Are there other similar problems?

Post by John McKenna » Mon Feb 17, 2014 5:47 pm

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 one-armed 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)

E Michael White
Posts: 1258
Joined: Fri Jun 01, 2007 6:31 pm

Re: Knight's Tour: Are there other similar problems?

Post by E Michael White » Mon Feb 17, 2014 11:54 pm

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.
Well John after June 30th this year it should be easier. Try these.

Show that:-
  1. 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.
  2. The longest possible games will have approx 8800 moves but no more than 8850.
  3. There will be only a finite number of different games possible.
  4. 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)
The last point was due to be discussed by the FIDE RTR commission but not in that form of question.

I calculated these a bit quickly whilst in the gym, so may be mistaken about some or all of the above !

Alex Holowczak
Posts: 8004
Joined: Sat May 30, 2009 5:18 pm
Location: Oldbury, Worcestershire
Contact:

Re: Knight's Tour: Are there other similar problems?

Post by Alex Holowczak » Tue Feb 18, 2014 4:43 pm

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 a1-a8 journey?

You only need to know one characteristic of the Knight move to work out the answer to both.

Neill Cooper
Posts: 1153
Joined: Sun Feb 24, 2008 4:43 pm
Location: Croydon
Contact:

Re: Knight's Tour: Are there other similar problems?

Post by Neill Cooper » Tue Feb 18, 2014 5:14 pm

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 zig-zag path across the board is a collection of eight white squares, one in each row, which meet at their corners. How many zig-zag paths are there?" http://www.bmoc.maths.org/home/bmo1-2009.pdf

E Michael White
Posts: 1258
Joined: Fri Jun 01, 2007 6:31 pm

Re: Knight's Tour: Are there other similar problems?

Post by E Michael White » Sun Nov 20, 2016 11:18 am

JMcK re infinite or finite number of primes
John 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.
Hello John: Maybe you'll like this one
http://www.johndcook.com/blog/2016/10/3 ... ny-primes/

NickFaulks
Posts: 3452
Joined: Sat Jan 02, 2010 1:28 pm

Re: Knight's Tour: Are there other similar problems?

Post by NickFaulks » Sun Nov 20, 2016 10:09 pm

Isn't this just the normal proof in a very thin disguise?

John McKenna
Posts: 3328
Joined: Tue May 17, 2011 2:02 pm

Re: Knight's Tour: Are there other similar problems?

Post by John McKenna » Sun Nov 27, 2016 5:28 pm

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
To find a for(u)m that accommodates the mess, that is the task of the artist now. (Samuel Beckett)

User avatar
Michael Farthing
Posts: 1380
Joined: Fri Apr 04, 2014 1:28 pm
Location: Morecambe, Europe

Re: Knight's Tour: Are there other similar problems?

Post by Michael Farthing » Sun Nov 27, 2016 5:44 pm

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.

Post Reply