Problem 7.5. In the forest, there live elves and gnomes. One day, 60 inhabitants of this forest lined up facing the same direction, at which point some of them might have been wearing hats. (There could have been from 0 to 60 elves, and inhabitants wearing hats could also have been from 0 to 60 inclusive.)

Each of the 60 inhabitants said one of the following phrases:

- "My neighbor on the right is an elf."
- "My neighbor on the right is wearing a hat."

It is known that elves without hats always tell the truth, while elves with hats always lie. Gnomes are the opposite: gnomes without hats always lie, while gnomes with hats always tell the truth.

(a) (2 points) What is the maximum number of elves without hats that could have been in the row?

(b) (2 points) What is the maximum number of elves with hats that could have been in the row?
Answer: (a) 59. (b) 30.

Solution. (a) Note that the rightmost resident cannot be telling the truth, since there is no one to the right of him. This means he cannot be a hatless elf, so the total number of hatless elves is no more than 59.

Now let's provide an example where there are exactly 59 hatless elves. Suppose the rightmost resident is an elf with a hat, and the other 59 are hatless elves. Let everyone say the phrase “My neighbor to the right is an elf.” Then the hatless elves are telling the truth, while the elf with the hat is lying.

(b) Note that among any two neighbors, there cannot be two elves with hats. Indeed, if this were the case, the left one would definitely have told the truth. But this cannot be, since elves with hats always lie.

Let's divide all residents into 30 pairs of neighbors. In each of these pairs, there is no more than one elf with a hat, so the total number of elves with hats is no more than 30.

Now let's provide an example where there are exactly 30 elves with hats. Suppose that gnomes with hats and elves with hats alternate, with the leftmost resident being a gnome. Let everyone say the phrase “My neighbor to the right is an elf.” Then the gnomes with hats are telling the truth, while the elves with hats are lying.