У каждого из 1000 гномов есть колпак, синий снаружи и красный внутри (или наоборот). Если на гноме надет красный колпак, то он может только лгать, а если синий – только говорить правду. На протяжении одного дня каждый гном сказал каждому: «На тебе красный колпак!» (при этом некоторые гномы в течение дня выворачивали свой колпак наизнанку). Найдите наименьшее возможное количество выворачиваний.

Рассмотрим ситуацию, когда есть всего 2 гнома.
Тогда, если на них колпаки одного цвета. Например красные, то они не смогут выполнить условие без выворачиваний. То есть изначально они должны сказать: "На тебе синий колпак!" - А это противоречит условию.
Аналогично, если оба в синих колпаках. То каждый скажет "На тебе синий колпак!" - Это противоречит условию.
Если же на них двоих колпаки разного цвета (один в синем, другой в красном), тогда оба скажут "На тебе красный колпак!". И это соответсвует условию и не требуется выворачивать колпак.
Теперь будем добавлять по 1 гномику. На нем будет либо красный либо синий колпак. И его цвет не совпадет с одним из гномов и они смогут сказать друг другу: "На тебе красный колпак!"
Но его цвет обязательно совпадет с другим гномом. И чтоб выполнить условие, ему потребуется вывернуть свой колпак, чтоб он стал разного цвета с другим гномом.
Таким образом  каждый добавленный гном должен обменятся выражениями с гномами у которых колпаки другого цвета. Потом вывернуть колпак и обменятся выражениями с гномами с которыми теперь колпаки стали разного цвета.
Получаем, что только 2 гнома не выворачивают колпак. А 998 гномов должны вывернуть колпаки.
Например: 1 в синем колпаке и 999 в красных. Они обменялись сообщениями и гном в синем со всеми уже переговорил и может не меняя колпака отдыхать.
Красные же по очереди выворачивают колпак и с оставшимися обмениваются сообщениями и тоже отправляются отдыхать. Последни оставшийся в красном колпаке, в конце уже обменялся со всеми репликами и выворачивать колпак ему уже не надо. Тоже идет отдыхать.
Показано что больше 2 оставаться без выворачиваний, не могут, то есть меньше 1000-2=998 нельзя. И приведен пример для 998 выворачиваний.
Ответ: Наименьшее число выворачиваний - 998