Posers and Puzzles

Posers and Puzzles

  1. Subscriberjoe shmo
    Strange Egg
    podunk, PA
    Joined
    10 Dec '06
    Moves
    7733
    11 May '16 01:00
    I'm stuck on finding approach to eliminate undesirable combinations in the problem below, any help would be appreciated.

    How many ways can a 8x2 rectangle be tiled with 2x1 dominoes such that exactly two of the dominoes are vertical?
  2. Standard memberwolfgang59
    Mr. Wolf
    at home
    Joined
    09 Jun '07
    Moves
    46120
    11 May '16 02:52
    Originally posted by joe shmo
    I'm stuck on finding approach to eliminate undesirable combinations in the problem below, any help would be appreciated.

    How many ways can a 8x2 rectangle be tiled with 2x1 dominoes such that exactly two of the dominoes are vertical?
    Is that 8 columns (positions) where a vertical domino can go?

    Or 2 columns of 8?
  3. Subscriberjoe shmo
    Strange Egg
    podunk, PA
    Joined
    10 Dec '06
    Moves
    7733
    11 May '16 12:38
    Originally posted by wolfgang59
    Is that 8 columns (positions) where a vertical domino can go?

    Or 2 columns of 8?
    8 columns where a vertical domino can be placed.
  4. Standard memberwolfgang59
    Mr. Wolf
    at home
    Joined
    09 Jun '07
    Moves
    46120
    11 May '16 14:07
    Originally posted by joe shmo
    8 columns where a vertical domino can be placed.
    Leftmost domino in position
    1 then second can go in 5 places (not 3 or 7)
    3 then second can go in 3 places (not 5 or 7)
    4 then second can go in 2 places (not 6 or 7)
    5 then second can go in 2 places (not 7)
    6 then second can go in 0 places (not 7 or 8)
    7 then second can go in 1 place (only 8)


    So I make that 13 in total.
  5. Subscriberjoe shmo
    Strange Egg
    podunk, PA
    Joined
    10 Dec '06
    Moves
    7733
    11 May '16 21:17
    Originally posted by wolfgang59
    Leftmost domino in position
    1 then second can go in 5 places (not 3 or 7)
    3 then second can go in 3 places (not 5 or 7)
    4 then second can go in 2 places (not 6 or 7)
    5 then second can go in 2 places (not 7)
    6 then second can go in 0 places (not 7 or 8)
    7 then second can go in 1 place (only 8)


    So I make that 13 in total.
    The answer is 10, so you have a few more to find.

    Correct me if i'm wrong, but your method is somewhat brute force? Is their a way that is mathematically succinct and generalized to any 2*n x 2 rectangle using combinatorics?
  6. Standard memberwolfgang59
    Mr. Wolf
    at home
    Joined
    09 Jun '07
    Moves
    46120
    12 May '16 00:531 edit
    Originally posted by joe shmo
    The answer is 10, so you have a few more to find.

    Correct me if i'm wrong, but your method is somewhat brute force? Is their a way that is mathematically succinct and generalized to any 2*n x 2 rectangle using combinatorics?
    OK. Sober now.
    The answer is n(n+1)/2 for all n.
    (triangle numbers)

    The proof is obvious but difficult to put down .....

    Start by considering that the left most domino is always odd and right most is always even..
  7. Standard memberwolfgang59
    Mr. Wolf
    at home
    Joined
    09 Jun '07
    Moves
    46120
    12 May '16 04:31
    Originally posted by wolfgang59
    OK. Sober now.
    The answer is n(n+1)/2 for all n.
    (triangle numbers)

    The proof is obvious but difficult to put down .....

    Start by considering that the left most domino is always odd and right most is always even..
    Ok.
    n(n+1)/2 is true for n=1
    Now to prove if true for n then true for m=(n+1)

    When we have 2m columns there is ONE additional place for the right most tile for all n positions of the left most tile. In addition there is one more configuration with left most tile in column (m-1) and right most in position m,
    Therefore there are an additional m, or (n+1) configurations.

    Total = n(n+1)/2 + (n+1) = {n(n+1)+2(n+1)}/2
    = (n+1)(n+2)/2 = m(m+1)/2
    QED
  8. SubscriberAThousandYoung
    iViva la Hispanidad!
    tinyurl.com/y2c6j2t3
    Joined
    23 Aug '04
    Moves
    24791
    12 May '16 18:221 edit
    Originally posted by joe shmo
    I'm stuck on finding approach to eliminate undesirable combinations in the problem below, any help would be appreciated.

    How many ways can a 8x2 rectangle be tiled with 2x1 dominoes such that exactly two of the dominoes are vertical?
    Seven. Basically there are four 2x2 squares which each fit two dominoes. Bother must be either vertical or horizontal. So depending on which of those four squares you put the vertical dominoes you can have four possibilities.

    You can also have one vertical one on each end. So five.

    Or one vertical, two horizontal, one vertical, four horizontal. That's six.

    Or one vertical, four horizontal, vertical, two horizontal. Seven.
  9. Subscriberjoe shmo
    Strange Egg
    podunk, PA
    Joined
    10 Dec '06
    Moves
    7733
    12 May '16 21:182 edits
    Originally posted by AThousandYoung
    Seven. Basically there are four 2x2 squares which each fit two dominoes. Bother must be either vertical or horizontal. So depending on which of those four squares you put the vertical dominoes you can have four possibilities.

    You can also have one vertical one on each end. So five.

    Or one vertical, two horizontal, one vertical, four horizontal. That's six.

    Or one vertical, four horizontal, vertical, two horizontal. Seven.
    The answer is 10...so your missing a few.
  10. Subscriberjoe shmo
    Strange Egg
    podunk, PA
    Joined
    10 Dec '06
    Moves
    7733
    12 May '16 22:00
    Originally posted by wolfgang59
    Ok.
    n(n+1)/2 is true for n=1
    Now to prove if true for n then true for m=(n+1)

    When we have 2m columns there is ONE additional place for the right most tile for all n positions of the left most tile. In addition there is one more configuration with left most tile in column (m-1) and right most in position m,
    Therefore there are an additional m, or (n ...[text shortened]... configurations.

    Total = n(n+1)/2 + (n+1) = {n(n+1)+2(n+1)}/2
    = (n+1)(n+2)/2 = m(m+1)/2
    QED
    Are there any methods in combinatorics that you know of that can be used to eliminate combinations of the remaining un-chosen columns?; That is removing combinations for which any two of the un-chosen columns are not adjacent?
Back to Top