9.6. Each of the 1000 gnomes has a hat, blue on the outside and red on the inside (or vice versa). If a gnome is wearing a red hat, he can only lie, and if it is blue, he can only tell the truth. During one day, each gnome said to each other, "You have a red hat!" (during the day, some gnomes turned their hats inside out). Find the minimum possible number of turnings. (I. Bogdanov)
9.6. Answer. 998 turnovers.

Let's call a gnome red or blue if he is wearing a cap of the corresponding color. Note that one gnome can say the required phrase to another if and only if these gnomes are of different colors: a blue gnome will tell the truth in this case, and a red one will lie. Now, if any three gnomes have not turned their caps, then two of them are of the same color, and they will not be able to say the required to each other, which is incorrect. Therefore, there are no more than two such gnomes, and the number of turnovers is not less than $1000-2=998$.

We will say that two gnomes have communicated if each of them has said the desired phrase to the other. Let's describe how it could happen that there were only 998 turnovers, for example, if at the beginning the gnome Vasya was blue, and the others were red. At the beginning of the day, each gnome communicated with Vasya. Then the red gnomes took turns turning their caps. In this case, after each turnover, all the red gnomes communicated with the one who changed color. When only one red gnome is left, any pair of gnomes will already have communicated with each other (at the moment when the first of them changed color), while 998 color changes have occurred.

Remark. An example with 998 color changes can be constructed starting from any situation where not all gnomes are of the same color.