1000 elves and their hat (by induction) Each of $1000$ elves has a hat, red on the inside and blue on the outside or vice-versa. An elf with a hat that is red outside can only lie, and an elf with a hat that is blue outside can only tell the truth. One day every elf tells every other elf, “Your hat is red on the outside.” During that day, some of the elves turn their hats inside out at any time during the day. (An elf can do that more than once per day.)Find the smallest possible number of times any hat is turned inside out (please use induction)
I calculate the smallest possible number times all of the hats are turned inside out but I wasn't able to find the smallest possible number of times any hat is turned inside out
my solution:(find all of the changes)
Lemma: If we have $n$ elves, each with the same color hat, it will take at least $n-1$ switches for each of them to tell each other "Your hat is red".
We will use induction:
The base case is pretty obvious.
Now, assume that this statement is true for $n$. If we have $n+1$ elves of the same color, none of them can tell each other "Your hat is red", so we must first switch at least one hat. Once this is done, the elf who switched colors can tell everyone and everyone can tell him that his hat is red, so we may remove this elf from the picture entirely. The remaining $n$ elves all have the same color, and by the inductive hypothesis, they can only finish in a minimum of $n-1$ moves, so we have at least $n-1+1=n$ moves, as desired.
Now, assume that among the 1000 elves, there are $x$ with blue hats and $1000-x$ with red hats. Every elf can tell the opposite colored elves that their hat is red, so we only need to consider the blue hat and red hat elves separately. By our lemma, it will take the blue elves at least $x-1$ switches and the red elves at least $1000-x-1$ switches to tell each other in their separate groups that their hats are red, so we must have at least $x-1+1000-x-1=998$ switches, as desired.
this question is from (Russian MO,2010,G9)
 A: You also have to show, that for $N>2$ elves this procedure can't be done in $N-3$ switches.
Assume, if there were only $N-3$ switches. There are then at least three elves, that didn't switched their hat. Using pigeonhole principle we can sat, that amongs them there are at least two with the same colour of hat. They can't tell each other 'you hat is red', so the procedure can't be done in $N-3$ switches.
A: If you have $n$ elves whose hats are all the same colour, let the $n^{th}$ elf turn their hat. Then all the conversations with the $n^{th}$ elf happen and you are only concerned with the other $n-1$. The Elf $n$ turns their hat just once. So you should be able to prove that no elf needs to turn their hat more than once. This is not the most efficient procedure time wise, of course, but minimises wear on hats.

Some additional comments.
The last elf of each colour never turns their hat, so if you start off with $N$ you can do $N-2$ turns unless all start the same colour, when $N-1$ is the best possible.
If all start the same colour, and elf $n$ does not change his hat at all, all the others must change at least once to be able to have the conversation with $n$, so you can't have two elves who do not turn their hat, so you need at least $N-1$ turns. If both colours are there at the start, you can have two which don't change - one of each colour.
