Problem of the Week 1154

The Wandering Bishop

MacPOW Home || Math Forum POWs || Search MacPOW

Solution Notes

Wagon received one solution — from Joseph DeVincentis, who settled the whole problem. Because they have submitted this to a journal, the full solution will not appear here.

Note that the Bishop's graph B(m,n) (m ≤ n) is Hamiltonian except where there is a simple proof that it is not: i.e., in all cases except B(1,n), B(2,n), and B(3,3). The open question as to which B(m,n) are Hamilton connected is unsolved. Wagon conjectures that it is true in all cases except B(2,n), B(3,n), and B(4,4).

One variation of this problem has appeared online, and it concerns the graph of the slow bishop (John Sullivans's suggested name), one that can move only one square along a diagonal in each move. Results for that case can be found at http://users.etown.edu/s/sanchisgr/Papers/bishops.pdf.

[Back to Problem 1154]

© Copyright 2012 Stan Wagon. Reproduced with permission.