Dominos 2

Is there a way to tile a 6x6 square with dominos so that it is impossible to make a horizonal or vertical cut across the square without slicing a domino?


If not, prove it.

Originally posted by iamatiger
Is there a way to tile a 6x6 square with dominos so that it is impossible to make a horizonal or vertical cut across the square without slicing a domino?


If not, prove it.

Yep, 1x2 dominos

It's definitely impossible to solve. Although I'm still working on a proof.

My conjecture is that it'll be solvable for an nxn grid where the number of dominoes needed to ensure we don't have any possible slices divided by the total grid is less than 1/2

(2x(n-1))/nxn < 1/2

And it's easily solved for n=8,10 etc.
something about needing enough spaces to fill in the rest of the board due to the facts that all the dominoes need to be in pairs.

Actually that kind of is my prove. Every domino placed will need a pair (otherwise you won't be able to fill the board) and there just aren't enough squares on a 6x6 board to allow enough pieces to stop all possible slices AND for each piece to have a pair.

Kind of an informal proof, but the best I can come up with.

Originally posted by VelvetEars
Actually that kind of is my prove. Every domino placed will need a pair (otherwise you won't be able to fill the board) and there just aren't enough squares on a 6x6 board to allow enough pieces to stop all possible slices AND for each piece to have a pair.

Kind of an informal proof, but the best I can come up with.

Isn't there mere fact there are 25 cuts and 18 dominos enough? A domino can only block one cut. If I have not missed anything there should be at least 7 possible cuts.

Originally posted by deriver69
Isn't there mere fact there are 25 cuts and 18 dominos enough? A domino can only block one cut. If I have not missed anything there should be at least 7 possible cuts.

yes it is, it was early in the morning and I misread the original problem as being a cut of each so 5x5 rather than 5+5

Can anyone state the proof of this formally?

Basically the only way I can see to prove it, is to prove the equivalent theorem that in placing dominoes, each must have a pair (another domino in the same configuration on the same row or column) as otherwise it'll be impossible to fill the board completely without leaving gaps.

However, how to prove that eludes me, it looks a bit like a parity problem in group theory, however it's been a couple of years since I studied group theory so I'm not sure I can prove it.

Then again I could be going in completely the wrong direction here and I look forward to being proved wrong.