2
$\begingroup$

You have a large collection of dominos, each labeled with two distinct symbols drawn from some infinite alphabet. The symbols have 180-degree rotational symmetry so dominoes can be rotated. In other words, these two dominoes are equivalent:

       +---------+---------+             +---------+---------+
       |         |         |             |         |         |
       |    N    |    S    |      ~      |    S    |    N    |
       |         |         |             |         |         |
       +---------+---------+             +---------+---------+

You wish to arrange your entire collection into 4-domino diamonds of the form

           +---------+---------+
           |         |         |
           |    Z    |    S    |
           |         |         |
           +---------+---------+
+---------+---------+ +---------+---------+
|         |         | |         |         |
|    X    |    Z    | |    S    |    N    |
|         |         | |         |         |
+---------+---------+ +---------+---------+
           +---------+---------+
           |         |         |
           |    Z    |    S    |
           |         |         |
           +---------+---------+,

where X, Z, S, N are distinct symbols. Actually, you have made lots of progress, having already assembled an infinite number of copies of each possible diamond. And more good news: the number of remaining dominoes is finite and a multiple of four!

By disassembling at most a finite number of your existing diamonds, will you always be able to arrange your entire collection as desired?

$\endgroup$

1 Answer 1

6
$\begingroup$

I claim that

yes, you can always arrange your collection this way.

The reason why:

Given any domino, we can swap it out for one with one symbol changed: if you want to change AB to AC, find a diamond of the form:
-YA-
XYAB
-YA-
and replace the right-hand domino.

Now that you have this trick, it's easy to make any domino into any other domino: if one symbol is on your target domino, then swap out the other. If neither is, swap one, then swap the other.

So, using this process, you can transmute every set of 4 dominoes into any diamond you like. This requires at most two swaps per domino, and so there are a finite number of broken diamonds.

$\endgroup$

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.