Cube Net
Problem
Getting Started
Use the <a href="http://thesaurus.maths.org">Thesaurus</a> if you don't know how to find the subsets of a given set.
In counting the tours remember that you can start from any vertex. From the start there are 3 possible ways to go and at the next vertex two ways to go.
Can you label the vertices of a cube with the subsets of the given set so that an edge connects two vertices if it is possible to move from one subset to another in the sequence?
Student Solutions
Congratulations Andrei, School No. 205, Bucharest, Romania on another excellent solution.
1. I observed that a cube could be represented by the diagram below, that keeps all edges and vertices (the lengths are not important).
From the beginning I observe that one could start from any vertex in a cube and there are $8$ vertices.
From any vertex there are three possible routes. I shall consider the routes starting from vertex $A$.
Below are written all the possible combinations I found starting with the edge $AD$:
| Path | Circuit |
| A-D-C-B-F-E-H-G | No |
| A-D-C-B-F-G-H-E-A | Yes |
| A-D-C-G-H-E-F-B-A | Yes |
| A-D-C-G-F - impossible | |
| A-D-H-E-F-B-C-G | No |
| A-D-H-E-F-G-C-B-A | Yes |
| A-D-H-G-C-B-F-E-A | Yes |
| A-D-H-G-F-E - impossible |
I observe that there are $6$ possible paths, $4$ of which are Hamiltonian Circuits.
I have to multiply the number of solutions I obtained. So the total number of solutions is given by $8 \times3 \times6$ that is $144$, and $96$ are Hamiltonian Circuits.
Because all vertices of the cube are indistinguishable, there are $18$ solutions, and $12$ Hamiltonian Circuits.
2. Set $\{a, b, c\}$ has the following subsets: $\{a, b, c\}, \{a, b\}, \{a, c\}, \{b, c\}, \{a\}, \{b\}, \{c\}, \phi $. I observe that they could be arranged so that one subset is connected with $3$ other subsets that differ from the first by only one element, deleted or inserted. These subsets can be positioned on the vertices of a cube.
Teachers' Resources
The use of set terminology here should not hold anyone up as they can find the definition in the <a href="http://thesaurus.maths.org">Thesaurus</a>. This is an exercise in combinatorics and it also gives a method for solving the problem about the sequence of subsets.