# Domino tile possibilities

I own a normal domino game with 28 tiles. Each tile carries two of the numbers [0, 1, 2, 3, 4, 5, 6] (where 0 represents blank).

During cleanup five pieces fell out of the box. Two of them showed their backside. How big is the chance that you can arrange these five pieces into a valid domino line?

One valid example of such a line: [2,5] [5,0] [0,3] [3,4] [4,4]

• When you say "valid domino line", are you accounting for doubles, which would cause a fork instead of a single line? i.e. [2, 5], [5, 5], [5, 0], [2, 5], [5, 5], [5, 4], [4, 4] Mar 11 '16 at 15:11
• @IanMacDonald no forks, just one complete single line with exactly these pieces Mar 11 '16 at 16:52
• Do you consider a fork that only extends off one edge a fork or a single line? For example: [5, 2] [2, 4] [4, 4] [4, 0] [0, 5] would fork on the middle [4, 4], but only extends in one direction. Is that a valid line? Mar 11 '16 at 16:56
• @IanMacDonald Yes [5, 2] [2, 4] [4, 4] [4, 0] [0, 5] is valid Mar 11 '16 at 16:59

This is a rather inelegant, brute-force way of solving it, but I think it works.

30/300 = 10%.

Consider a graph with its vertices labelled 0 to 6. A given domino tile connects two vertices in this graph (not necessarily distinct vertices, either; the double-4 domino connects vertex #4 to itself.) A line of dominoes will correspond to a path in this graph. Finally, we can only have one line connecting any pair of vertices (again, not necessarily distinct vertices), since a standard set of dominoes only contains one of each tile.

Now, the dominoes that are exposed when they fell out of the box are connecting the following vertices:

We wish to find how many ways there are to select two more edges in this graph such that the resulting subgraph forms a path in the graph. Note that this implies that the resulting subgraph can have at most two vertices with odd degree (shout-out to Euler.) We can break this down into sub-cases:

1. The resulting subgraph contains only the vertices (0, 2, 4, 5). The ways that we can do this are as follows:

(a) Vertex 4 is connected to Vertex 0 only. Then Vertices 2 and 4 will have odd degree, and Vertices 0 and 5 have even degree. The remaining edge must either connect a vertex with odd degree to a vertex with even degree, or connect a vertex to itself. (In principle we could also connect two vertices of odd degree, but we already said that there was only one edge to Vertex 4.) For the first case, we can only connect (2,0), since (2,5) is already taken; for the second case, we can connect (0,0), (2,2), or (5,5). So there are 4 options in this case. (Note that my first answer for this case was wrong, and I didn't realize it until I closely examined @Marius's table of results.)

(b) Vertex 4 is connected to Vertex 2 only. The above logic still holds, with the roles of Vertex 0 and Vertex 2 swapped. So there are 4 options in this case as well.

(c) Vertex 4 is attached to Vertex 5 only. Then all four vertices have odd degree, and the remaining edge must connect two distinct vertices. The only way left to do this is to attach Vertex 0 to Vertex 2 (by assumption, Vertex 4 is not attached to any of the others, and the only edge left to choose is the edge between Vertices 0 and 2.) So there is 1 option in this case.

(d) Vertex 4 is attached to both Vertices 0 and 2. This is one more valid option, and there are no other choices to make.

(e) Vertex 4 is attached to both Vertices 0 and 5. This is one more valid option, and there are no other choices to make.

(f) Vertex 4 is attached to both Vertices 2 and 5. This is one more valid option, and there are no other choices to make.

2. The resulting graph contains one of the remaining vertices (1, 3, 6). It cannot contain more than one such vertex, since this would necessarily result in a disconnected graph. Let us denote this new vertex by x. We can distinguish then between the following cases:

(a) Vertex x has degree 2. Then one of the two edges attached to x must go to Vertex 4 (since otherwise it will be disconnected) and the other must go to one of Vertices 0 or 2. (As pointed out by @Trenin in the comments, it cannot go to Vertex 5, since this would result in four vertices with odd degree). Thus, there are two options for each value of x, or a total of six options.

(b) Vertex x has degree 1. We can then distinguish between two sub-sub-cases:

(i) Vertex x is connected to Vertex 4. Then Vertex 4 will have odd degree, and so must be connected to another vertex of odd degree, which must be Vertex 0 or Vertex 2. So there are two options for each value of x, or six more options.

(ii) Vertex x is connected to Vertex 0 or 2. Then Vertex 4 must be connected to the other one of those two vertices. (Otherwise, there will be four vertices with odd degree.) Thus, we have two more options for each value of x, or six more options.

(iii) Vertex x is connected to Vertex 5. At this point, we have four vertices with odd degree (0, 2, 5, x), and since we must also connect Vertex 4 to the rest of the graph, we cannot reduce the number of odd-degree vertices with our remaining edge. So this option doesn't work at all.

So, summing up: there are $4 + 4 + 1 + 1 + 1 + 1 + 6 + 6 + 6 = 30$ ways to choose these two dominoes such that they form a connected path in this graph. Since there are 25 unspecified dominoes in the set, there are $25 \times 24/2 = 300$ ways to choose two of them. Thus, the chance of being able to assemble these into a line is 30/300 = 10%.

.

For the record, the options for domino choices are: (4,0) & (2,2); (4,0) & (2,0); (4,0) & (0,0); (4,0) & (5,5); (4,2) & (0,0); (4,2) & (2,0); (4,2) & (2,2); (4,2) & (5,5); (4,5) & (0,2); (4,0) & (4,2); (4,0) & (4,5); (4,2) & (4,5); (4,x) & (0,x); (4,x) & (2,x); (4,x) & (4,0); (4,x) & (4,2); (0,x) & (2,4); and (2,x) & (0,4). Throughout, x stands for 1, 3, or 6.

• 2a you say that one edge connects x to 4, leaving the other edge between x and 2, x and 5, or x and 0. However, if you connect x to 5 there will be 4 odd vertices and Euler says you can only have 2. Mar 11 '16 at 16:02
• 2bi If vertex x is connected to 4 the you don't have to make 4 even. Instead, you can connect 0 and 2, leaving only 1 and 4 odd. Mar 11 '16 at 16:03
• You either misspelled a digit or did the wrong math for 2+2+1+1+1+1+9+6+6 Mar 11 '16 at 16:03
• @Trenin: Good point on case 2(a); I've edited my answer appropriately. On case 2(b)(i), adding both (4,x) and (0,2) will result in a disconnected graph, so that doesn't work. Mar 11 '16 at 16:28
• @MichaelSeifert Yes, you are right about the disconnected graph. Mar 11 '16 at 16:52

$10%$

because

Henceforth the notation 2 $|$ 5-5 $|$   refers to the event that piece 2 $|$ 5 is joined to 5 $|$  . the notation 2 $|$  ' refers to a "reduced" piece, for example 2 $|$ 5-5 $|$   effectively can be considered as a single 2 $|$  ' piece, as long as we bear in mind that the actual 2 $|$   piece hasn't been used. The notation 2 $|$ * refers to anything containing a 2. square brackets enclose a set of pieces that need to be joined.
Since there's a 4 $|$ 4 piece, at least one of the face down pieces needs to have a 4. Call this piece $D$. Consider each possibility for $D$:

$D=$4 $|$  .

• If 2 $|$ 5-5 $|$  , then we have $[$4 $|$  ', 2 $|$  ',$E]$.

• If 4 $|$  '-2 $|$  ', then $E$ can be 2 $|$ * or 4 $|$ *, barring already used pieces.
• If not 2 $|$ 5-5 $|$  , then it must be that 4 $|$  '-  $|$ 5, therefore 4 $|$ 5' and 5 $|$ 2 need to be joined but not on the fives. This can be done with 4 $|$ 5,4 $|$ 2,5 $|$ 5.

Joining the 2 sets we get:

2 $|$  ,2 $|$ 1,2 $|$ 2,2 $|$ 3,2 $|$ 4,2 $|$ 6,4 $|$ 1,4 $|$ 2,4 $|$ 3,4 $|$ 5,4 $|$ 6,  $|$  ,5 $|$ 5

$D=$4 $|$ 1.

• If 2 $|$ 5-5 $|$  , then $[$4 $|$ 1',2 $|$  ',$E]$. The first 2 of these have no numbers in common, therefore new solutions are 4 $|$ 2,1 $|$ 2,1 $|$  .
Note that I don't include 4 $|$  , as that would be a repeat of a solution already counted in $D=$4 $|$  , therefore is not new.

• If not 2 $|$ 5-5 $|$  , there are no solutions.

$D=$4 $|$ 2.

• If 2 $|$ 5-5 $|$  , then we have $[$4 $|$ 2',2 $|$  ',$E]$.

• If 4 $|$ 2'-2 $|$  ', then any new, not used 4 $|$ * or   $|$ * will suffice. These are 4 $|$ 3,4 $|$ 5,4 $|$ 6,  $|$ 1,  $|$ 2,  $|$ 3,  $|$ 6.

• If not 4 $|$ 2'-2 $|$  ' then solutions are 2 $|$ 2,2 $|$  .

• If not 2 $|$ 5-5 $|$  , then solutions are 4 $|$ 5,5 $|$ 5.

Joining the 2 sets we get:

4 $|$ 3,4 $|$ 5,4 $|$ 6,  $|$ 1,  $|$ 2,  $|$ 3,  $|$ 6,5 $|$ 5,2 $|$ 2

$D=$4 $|$ 3.

• If 2 $|$ 5-5 $|$  , then we have $[$4 $|$ 3',2 $|$  ',$E]$. Solutions are 3 $|$ 2,3 $|$  .

• If not 2 $|$ 5-5 $|$  , then $[$4 $|$ 3',5 $|$ 2,5 $|$  ,$E]$ has no new solutions.

$D=$4 $|$ 5.

• If 2 $|$ 5-5 $|$  , then $[$4 $|$ 5',2 $|$  ',$E]$. No new solutions.

• If not 2 $|$ 5-5 $|$  , then $[$4 $|$ 5',5 $|$ 2,5 $|$  ,$E]$.

• If 5 $|$  -5 $|$ 4', then the only new solution to $[$  $|$ 4',5 $|$ 2,$E]$ is   $|$ 2.

• If 4 $|$ 5'-5 $|$ 2, no new sols.

$D=$4 $|$ 6.

• If 2 $|$ 5-5 $|$  , then $[$2 $|$  ',4 $|$ 6',$E]$ has new solutions 2 $|$ 6,  $|$ 6.

• Otherwise, no new solutions.

Counting the bold dominoes I get $30$. ${25\choose2} = 300$, therefore the probability is $\frac{30}{300} = 0.1$. Unless I've messed up somewhere.

• I think you missed the case (4,2) and (0,0). Mar 11 '16 at 15:45
• @astralfenix Thanks for this post. Now I've been forced to figure out how you did that, which lead me to this post, which has me cracking up. Mar 11 '16 at 21:05

So for the fun of it here it is "the long way around":

0 = chain not possible
1 = chain formed
X = cannot have this combination

      [0,0]||[0,1]||[0,2]||[0,3]||[0,4]||[0,5]||[0,6]||[1,1]||[1,2]||[1,3]||[1,4]||[1,5]||[1,6]||[2,2]||[2,3]||[2,4]||[2,5]||[2,6]||[3,3]||[3,4]||[3,5]||[3,6]||[4,4]||[4,5]||[4,6]||[5,5]||[5,6]||[6,6]
[0,0]|  X  |
[0,1]|  0  ||  X  |
[0,2]|  0  ||  0  ||  X  |
[0,3]|  0  ||  0  ||  0  ||  X  |
[0,4]|  1  ||  0  ||  1  ||  0  ||  X  |
[0,5]|  X  ||  X  ||  X  ||  X  ||  X  ||  X  |
[0,6]|  0  ||  0  ||  0  ||  0  ||  0  ||  X  ||  X  |
[1,1]|  0  ||  0  ||  0  ||  0  ||  0  ||  X  ||  0  ||  X  |
[1,2]|  0  ||  0  ||  0  ||  0  ||  1  ||  X  ||  0  ||  0  ||  X  |
[1,3]|  0  ||  0  ||  0  ||  0  ||  0  ||  X  ||  0  ||  0  ||  0  ||  X  |
[1,4]|  0  ||  1  ||  0  ||  0  ||  1  ||  X  ||  0  ||  0  ||  1  ||  0  ||  X  |
[1,5]|  0  ||  0  ||  0  ||  0  ||  0  ||  X  ||  0  ||  0  ||  0  ||  0  ||  0  ||  X  |
[1,6]|  0  ||  0  ||  0  ||  0  ||  0  ||  X  ||  0  ||  0  ||  0  ||  0  ||  0  ||  0  ||  X  |
[2,2]|  0  ||  0  ||  0  ||  0  ||  1  ||  X  ||  0  ||  X  ||  0  ||  0  ||  0  ||  0  ||  0  ||  X  |
[2,3]|  0  ||  0  ||  0  ||  0  ||  1  ||  X  ||  0  ||  0  ||  0  ||  0  ||  1  ||  1  ||  0  ||  0  ||  X  |
[2,4]|  1  ||  1  ||  1  ||  1  ||  1  ||  X  ||  1  ||  0  ||  0  ||  0  ||  1  ||  0  ||  0  ||  1  ||  0  ||  X  |
[2,5]|  X  ||  X  ||  X  ||  X  ||  X  ||  X  ||  X  ||  X  ||  X  ||  X  ||  X  ||  X  ||  X  ||  X  ||  X  ||  X  ||  X  |
[2,6]|  0  ||  0  ||  0  ||  0  ||  1  ||  X  ||  0  ||  0  ||  0  ||  0  ||  0  ||  0  ||  0  ||  0  ||  0  ||  0  ||  X  ||  X  |
[3,3]|  0  ||  0  ||  0  ||  0  ||  0  ||  X  ||  0  ||  0  ||  0  ||  0  ||  0  ||  0  ||  0  ||  0  ||  0  ||  0  ||  X  ||  0  ||  X  |
[3,4]|  0  ||  0  ||  0  ||  1  ||  1  ||  X  ||  0  ||  0  ||  0  ||  0  ||  0  ||  0  ||  0  ||  0  ||  1  ||  1  ||  X  ||  0  ||  0  ||  X  |
[3,5]|  0  ||  0  ||  0  ||  0  ||  0  ||  X  ||  0  ||  0  ||  0  ||  0  ||  0  ||  0  ||  0  ||  0  ||  0  ||  0  ||  X  ||  0  ||  0  ||  0  ||  X  |
[3,6]|  0  ||  0  ||  0  ||  0  ||  0  ||  X  ||  0  ||  0  ||  0  ||  0  ||  0  ||  0  ||  0  ||  0  ||  0  ||  0  ||  X  ||  0  ||  0  ||  0  ||  0  ||  X  |
[4,4]|  X  ||  X  ||  X  ||  X  ||  X  ||  X  ||  X  ||  X  ||  X  ||  X  ||  X  ||  X  ||  X  ||  X  ||  X  ||  X  ||  X  ||  X  ||  X  ||  X  ||  X  ||  X  ||  X  |
[4,5]|  0  ||  0  ||  1  ||  0  ||  1  ||  X  ||  0  ||  0  ||  0  ||  0  ||  0  ||  0  ||  0  ||  0  ||  0  ||  0  ||  X  ||  0  ||  0  ||  0  ||  0  ||  0  ||  X  ||  X  |
[4,6]|  0  ||  0  ||  0  ||  0  ||  1  ||  X  ||  1  ||  0  ||  0  ||  0  ||  0  ||  0  ||  0  ||  0  ||  0  ||  1  ||  X  ||  0  ||  0  ||  0  ||  0  ||  0  ||  X  ||  0  ||  X  |
[5,5]|  0  ||  0  ||  0  ||  0  ||  1  ||  X  ||  0  ||  0  ||  0  ||  0  ||  0  ||  0  ||  0  ||  0  ||  0  ||  1  ||  X  ||  0  ||  0  ||  0  ||  0  ||  0  ||  X  || 0/1 ||  0  ||  X  |
[5,6]|  0  ||  0  ||  0  ||  0  ||  0  ||  X  ||  0  ||  0  ||  0  ||  0  ||  0  ||  0  ||  0  ||  0  ||  0  ||  0  ||  X  ||  0  ||  0  ||  0  ||  0  ||  0  ||  X  ||  0  ||  0  ||  0  ||  X  |
[6,6]|  0  ||  0  ||  0  ||  0  ||  0  ||  X  ||  0  ||  0  ||  0  ||  0  ||  0  ||  0  ||  0  ||  0  ||  0  ||  0  ||  X  ||  0  ||  0  ||  0  ||  0  ||  0  ||  X  ||  0  ||  0  ||  0  ||  0  ||  X  |
[0,0]||[0,1]||[0,2]||[0,3]||[0,4]||[0,5]||[0,6]||[1,1]||[1,2]||[1,3]||[1,4]||[1,5]||[1,6]||[2,2]||[2,3]||[2,4]||[2,5]||[2,6]||[3,3]||[3,4]||[3,5]||[3,6]||[4,4]||[4,5]||[4,6]||[5,5]||[5,6]||[6,6]


There are $24*25 / 2$ combinations in total
Now just count the 1. I got:
- 31 if you allow forks. In this case the chance is $31/300 = 0.1033$. So 10.33%
- 30 if you don't allow forks. In this case the chance is $30/300 = 0.10$. So 10%

• I formatted your table so that it lines up, but I don't understand it. How are you calculating your Xs, and why is everything an X with [0,5]? Mar 11 '16 at 16:24
• @IanMacDonald. Thanks for the edit. X is something that's not possible. For example the combination [0,0],[0,0] cannot be because there is only one tile with [0,0]. Also [0,5], [2,5] and [4,4] are all X because those are the tiles already facing up. And there is not an other one with the same combination. Mar 11 '16 at 16:28
• You have counted [5,5] [4,5] as a 0, though. Mar 11 '16 at 16:38
• Ah. Damn it. Thanks for this. Will fix it fast. Mar 11 '16 at 16:40
• @IanMacDonald Wait. I saw your comment on the question. The question is actually fuzzy. It says five pieces into a valid domino line. But with [5,5] [4,5] you don't get a line. Fixed my answer for both cases. Mar 11 '16 at 16:44