Кратко: ошибка в шаге индукции при переходе от $n$ к $n+1$.
Идея «доказательства»: для множества из $n+1$ коров берут две подпоследовательности по $n$ коров (удалив по одной разной корове). По предположению индукции в каждой такой подпоследовательности все коровы одного цвета, и раз эти подпоследовательности пересекаются хотя бы одной коровой, цвета совпадают на пересечении, значит все $n+1$ коров одной и той же краски.
Где ломается: пересечение этих двух $n$-подмножеств имеет размер $n-1$. Оно ненулевое только если
$$n-1\ge 1\iff n\ge 2.$$ При переходе $n=1\to n+1=2$ пересечение пусто, поэтому утверждение «цветы в первой подпоследовательности совпадают с цветами во второй» не гарантировано. Именно здесь доказательство даёт неверный вывод (фактически для двух коров цвета могут различаться).
Как правильно обобщить правило применения индукции:
- Нужно проверить достаточно начальных случаев, чтобы вспомогательное построение индуктивного шага было корректно. В рассматриваемом «удалительном» аргументе требуется $n\ge 2$, значит дополнительно к базе $n=1$ нужно проверить базу $n=2$.
- В общем: если в индуктивном шаге вы строите $n+1$-объект из нескольких $n$-объектов, убедитесь, что эти $n$-объекты перекрываются там, где вам нужно; требуемый размер перекрытия диктует, сколько начальных случаев нужно доказать.
- Альтернатива: использовать сильную индукцию (предполагая утверждение для всех размеров $\le n$), но и тогда необходимо проверить соответствующий набор базовых случаев.
Замечание: в задаче «все коровы одного цвета» утверждение ложно (уже для $n=2$), поэтому никакая корректная индукция с истинными базами не сделает его верным.