Problems

Prove that the number of all arrangements of the largest possible amount of peaceful bishops (figures that move on diagonals and don’t threaten each other) on the $8\times 8$ chessboard is an exact square.

Tickets cost 50 cents, and $2n$ buyers stand in line at a cash register. Half of them have one dollar, the rest – 50 cents. The cashier starts selling tickets without having any money. How many different orders of people can there be in the queue, such that the cashier can always give change?

Prove that the Catalan numbers satisfy the recurrence relationship $C_n=C_0{C}_{n-1}+C_1{C}_{n-2}+\cdots +C_{n-1}{C}_0$. The definition of the Catalan numbers $C_n$ is given in the handbook.

There is an elastic band and glass beads: four identical red ones, two identical blue ones and two identical green ones. It is necessary to string all eight beads on the elastic band in order to get a bracelet. How many different bracelets can be made so that beads of the same colour are not next to each other? (Assume that there is no buckle, and the knot on the elastic is invisible).

A $1\times 10$ strip is divided into unit squares. The numbers $1,2,\dots ,10$ are written into squares. First, the number 1 is written in one square, then the number 2 is written into one of the neighboring squares, then the number 3 is written into one of the neighboring squares of those already occupied, and so on (the choice of the first square is made arbitrarily and the choice of the neighbor at each step). In how many ways can this be done?

Tile a $5\times 6$ rectangle in an irreducible way by laying $1\times 2$ rectangles.

Does there exist an irreducible tiling with $1\times 2$ rectangles of

(a) $4\times 6$ rectangle;

(b) $6\times 6$ rectangle?

Irreducibly tile a floor with $1\times 2$ tiles in a room that is

(a) $5\times 8$; (b) $6\times 8$.

Having mastered tiling small rooms, Robinson wondered if he could tile big spaces, and possibly very big spaces. He wondered if he could tile the whole plane. He started to study the tiling, which can be continued infinitely in any direction. Can you help him with it?

Tile the whole plane with the following shapes:

Robinson Crusoe was taking seriously the education of Friday, his friend. Friday was very good at maths, and one day he cut 12 nets out of hardened goat skins. He claimed that it was possible to make a cube out of each net. Robinson looked at the patterns, and after some considerable thought decided that he was able to make cubes from all the nets except one. Can you figure out which net cannot make a cube?