7
$\begingroup$

Inspired by The five problems of the six domino tiles, where one of the tasks was to place six domino tiles so that each tile touches three others (corner / edge touches don't count). My solution there required putting domino tiles on top of each other, and the OP (not the author of the puzzle) thought there is no 2D solution.

Now, if we increase the number of tiles, we can certainly make a 2D solution, e.g. the following one using 16 tiles:

enter image description here

A natural question/puzzle is therefore to ask:

What pattern uses the minimum number of tiles?

Rules:

  • The tiles are twice as long as wide
  • Tiles have to be laid out in a two-dimensional pattern
  • Each tile needs to touch exactly three others; only touches between edges count
  • Just to be pedantic: there needs to be at least one tile
$\endgroup$
0

1 Answer 1

5
$\begingroup$

Based on your 16-tile example I reduced it down to

8 dominoes.
enter image description here

Sketch of proof why this is minimal:

The number of dominoes must be even because of the handshaking lemma. So it only remains to show that 6 is impossible.
Thinking about it as a graph with the dominoes as vertices with edges connecting touching dominoes, then we are looking for a planar, 3-regular, simple graph with 6 vertices. The only such graph is that formed by the edges of a triangular prism. It has three 4-sided faces and two triangular faces.
Unfortunately we need one face to have at least 5 edges, since one face forms the outside boundary of the graph, and it is impossible to have four dominoes fully enclosing the other two. So it is not possible with 6 dominoes.

I did not prove the assertion that there is only one planar, 3-regular, simple graph with 6 vertices, and I don't really know how. Still, it is easy to convince yourself that if you start with a hexagon and turn it into a 3-regular graph by adding diagonals, then the added diagonals must cross. The same happens to a pentagon with a sixth vertex somewhere inside.

$\endgroup$
2
  • 1
    $\begingroup$ I think you have found the minimum solution... $\endgroup$
    – Pspl
    Jul 30, 2020 at 12:50
  • 1
    $\begingroup$ @Glorfindel I've added a sketchy proof. $\endgroup$ Jul 30, 2020 at 13:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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