Цепочка из сосисок, коты

[ole-ole-ole]

Два кота делят огромную цепочку из 100 свиных и 200 говяжьих сосисок, причем они хотят разделить ее так, чтобы каждому
досталось ровно по половине сосисок каждого вида. Какое минимальное число разрезов надо сделать для этого?

Я так понимаю, что сосиски в разнобой идут, то есть не подряд 100 свиных, а потом 200 говяжих (иначе бы хватило двух разрезов).
Сразу можно оценить сверху число разрезов. Это будет 199.
Это число можно сразу уменьшить, потому как число сосисок каждого вида кратно двум. Потому можно рассматривать пары сосисок по 2 шутки. В итоге будет 300 пар, для чего потребуется 149 разрезов.
В правильном ли направлении думаю?

[Cash]

Не с того конца.
Когда требуется минимальное число, то лучше и начинать с наименьших.
То есть задаться вопросами:
Можно ли поделить с одного разреза?
А с двух?
Если не получится - задать следующий вопрос.

[ole-ole-ole]

Cash в сообщении #1036270 писал(а):

Не с того конца.
Когда требуется минимальное число, то лучше и начинать с наименьших.
То есть задаться вопросами:
Можно ли поделить с одного разреза?
А с двух?
Если не получится - задать следующий вопрос.

С одного разреза можно, если только повезет. Рассмотрим случай, когда первые 50 мест будут свиные, следующие 100 мест говяжьих, потом 50 мест свиных. Если ровно посредине разрезать, то получится за один разрез. Но это, если повезет. То есть можно. Но, если не повезет?

[Cash]

Везение - не математическое понятие.
Так можно с одного разреза или нельзя?

[ole-ole-ole]

Cash в сообщении #1036323 писал(а):

Везение - не математическое понятие.
Так можно с одного разреза или нельзя?

Заведомо при любом раскладе нельзя! За два -- тоже нельзя. За три -- тоже.

[Cash]

ole-ole-ole в сообщении #1036343 писал(а):

За два -- тоже нельзя.

Почему?

ole-ole-ole в сообщении #1036343 писал(а):

За три -- тоже.

Почему?

И ole-ole-ole, эти вопросы не значат, что вы неправы. Хочется только видеть доказательство этих утверждений.

[ole-ole-ole]

Пусть говяжьи Г, свиные - С.
Контр пример про один разрез: пусть у нас подряд идут 100 свиных, а затем к этому крепится цепочка 200 говяжьих.
Если разрезать пополам, то одному достанутся только говяжьи, другому смесь Г и С, что противоречит условию.
Если резать не пополам, то одному больше достанется сосисок, другому меньше, противоречие.

С тремя доказать сложнее, пока что не придумать

[angor6]

А цепочка замкнутая?

[ole-ole-ole]

angor6 в сообщении #1036385 писал(а):

А цепочка замкнутая?

Не знаю, но можно рассмотреть оба варианта! (я пока что считал, что незамкнутая)

[angor6]

По крайней мере, вроде бы становится понятно, что если удастся решить задачу для незамкнутой цепочки, то чтобы получить решение для замкнутой, нужно будет добавить ещё один разрез.

Пока даже не представляю, за что можно "зацепиться". Может быть, что-то связанное с делимостью чисел? Может быть, есть смысл сначала решить задачу с меньшими количествами сосисок?

(Оффтоп)

Пока будем решать, коты умрут от голода...

[ole-ole-ole]

Хорошо, пусть будет 2 свиных и 4 гов.

ССГГГГ такую цепочку не распилить одним разрезом на двух котов, чтобы выполнить условия задачи.

С|СГГ|ГГ двумя разрезами вполне

СГГ|ГСГ

С|ГCГ|ГГ --

Вроде как все ок. Как будто двумя все получится.

Кстати, 300 делится на три. Потому все вполне может быть. Может это и есть ответ, но пока не очевидно -- как обобщить.

[Nemiroff]

ole-ole-ole в сообщении #1036364 писал(а):

Контр пример про один разрез: пусть у нас подряд идут 100 свиных, а затем к этому крепится цепочка 200 говяжьих.
Если разрезать пополам, то одному достанутся только говяжьи, другому смесь Г и С, что противоречит условию.
Если резать не пополам, то одному больше достанется сосисок, другому меньше, противоречие.

С тремя доказать сложнее, пока что не придумать

Вы как-то очень элегантно пропустили два разреза.

[ole-ole-ole]

Да, я опечатался, имел ввиду два разреза

[Cash]

И не докажете.

[Nemiroff]

На мой взгляд, с непрерывного случая начинать проще.