1. Joined
    26 Apr '03
    Moves
    25805
    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. Subscribersonhouse
    Fast and Curious
    slatington, pa, usa
    Joined
    28 Dec '04
    Moves
    52724
    10 Jul '11 13:321 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. Joined
    26 Apr '03
    Moves
    25805
    10 Jul '11 15:56
    Yep, 1x2 dominos
  4. Joined
    22 Aug '08
    Moves
    9361
    11 Jul '11 15:471 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. Joined
    22 Aug '08
    Moves
    9361
    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. Joined
    26 Apr '03
    Moves
    25805
    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. Shanghai
    Joined
    16 Feb '06
    Moves
    113360
    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 memberPalynka
    Upward Spiral
    Halfway
    Joined
    02 Aug '04
    Moves
    8702
    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. Shanghai
    Joined
    16 Feb '06
    Moves
    113360
    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. Joined
    26 Apr '03
    Moves
    25805
    24 Jul '11 21:35
    Can anyone state the proof of this formally?
  11. Joined
    22 Aug '08
    Moves
    9361
    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.
Back to Top