Solution

In total there are 45 rocks. In the end we get 45 piles with 1 rock each. In order to divide the first pile into piles with 1 rock each, we need 9 moves. To do the same for the second pile we need 14 moves, and for the third pile we need 19 moves. (Note: the number of moves does not depend on whether we take one rock out of the pile per move, or a few rocks per move.) Thus the total number of moves is $9+14+19=42$ and this number does not depend on which moves the players make. The last, even, move is by the second player, and so the second player wins.

Hint

Solution

Solution 1.

We will consider all possible pairs of letters which go into the word. We call the pairs a … b, b … c and c … a good pairs a … c, c … b and b … a – bad.

a$)$ Consider how the number of pairs changes when one card is added. Inside this card there are two good and one bad pair. Since three different letters are inserted “into one place,” with each of the already existing letters they form three new pairs: neutral, good and bad. Hence it is clear that the number of good pairs is always greater than the number of bad pairs. And in the palindrome, they should be equally divided because of the symmetry of the word.

b$)$ As shown in a$)$, each red card increases the difference between the number of good and bad pairs by one unit, and each blue – reduces the number by one. Since in the palindrome the number of good pairs is equal to the number of bad pairs, the number of red cards is equal to the number of blue ones.

Solution 2.

We consider a triangular lattice of equal triangles on the plane, we paint it in a staggered order, and select the starting point $O$ on it. Let’s compare the letters $a, b, c$ to unit vectors in three directions $($see the figure$)$ and consider the word as a description of a path, starting at point $O.$ Any of the triples $abc, bca, cab$ adds to the path a trip around a dark triangle, and from the triples $acb, cba, bac$ – a trip around a light one. The path is still closed, although some edges may be passed several times. If the closed path is a palindrome, then the first and last edges coincide in direction, but one starts at $O,$ and the other ends at $O.$ Hence, the corresponding segments are centrally symmetric with respect to $O.$ In the same way, the second and penultimate segments of the path are centrally symmetric, and so on. So the entire path turns out to be centrally symmetric.

Let us calculate the oriented area covered by a closed broken line. We choose $O$ as the origin. Then if $AB$ and $CD$ are centrally symmetric segments, and the vectors $AB$ and $CD$ are co-directional, then the sum of the oriented areas $OAB$ and $OCD$ is 0. Hence, the total oriented area is equal to 0. Let the area of each triangle of the lattice be equal to 1. Then the triangles of the first type add up to 1, and the second type gives the sum -1. Hence, a$)$ in the palindrome there were cards of both types used, and b$)$ the cards of both types were used equally.

Hint

–

Solution

It is convenient to depict a row of dragons in the form of a graph: instead of each dragon, draw a point at the height corresponding to the number of heads that the dragon has, and connect these points.

a$)$ See the figure.

b$)$ Note, firstly, that somewhere in the interval between every two cunning dragons there is a strong one. Indeed, if we go along a series of dragons, then after we pass a cunning dragon, the number of heads begins to decrease. At some point it should start to increase – this is the position where there is a strong dragon. Likewise, further increases at some point will end with another cunning dragon.

The first method. Let’s see in what order can the strong and cunning dragons be arranged. A strong dragon with six heads can only stand between two cunning dragons with seven heads. There are three such cases: the two remaining strong dragons stand either on one side of this trinity in one of two orders, or on opposite sides.

In the first case, the position of 14 dragons has already been determined unequivocally, and the only way to get the first and last dragon heads to be equal, is to add another dragon with five heads to the right of the right edge.
The second and third arrangements are impossible, since they require more than 15 dragons $($ even without considering the condition of the same number of heads on the dragons at the edges $)$.

The second method $($ sketch $)$. You can do without trials. Choose a plot of the graph between some strong dragon and the cunning dragons nearest to it and “straighten it out”, replacing a “dip” with a “hill” $($ see the picture $)$.

The number of heads that the dragons have  will change, and instead of two cunning dragons and one strong one this plot, there will be just one cunning dragon. Note that the number of heads that the new cunning dragon will have will be equal to the sum of the number of heads that the initial two cunning dragons had minus the number of heads that the former strong dragon had. This means that with such a procedure, the amount $($ the sum of the number of heads of all the cunning dragons minus the sum of the number of heads of all the strong dragons $)$ does not change.
Note also that the number of heads that the dragons at the edges of the row have from such an operation is not known to change. Let us repeat this operation until all the strong dragons disappear. We will have one cunning dragon, which, for reasons of symmetry, will be exactly in the middle of the row. Let’s count how many heads he will have. We know that initially the sum of the numbers of cunning dragon heads minus the sum of the number of heads of strong dragons is
4 + 6 + 7 + 7 – 3 – 3 – 6 = 12. But now this amount is the number of heads of just the cunning dragon!
Knowing that he has 12 heads, we can further easily restore that the edge dragons $($ separated by seven positions in the row $)$ have five heads.

Hint

Solution

a$)$ See the problem 35111.

b$)$ First we turn all the coins except the first, then all but the second, etc. As a result, each coin will be turned 19 times.

Answer

a$)$ It is impossible; b$)$ it is possible.

Hint

–

Solution

We will prove that any such initial table will contain a sub-table of size $2 \times 2$, in which there is one zero and three ones.

There will always be a row in the table containing only 0s, as there are $n$ rows but only $n-1$ 1s. It follows that there will always be two adjacent rows, one of which contains only 0s and the other contains at least one cell with the number 1.

This non-zero row will always contain two adjacent cells, one of which will contain the number 0 and the other the number 1. These two squares, along with the two adjacent squares in the row with only 0s, make up the sub-table we are looking for.

Let us choose an arbitrary $2 \times 2$ sub-table. Let the value in the top left corner equal $a$, the top right corner $b$, the bottom left corner $c$, and the bottom right – $d$. After the operation is carried out on a random cell $X$, let these values be $a_1, b_1, c_1, d_1$, respectively.

Consider the expressions:

$$D = (a+d) – (b+c)$$ and $$D_1 = (a_1+d_1)-(b_1+c_1)$$

Three scenarios are possible:

1) Cell $X$ lies outside of our sub-table, but lies in a row or column which intersects with our sub-table. Without loss of generality, let $X$ lie in the same row as $a$ and $b$. Then $a_1=a+1$, $b_1=b+1$, $c_1=c$, $d_1=d$ and $D_1= (a+1+d)-(b+1+c)=D$.

2) Cell $X$ lies outside of our sub-table, and lies on neither a row nor a column which intersects with our sub-table. Then, obviously, $D_1=D$.

3) Cell $X$ lies within our sub-table. Without loss of generality, let it be the top left cell in the sub-table. Then $a_1=a-1$, $b_1=b+1$, $c_1=c+1$, $d_1=d$ and $D_1=D-3$. If $X$ is the bottom right cell, then again $D_1=D-3$, otherwise $D_1=D+3$.

In this way, we have proved that the remainder when dividing $D$ by 3 is invariant. However in our initial table we found a $2 \times 2$ sub-table in which $D= \pm 1$, but we are tasked with creating a table in which all the numbers are the same – i.e. $D=0$, which is impossible.

Answer

No, it is not.

Hint

–