For teaching: Combinatorial Construction Riddles

Question

Can you give examples of combinatorial construction riddles, approachable by gifted high school students?

Examples:

1. Find a finite set $A$ and $B \subset 2^A$ such that any element of $A$ is covered by at least 100 sets in $B$, but $B$ cannot be partitioned into 2 disjoint sets, each covering $A$.

2. Find the shortest sequence of numbers between 1 and K (K=99) such that each pair of numbers are adjacent somewhere in the sequence (1231 is an answer if K=3).

3. Find a systematic way to arrange a round robin tournament between N teams (N even or odd).

4. Find (different methods) to cover the complete graph on 50 vertices by disjoint spanning trees.

Motivation: I'm working with gifted high school students. This is part of an excellence program in computer science. We have found these kind of problems adequate for stimulating and identifying the better students, before we teach them algorithmic methods. We also let them find winning strategies for mathematical games at this level of their knowledge.

Answer 1

1)

This is a classic/folklore puzzle.

You have 12 apostles and a messiah sitting around a circular table every night for supper.

Can it be so arranged that every night each person gets to sit with different people immediately to the left and right? Try to give a construction which achieves the maximum possible number of nights. What is the maximum possible number?

This basically boils down to decomposing $K_{13}$ (the complete graph on $13$ vertices) into hamiltonian cycles. For a solution, see: Generating a Eulerian circuit of a complete graph with constant memory

2)

Try to arrange the students of the class into two groups so that at least half a student's friends are in the other group.

(Assume friendship in mutual).

This can be done by starting with a random split, and then refining the split by moving around students who don't 'fit' in the group.

The proof it works is by looking at the size of the cut between the groups and by showing that it reduces each time.

3)

You are given a subset of points on a grid.

Can we find a colouring of the given points red/blue so that for each horizontal and vertical line, the difference of number of red and blue points is no more than 1?

You can form a Bipartite graph with one set of vertices to be the x-coordinates, and the other to be the y-coordinates. An edge exists between x and y, if the point (x,y) is given.

If I recollect correctly, I believe this can be solved by finding an Euler tour in the above graph.

Answer 2

The carromboard puzzle

You get inside a room with a square table and a lamp. On each side of the table there's a toggle switch, which can be pressed to toggle it (the four switches have two states each). The lamp turns on if all switches are in the same state (either on or off). When you enter a room, the lamp is not on, so you know that the switches are not all the same state - but that's all you know about their states.

Your goal is to turn the lamp on in as few rounds as possible. The complication is that after each round of pressing (you can press either one switch or two at a time), you must close your eyes, and a goblin turns the table by some unknown amount (wlog it is either 0, 90, 180 or 270 degrees).

Can you turn the lamp on at all? How many rounds does it take you? Is the optimal solution (essentially) unique?

Generalizations

The puzzle can be generalized as follows. There are $n$ switches and $m$ states for each. Each round, you're allowed to press any number of switches (i.e. you have as many hands as you want), and moreover, you can press any given switch more than once. In other words, you're adding an arbitrary vector to the state vector of the switches. The goblin still turns the $n$-sided table each round.

For which $n,m$ can you turn the lamp? What is the minimal rounds needed? How do all the optimal solutions look like?

(If you don't like switches with $m$ states, you can stick to the case $m=2$, which is also simpler.)

Answers

Well, not quite. There is a simple condition on $n,m$ that tells you whether there is a solution. When a solution does exist, the size of the minimal solution has a simple formula. When $m$ is prime (e.g. $m=2$), all minimal solutions have a nice description. For the rest of the solvable cases (other than the trivial ones), there's apparently no nice description (this is an open question, for your more ambitious students).

It turns out that it's better to change the turn-on criterion from all-switches-equal to all-switches-on; there's a simple reduction between the two (when $m$ is prime), and the latter criterion is somewhat more natural.

Prison

The wardens in a state penitentiary are playing a game with the prisoners. All the prisoners are gathered, and told the following: "There is a special cell in the prison, within it a switch with N states (we do not tell you its initial state). From time to time, we will take a prisoner into the special cell. We promise to take each prisoner indefinitely many times into the cell, but we take the prisoners in any order. At any given time, a prisoner can shout "Liberty!" At that point, if all prisoners have been to the cell, we set you free; otherwise, we double your sentences."

For which N do the prisoners have a winning strategy? (I think they win even for $N=2$ but I don't remember; larger N are easier anyhow.)

Hats

A 100 students are standing in a row, so that each one can see the color of everyone in front of her. They know that the color of their hats is either red or blue. The teacher asks them one by one, from back to front, as to the color of their hat. Anyone who answers correctly gets a trip to Disneyworld.

What should the students do to maximize the number of those students who go to Disneyworld?

For the ambitious: What happens if there are countably many students?