Each of $1000$ elves has a hat, red on the inside and blue on the outside or vise 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.
1. **Initial Setup and Definitions**:
   - Each elf has a hat that is either red on the outside and blue on the inside, or blue on the outside and red on the inside.
   - An elf with a hat that is red on the outside can only lie.
   - An elf with a hat that is blue on the outside can only tell the truth.
   - Each elf tells every other elf, "Your hat is red on the outside."
   - Some elves may turn their hats inside out during the day.

2. **Claim**:
   - The smallest possible number of times any hat is turned inside out is \(998\).

3. **Proof of Possibility**:
   - Number the elves \(e_1, e_2, \ldots, e_{1000}\).
   - Initially, let \(e_1\) have a blue hat (truth-teller) and the other 999 elves have red hats (liars).
   - \(e_1\) tells each \(e_k\) (for \(k > 1\)) that their hat is red on the outside. Since \(e_1\) is a truth-teller, \(e_k\) must have a red hat.
   - Now, let \(e_2\) turn their hat inside out to become a blue hat (truth-teller). \(e_2\) then tells each \(e_k\) (for \(k > 2\)) that their hat is red on the outside.
   - Repeat this process iteratively up to \(e_{999}\). After \(e_{999}\) changes to a blue hat and tells \(e_{1000}\) that their hat is red on the outside, the process is complete.
   - In this scenario, \(998\) hat changes were made (from \(e_2\) to \(e_{999}\)).

4. **Proof of Necessity**:
   - Assume fewer than \(998\) changes are made. This implies at least 3 elves did not change their hats.
   - By the pigeonhole principle, at least two of these elves must have the same initial hat color.
   - If two elves have the same initial hat color, they cannot both tell each other that the other's hat is red on the outside, as one would be lying and the other would be telling the truth, which contradicts the initial conditions.
   - Therefore, fewer than \(998\) changes would not satisfy the condition that every elf tells every other elf that their hat is red on the outside.

5. **Conclusion**:
   - The minimum number of hat changes required is \( \boxed{998} \).