А доказывать нужно, потому что каждый может крикнуть невозможно. Пусть даже это и так очевидно, если подумать.

Доказательство выше кажется сложным, потому что оно немного некорректно описано.

Было и другое доказательство с точки зрения дискретной математики.

Одно, что здесь остается неясным, так это почему ТС выложил эту загадку, заведомо не имеющею решения.