0
$\begingroup$

This the problem from the test and I'm stuck at one part.

Matt will arrange four identical, dotless dominoes (shaded 1 by 2 rectangles) on the 5 by 4 grid to the right so that a path is formed from the upper left-hand corner A to the lower right hand corner B. In a path, consecutive dominoes must touch at their sides and not just their corners. No domino may be placed diagonally; each domino covers exactly two of the unit squares shown on the grid. One arrangement is shown. How many distinct arrangements are possible, including the one shown?

Example Picture

So do I just find all the numbers of vertical and horizontal possible and then multiply by the number of arrangements of each, or should I go a different route?

$\endgroup$
  • $\begingroup$ I have no idea what you mean by finding 'all the numbers of vertical and horizontal possible and then multiply' ... can you explain a bit of what you had in mind? $\endgroup$ – Bram28 Dec 10 '17 at 1:15
  • $\begingroup$ Oh I'm sorry, I meant the number of vertically and horizontally placed dominos. $\endgroup$ – The Math Guy Dec 10 '17 at 1:35
1
$\begingroup$

I’m not sure what you had in mind, but here is what I did to get the answer:

The trick here is that the dominos don’t actually restrict the problem much. In fact, any walk from the top left corner to the bottom right corner using only steps to the right and down gives a unique domino path, and vice versa. (I am leaving some of these details out. Showing this bijection isn’t hard, but is a bit technical.)

Thus we need to only count the number of such walks. We can encode such a walk as a sequence of R’s and D’s(right and down steps.) We need to take seven total steps, three to the right, so we get that there are a total of $$\binom{7}{3}=35$$ ways to do this.

$\endgroup$
  • $\begingroup$ +1 for taking into account the shape of the dominoes ... like you said any path can be covered by dominoes, but if the pieces were 1x3 that would no longer be true, so it's good you point this out. $\endgroup$ – Bram28 Dec 10 '17 at 1:38
2
$\begingroup$

You need to traverse $7$ cells (you start from $A$, so that cell is a given). You need to make exactly $3$ movements rightwards in total (otherwise we won't reach point $B$'s x-coordinate).

So we are looking for the number of ways we can order $$rrrdddd$$ where $r$ denotes going right, and $d$ denotes going down.

That gives $$\binom 73 = 35$$ ways.

$\endgroup$
  • $\begingroup$ This was the same as Sean's, but he explained a little bit better, Thank You. $\endgroup$ – The Math Guy Dec 10 '17 at 1:37
0
$\begingroup$

You have to get from A to B using only steps right and down. The number of paths to a given square is the number of paths to the one just above (from which you step down) and the number of paths to the one just to the left (from which you step right). This sounds like Pascal's triangle.

$\endgroup$
0
$\begingroup$

I would consider the cells that you can get at after placing 1,2,3, and 4 dominoes on the way to the lower right.

So, after 1 domino you can be in (1,2) (row 1, column 2), or (2,1), and there is only 1 way to get to each.

After 2 dominoes, you can be in (1,4) (only 1 possibility to get there, through (1,2)), (2,3) (3 ways to get there: 2 via (1,2), and 1 through (2,1)), (3,2) (3), or (4,1) (1)

After 3 dominoes, it's (3,4) (1+2*3+3=10), (4,3) (by symmetry, also 10), or (5,2) (2+3=5)

So, after 4, you have to be in (5,4), and there are 10+2*10+5=35 paths to get there.

Here's a graphic that will help, indicating in how many ways you can get to the various cells:

\begin{array}{|c|c|c|c|} \hline &1&&1\\ \hline 1&&3&\\ \hline &3&&10\\ \hline 1&&10&\\ \hline &5&&35\\ \hline \end{array}

$\endgroup$
  • $\begingroup$ You should get 10+2*10+5=35 after 4. $\endgroup$ – Sean English Dec 10 '17 at 1:32
  • $\begingroup$ @SeanEnglish Yeah, just realized my mistake ... thanks! $\endgroup$ – Bram28 Dec 10 '17 at 1:34
  • $\begingroup$ This was the right answer, but Sean's was a bit faster, sorry. $\endgroup$ – The Math Guy Dec 10 '17 at 1:36
  • $\begingroup$ @TheMathGuy No worries! Sean's answer was more efficient anyway :) I'm more of a visual person though, so the graphic really works for me. $\endgroup$ – Bram28 Dec 10 '17 at 1:40

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.