4 ms·
I am curious. Are all boards that have equal white and black tiles counts solvable?
by brennanpeterson 5y ago
I am curious. Are all boards that have equal white and black tiles counts solvable?
- mcphage 5y agoNope—consider a black and white square, disconnected. But if they don’t have equal black and white counts, then they’re definitely not solvable.
- deleted 5y ago[deleted]
- Karliss 5y agoSlightly more interesting example which isn't disconnected is a H letter consisting of 8 blocks. 3 blocks high and 2 in the horizontal section.
- dmurray 5y agoYes, by induction. Suppose the total number of squares is 2n. Remove any domino that doesn't disconnect the board, and reduce to the problem for 2n - 2. Alternative proof: no, by example. Consider the shape made up by the X's in XXX .X. .X. XXX (All maths proofs should be presented alongside a proof of the opposite result, to allow the reader to judge which one is likely to have slipped something past you. My favourite presentation following this rule is Mental Poker [0] by the authors of RSA.) [0] https://people.csail.mit.edu/rivest/pubs/SRA81.pdf https://people.csail.mit.edu/rivest/pubs/SRA81.pdf