Please turn on javascript in your browser to play chess.
Posers and Puzzles

Posers and Puzzles

  1. 09 Jul '11 20:28
    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.
  2. Subscriber sonhouse
    Fast and Curious
    10 Jul '11 13:32 / 1 edit
    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.
    In that are we assuming the domino is 1X2? Meaning 18 total domino's?
  3. 10 Jul '11 15:56
    Yep, 1x2 dominos
  4. 11 Jul '11 15:47 / 1 edit
    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.
  5. 11 Jul '11 16:42
    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.
  6. 11 Jul '11 19:55
    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.
    I think that is essentially right! Nice one
  7. Subscriber deriver69
    Keeps
    23 Jul '11 08:11
    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.
  8. Standard member Palynka
    Upward Spiral
    23 Jul '11 09:34
    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.
    Isn't it 10 cuts? 5 horizontal, 5 vertical?
  9. Subscriber deriver69
    Keeps
    23 Jul '11 10:48
    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
  10. 24 Jul '11 21:35
    Can anyone state the proof of this formally?
  11. 24 Jul '11 22:18
    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.