Problems
There are \(n\) balls labelled 1 to \(n\). If there are \(m\) boxes labelled 1 to \(m\) containing the \(n\) balls, a legal position is one in which the box containing the ball \(i\) has number at most the number on the box containing the ball \(i+1\), for every \(i\).
There are two types of legal moves: 1. Add a new empty box labelled \(m+1\) and pick a box from box 1 to \(m+1\), say the box \(j\). Move the balls in each box with (box) number at least \(j\) up by one box. 2. Pick a box \(j\), shift the balls in the boxes with (box) number strictly greater than \(j\) down by one box. Then remove the now empty box \(m\).
Prove it is possible to go from an initial position with \(n\) boxes with the ball \(i\) in the box \(i\) to any legal position with \(m\) boxes within \(n+m\) legal moves.
Given a natural number \(n\), find a formula for the number of \(k\) less than \(n\) such that \(k\) is coprime to \(n\). Prove that the formula works.
A paper band of constant width is tied into a simple knot and tightened. Prove that the knot has the shape of a regular polygon.
In the picture below you can see the graphs of \(K_5\), the complete graph on \(5\) vertices, and \(K_{3,3}\), the complete bipartite graph on \(3\) and \(3\) vertices. A theorem states that these graphs cannot be embedded into plane, namely one cannot draw graphs \(K_5\) and \(K_{3,3}\) on a plane in such a way that there are no intersecting edges.
The question is: can you draw the graphs \(K_5\) and \(K_{3,3}\) without intersecting edges on a torus?
Is it possible to draw the graph \(K_{3,3}\) without intersecting edges on a Moebius band?
Is it possible to link three rings together in such a way that they cannot be separate from each other, but if you remove any ring, then the other two will fall apart?
If we glue the opposite sides of the paper band in the same direction as on the picture, we will get a cylinder. What surface do we get, if we glue the circles of the cylinder in the same direction as well?
We start with a rectangular sheet of paper - preferably with proportions more than \(6:1\), so that it looks more like a band. For now assume that one can stretch or shrink the paper band as needed. Describe the surface we get if we start with a rectangular sheet of paper and then glue the opposite sides of the paper band in the opposite direction as in the picture.
In the last room, there are two doors, but someone broke into this room and the signs that used to be on the doors are now on the floor! You do not know which sign was on which door, but the statements on them say:
There is a trap behind this door.
There are traps behind both doors.
Your guide says: The first sign is true if there is treasure behind the first door, otherwise it is false. The second sign is false if there is treasure behind the second door, otherwise it is true.
But you don’t know which sign is first! What do you do?
How would you describe the surface obtained by glueing the sides of the octagon as on the picture? Sides of the same colour are glued together in the same direction as shown.
