0
$\begingroup$

There is a chessboard of size $8\times 8$. I am given dominoes of size $1\times 2$ and of a single color (assume, it has a color). It is possible to place a domino on the board so that it covers exactly two squares. I can't place two dominoes on the same square and I can't place a domino so that it is partially off the board.

a) How many ways are there to place a single domino on the board( I place it only horizontally or vertically) My Answer is : 112

b)How many ways are there to place two different dominoes on the board(red domino and blue)? My Answer is : $1024$ (But, I'm not sure at all)

c)How many ways are there to place two blue dominoes on the board? I don't know how to approach to this question. I have started to learn Combinatorics this year, and kind of stuck. Thank you, in advance.

$\endgroup$
  • 2
    $\begingroup$ Why 32? Why 1024? What reasoning led you to those numbers? $\endgroup$ – Arthur Dec 7 '17 at 17:11
1
$\begingroup$

(a) Treat the centers of $64$ chess positions as vertices and join neighboring vertices by edges. There are $112 = 2\times 7 \times 8$ of them. There is a one-one correspondence between possible placement of domino and the edge it covered. This means there are $112$ ways to place a single domino.

(b) Given two different domino positions, they didn't overlap when and only when corresonding edges do not sharing any vertices. After you pick the first edge $e_1$, there are four scenarios for picking the second edge $e_2$:

  • If $e_1$is one of the $8 = 4\times 2$ edges at the corners, let's say $e_1$ is the edge $1$ in diagram below, you cannot pick the $4$ edges colored in red as $e_2$. Otherwise, the two dominos with overlap. This leaves us $112-4$ ways to pick $e_2$.
  • If $e_1$ is the remaining $20 = 4\times 7 - 8$ on the sides, e.g. edge $2$ in diagram below, you cannot pick the $5$ edges colored in orange. This leaves us $112-5$ ways to pick $e_2$.
  • If $e_1$ is one of the $24 = 4 \times 6$ edges adjacent to the sides, eg. edge $3$ in diagram below, you cannot pick the $6$ edges colored in yellow. This leaves us $112-6$ ways to pick $e_2$.
  • Finally, when $e_1$ is one of the remaining $60 = 112-8-20-24$ edges, e.g edge $4$ in diagram below, you cannot pick the $7$ edges colored in green. In this case, there are $112-7$ choices for $e_2$.

Excluded edges

Combine these, we find the number of ways of placing two dominos of different color is $$8(112-4) + 20(112-5)+ 24(112-6)+60(112-7) = 11848$$

(c) Just divide the number from (b) by two. This is because there is a one-two correspondence between placing two dominos of same color and placing two dominos of different color. There are $5924 = 11848/2$ ways to place two domoinos of same color on the chessboard.

$\endgroup$
  • $\begingroup$ Your explanation for b is "too complicated" for me ;( Is there any other ways to approach it? $\endgroup$ – WannaKnow Dec 7 '17 at 18:18
  • $\begingroup$ WannaKnow In this case, I hope a picture worth more than thousand words. $\endgroup$ – achille hui Dec 7 '17 at 19:03
  • $\begingroup$ I almost got it, thank you for your help. But, what is 4x7-8, 4x6, cause for 8 = 2 x 4 (As I understood, it's because we have a 4 corner that can go vertically or horizontally (2 options)), Am I right about it? And, if yes, what about others? $\endgroup$ – WannaKnow Dec 7 '17 at 19:19
  • $\begingroup$ @WannaKnow 1) You are right about the $8$. 2) $4\times 7 - 8$ : there are 4 sides, each sides of seven edges but $8$ of them has be counted before (those attached to corners). 3) $4 \times 6$ : On each side, the are $6$ edges that like edge $3$ in diagram. i.e. one vertex is on the side, another vertex is the interior. $\endgroup$ – achille hui Dec 7 '17 at 19:39
  • $\begingroup$ Thank you so much for your help! I totally got it! Thank you =) $\endgroup$ – WannaKnow Dec 7 '17 at 19:45
0
$\begingroup$

For (a): if the domino is oriented horizontally, its position is determined by the leftmost square it covers, for which there are 7$\cdot$8=56 possibilities (the rightmost file is excluded). Similar for vertical orientation. Thus, there are 2$\cdot$56=112 possibilities in total.

For (b), if the dominoes are distinguishable, and I get 11,848 by going through all the cases (somewhat tedious work). Say we place the red domino first, and without loss it is placed vertically. For each of the 56 possibilities we have to consider how many possibilities for the blue domino are made impossible. Essentially this depends only how close to the boundary we are.

For (c), the answer is half of the answer to (b), as each placement of two blue dominoes corresponds to two different placements of two dominoes which have different colors. The answer is thus 11 848 / 2 = 5 924.

$\endgroup$
  • $\begingroup$ how did you get such number in b and c? $\endgroup$ – WannaKnow Dec 7 '17 at 17:31
  • $\begingroup$ I'll add some more text $\endgroup$ – Reiner Martin Dec 7 '17 at 17:31
  • $\begingroup$ I still don't get how you goot 11848 in b? $\endgroup$ – WannaKnow Dec 7 '17 at 17:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.