News for hackers. Stuff that matters.
Re:Mutilated chessboard problem by Grustaf on Sunday October 04, 2015 @04:55PM (#10328774)
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)?

Re:Mutilated chessboard problem by ColinWright on Sunday October 04, 2015 @04:56PM (#10328781)
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.
Re:Mutilated chessboard problem by probably_wrong on Sunday October 04, 2015 @06:09PM (#10329030)
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

Re:Mutilated chessboard problem by eli173 on Sunday October 04, 2015 @04:20PM (#10328664)
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
Re:Mutilated chessboard problem by wolfgke on Sunday October 04, 2015 @04:21PM (#10328668)
Indeed (spoiler!) an easy, but nice induction proof, which easily can be turned into an algorithm.
Re:Mutilated chessboard problem by glxc on Sunday October 04, 2015 @03:58PM (#10328597)
"here's another interview brain teaser for sociopathic managers"
Re:Mutilated chessboard problem by wolfgke on Sunday October 04, 2015 @04:20PM (#10328665)
Rather a simple exercise for a first-semester exercise sheet.
Re:Mutilated chessboard problem by danbruc on Sunday October 04, 2015 @04:38PM (#10328725)
Only if you already know the trick to attack this class of problems.
Re:Mutilated chessboard problem by wolfgke on Sunday October 04, 2015 @05:09PM (#10328836)
No, it's really that easy: Clearly the complete coverings with dominoes biject to matchings of the graph with vertices = squares and edges defined by 2-sets of squares sharing an edge on the chessboard. Clearly this graph is bipartite, but the two elements of the bipartision are of different cardinality. Thus no perfect matching can exist.
Re:Mutilated chessboard problem by semi-extrinsic on Sunday October 04, 2015 @04:58PM (#10328794)
Really? Just by looking at the figure, bruteforcing for a couple of minutes and then noticing a solution which gives the same problem but 6x6 instead of 8x8, I was able to solve this without even pen and paper. Unless you're talking about an extremely abstract class of problems, I don't think that statement is true.
Re:Mutilated chessboard problem by ap22213 on Monday October 05, 2015 @12:17AM (#10329943)
We solved this as a high school homework problem.