$\begin{array}{ll}{\left[\begin{array}{l}\text { Game Theory (other) }\end{array}\right]} \\ {\left[\begin{array}{l}\text { Pairings and Groupings; Bijections }\end{array}\right]}\end{array}$

A token is placed on a chessboard. Two players take turns moving the token to an adjacent square. It is forbidden to place the token on a square it has already visited. The player who cannot make a move loses. Who wins with correct play?
Match the second move with some move of the first.

## Solution

We will divide the board into dominoes $1 \times 2$. The strategy of the first player: if before the first player's move, the token is in one of the cells belonging to some domino, then by his move, the first player moves it to the other cell of the same domino. Note that after the first player's move, all allowed cells are again divided into dominoes. This means that the first player will always be able to make a move, adhering to his strategy, and therefore will not lose.

## Answer

The first.

In the cafeteria, six dishes are offered for selection. Each day, Vasya takes some set of dishes (possibly not taking any dishes), and this set must be different from all the sets he took on previous days. What is the maximum number of days Vasya can follow such rules, and how many dishes will he eat on average per day?

## Hint

Each set of dishes can be matched with an opposite set, consisting precisely of the dishes that are not in the original set.

## Solution

The number of days is obviously the number of different sets of six dishes. For each dish, there are two possibilities - to be chosen or not chosen. Therefore, the number of days is $2^{6}$.

Each set of dishes can be matched with an opposite set, consisting precisely of the dishes that are not in the original set. Together, the original and the opposite set contain six dishes, so on average, there are three dishes per set. Since all 64 sets are divided into pairs of opposite sets, Vasya ate, on average, three dishes per day over these 64 days.

## Answer

64 days, on average 3 dishes per day.