Mutilated chessboard problem

https://en.wikipedia.org/wiki/Mutilated_chessboard_problem

by ColinWright • 11 years ago

21 11 11 years ago

en.wikipedia.org

glxc• 11 years ago

"here's another interview brain teaser for sociopathic managers"

wolfgke3• 11 years ago

Rather a simple exercise for a first-semester exercise sheet.

danbruc• 11 years ago

Only if you already know the trick to attack this class of problems.

ap22213• 11 years ago

We solved this as a high school homework problem.

eli173• 11 years ago

I was shown a similar problem (I believe it was originally a Putnam question) which asked if you could cover a chessboard missing one corner with L-shaped triominos, and then asked to prove whether or not you could always cover a 2nx2n board with one corner missing. Neat problem

wolfgke3• 11 years ago

Indeed (spoiler!) an easy, but nice induction proof, which easily can be turned into an algorithm.

Grustaf• 11 years ago

The problem where one square of each is colour is removed is much more interesting. It's not obvious to me why it should always be possible to solve that problem, regardless of which squares are removed, but apparently it is.

I wonder if it can be proved without resorting to looking at classes of cases (removed squares right next to each other, removed squares with two squares between them, etc)?

ColinWright• 11 years ago

Yes - there is a simple, clear, elegant way to see that removing one square of each colour leaves the board coverable. It's even given in the article.

probably_wrong• 11 years ago

I got the correct answer immediately because I've seen a similar problem before in HN, although with a Tetris lamp instead.

Link: http://jackm.co.uk/the-simple-proof-of-the-tetris-lamp/

Discussion: https://news.ycombinator.com/item?id=8870479

Mutilated chessboard problem

Related Stories