Метод спуска, индукция и последовательное конструирование в ТЧ

(a) Заметим, что к весу всех коров можно добавить одно и то же число, тогда задача не изменится. Тогда можно считать, что самая лёгкая корова имеет вес 0. Предположим, что существует корова веса Тогда пусть общий вес всех коров Числа и чётные, поскольку после выкидывания коров нулевого веса и веса оставшиеся коровы должны поделиться на группы равного веса. Тогда чётно. Аналогично можно получить, что веса всех коров чётны. Тогда разделим их на 2, получим аналогичную задачу. Бесконечно делить на 2 мы не можем, поэтому все коровы имеют одинаковый вес.

(b) Домножим веса всех коров на общий знаменатель. Тогда получим условие пункта (a), так что снова все коровы весят одинаково.