Browse · MathNet
PrintCroatian Mathematical Olympiad
Croatia counting and probability
Problem
In the picture below a chain consisted of unit squares is shown. Each unit square, except for the two at the front and the end, is connected to its neighbouring ones in opposite vertices.
It is allowed to put any unit square of the chain in any position in space as long as it is connected to its neighbouring unit squares in corresponding vertices. Is it possible for that chain to make the surface of a cube? (Russia 1999)
It is allowed to put any unit square of the chain in any position in space as long as it is connected to its neighbouring unit squares in corresponding vertices. Is it possible for that chain to make the surface of a cube? (Russia 1999)
Solution
No, it is not possible.
Let us assume the opposite, i.e. that the chain fully covers the surface of a cube. Let us draw a diagonal joining two opposite vertices which are two meeting points of the chain in each unit square of the chain (including the first and the last unit square in the chain as well). After that, we colour vertices which are the meeting points of the chain in black, and other ones in white.
In this manner we got polyline (possibly intersecting itself) on the surface of the original cube. Notice that the degree of all vertices on that polyline is even, except for the first and the last one. Namely, each vertex is connected to exactly two other vertices, while the boundary ones are connected to one. More precisely, all black vertices, except for the two boundary vertices, have degree equal to , while two boundary black vertices have degree equal to or , depending on the case if we end the polyline in the same point from which we started it.
Now, observe the cube and notice that four of its vertices are black. Since each of those vertices has degree equal to , we have at least four vertices with odd degree, which leads to contradiction.
Let us assume the opposite, i.e. that the chain fully covers the surface of a cube. Let us draw a diagonal joining two opposite vertices which are two meeting points of the chain in each unit square of the chain (including the first and the last unit square in the chain as well). After that, we colour vertices which are the meeting points of the chain in black, and other ones in white.
In this manner we got polyline (possibly intersecting itself) on the surface of the original cube. Notice that the degree of all vertices on that polyline is even, except for the first and the last one. Namely, each vertex is connected to exactly two other vertices, while the boundary ones are connected to one. More precisely, all black vertices, except for the two boundary vertices, have degree equal to , while two boundary black vertices have degree equal to or , depending on the case if we end the polyline in the same point from which we started it.
Now, observe the cube and notice that four of its vertices are black. Since each of those vertices has degree equal to , we have at least four vertices with odd degree, which leads to contradiction.
Final answer
No
Techniques
Graph TheoryInvariants / monovariantsOther 3D problems