Domino tile possibilities

Question

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]

Answer 1

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

ANSWER:

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.

Answer 2

Answer:

$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.

Answer 3

I started answering in the math way, but 2 answers already appeared.
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%