Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Imagine matching dominoes end-to-end such that only like numbers are joined. For a collection of dominoes, one could ask whether it is possible to join them all into a single strand.

I'm interested in a slightly different problem. What if dominoes could be translated but not rotated? That is, [2 | 3] is distinct from [3 | 2] so there are $n^2$ dominoes with numbers up to $n$ rather than ${n\choose2}+n$ dominoes. In particular, for a given multiset of dominoes (a non-negative integer-valued $n\times n$ matrix, if you prefer), is it possible to choose an order such that the second and first numbers, respectively, of adjacent dominoes are equal? (The first number of the first domino need not equal the second number of the last domino: they are in a line not a ring.)

I'd also be interested in related questions:

  • the number of solutions (if there are solutions)
  • an algorithm for finding a solution (if there are solutions)
  • the length of a maximal solvable submultiset (if there are no solutions)
  • an algorithm for finding a maximal solvable submultiset (if there are no solutions)

if anyone has a reference (or is looking for brownie points).

Clarification: I do not have all $n^2$ dominoes, but a multiset of dominoes. Some appear more than once, others (most!) do not appear at all.

share|improve this question
add comment

3 Answers 3

up vote 4 down vote accepted

I don't quiet like @RossMillikan's answer since it reduces to a hard problem (Hamiltonian path!). Here is another reduction to an easier question: Eulerian path in the directed multi-graph (if you want your non-rotation condition and allow repeated dominos).

If you dominos have ends numbered from $1$ to $n$, then create a graph on $n$ vertices. If a domino is labeled $[x | y]$ then add the directed edge $(x,y)$ to your graph (add multiple edges if the domino appears multiple times). To make a chain you need to find a Eulerian path in this graph (if you want your dominos to form a circle, then you need a Eulerian cycle). Further, note that the reduction in the opposite direction works too, every dircted multigraph can be encoded as a dominos problems. Thus this question is equivalent to the Eulirean path problem, and hence a reference is the literature on Eulerian paths.

If you said domino could only appear once, then the graph would not be a multi-graph. If you said we could rotate dominos, then the graph would be undirected.

How do you check if a multi-graph has a Eulirean path? If you have a set (instead of a multi-set) of dominos or in terms of graphs you have a directed multi-graph then the condition is simple:

  1. The graph is connected

  2. And each vertex has the same in-degree and out-degree. With the possible except of two vertexes with one having one more in-degree than out-degree and the other having one more out-degree than in-degree.

share|improve this answer
    
@Brian thanks, fixed! –  Artem Kaznatcheev Aug 22 '11 at 3:10
2  
Sorry for the late accept, had Hurricane Irene-related issues. –  Charles Sep 1 '11 at 19:41
add comment

In terms of a general multiset it is possible to generate an enormous number of instances where you cannot create a path simply by adding a domino that cannot connect to any of the dominoes already in the set. If you have the set {[1|2][2|3][3|4][7|9]} there is no possible path.

To test a multiset count and record the number of times each digit appears on a domino in the set. If there are 3 or more digits with an odd number of occurrences there is no possible path. If there are 2 digits that have only one occurrence they must not occur on the same domino in order to be able to construct a path. Also, if there is a domino that has the same digit on both sides [x,x] then that domino cannot be the only one containg the digit x.

In the case where there are $n^2$ distinct dominoes you can apply Meyniel's Theorem to determine that there does exist a hamiltonian cycle. For each possible (non-isomorphic) cycle you can choose an arbitrary place to seperate it to make a path. Then, leaving the dominoes in order, there are $n^2$ distinct paths you can create (per hamiltonian cycle) by moving the last domino to the front of the path.

share|improve this answer
add comment

There are always many solutions. You can think of it as a directed graph. Each domino is a vertex. There is a path from vertex $A$ to vertex $B$ if domino $B$ can follow $A$ in the chain. Each domino has $n$ incoming paths and $n$ outgoing paths, and you are looking for a Hamiltonian path. One way to prove it possible is by induction. It works for $n=1$ as there is only one domino. Given a solution for $n$, create a solution for $n+1$ by joining all dominoes $[a,n+1]$ to $[n+1,a]$ to make a new $[a,a]$. These can be inserted anywhere in the chain where there is an $a$. You also need to hide the $[n+1,n+1]$ in one of the joints.

There are clearly many more solutions.

share|improve this answer
    
I don't see why each domino would have $n$ incoming paths and $n$ outgoing paths. What if we just have $n - 1$ dominos? Also, Hamiltonian path is a hard problem! Also, there are not always many solutions, consider the domino set $[1|2],[2|3],[3|4],...,[n-1|n]$. –  Artem Kaznatcheev Aug 20 '11 at 16:35
    
@Artem Kaznatcheev: OP specified we have a complete set of n^2. In that case the problem isn't so hard. –  Ross Millikan Aug 20 '11 at 16:39
    
where did he specify that? OP's statement is: "In particular, for a given multiset of dominoes (a non-negative integer-valued n×n matrix, if you prefer), is it possible to choose an order such that the second and first numbers, respectively, of adjacent dominoes are equal?" He just tells us in the line before how many possible dominos there could be (so that we better understand what he means by non-rotatable), however I think the OP wants an answer for an arbitrary multiset. –  Artem Kaznatcheev Aug 20 '11 at 16:41
    
@Artem Kaznatcheev: Precisely. –  Charles Aug 20 '11 at 20:23
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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