Показать скрытый текст
Одного перекусывания не хватит, если все сардельки слева, а сосиски справа: тогда либо все сардельки, либо все сосиски достанутся одной собаке.
Докажем, что двух перекусываний хватит, даже если замкнуть цепочку в кольцо. Разделим кольцо диаметром на две равные части (по 15 колбасных изделий). Тогда если сосисок в частях будет поровну, то и сарделек тоже.
Если сосисок оказалось не поровну, будем поворачивать диаметр, пока он не сделает половину оборота (и части как бы «поменяются местами»). Докажем, что в какой-то момент сосисок в частях будет поровну. В начальный момент сосисок в одной части столько же, сколько их будет в конечный момент в другой части. Значит, если в начальный момент сосисок в одной части меньше, чем в другой, то в конечный момент - больше. Но после каждого шага число сосисок в каждой части либо не меняется, либо меняется ровно на 1. Поэтому в какой-то момент в частях будет по половине всех сосисок (а значит, и по половине сарделек).
Записан