December 2005 1

Invariants (J)

Problems

1. Suppose the positive integer n is odd. First Alice writes the numbers 1, 2, …, 2n on the blackboard. Then she picks any two numbers a, b, erases them, and writes |a − b| in their place. Prove that when there is exactly one number left on the board, then it is odd.

2. A circle is divided into six sectors. The numbers 1, 0, 1, 0, 0, 0 are written in the sectors, anticlockwise in that order. You may increase two neighbouring numbers by 1. Is it possible to equalise all numbers by a sequence of such steps?

3. Three automata I, H and T print pairs of positive integers on tickets. For an input (a, b), I and H give (a + 1, b + 1) and (a/2, b/2) respectively. H accepts only even a, b as input. T accepts two pairs (a, b) and (b, c) as input and yield output (a, c). Starting with (5, 19), for which n can the ticket (1, n) be reached?

4. Each term in a sequence 1, 0, 1, 0, 1, 0, … starting with the seventh is the sum of the last six terms modulo 10. Prove that the string 0, 1, 0, 1, 0, 1 never occurs in this sequence

5. Two opposite corner squares of an 8 × 8 chessboard are deleted. In how many ways can the resulting 62 squares be tiled by 2 × 1 dominos?

6. A square chessboard of side length 2^{n} is given with exactly one square coloured red. Prove that it is possible to tile the non-red squares exactly using L-shaped trionimos only.

7. In the Parliament of Sikinia, each member has at most three enemies. Prove that the house can be separated into two houses, such that each member has at most one enemy in his own house.

8. 2n ambassadors are invited to a banquet. Every ambassador has at most n−1 enemies. Prove that the ambassadors can be seated around a round table in such a way that nobody is sitting next to an enemy.

9. Start with a sequence S = (a, b, c, d) of positive integers and find the derived sequence T (S) = (|a − b|, |b − c|, |c − d|, |d − a|). Does the sequence S, T (S), T (T (S)), … always reach (0, 0, 0, 0)?

10. For what m and n can a m × n rectangle be tiled with 1 × 4 tiles?