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

[angor6]

ole-ole-ole, Вы установили, что если в незамкнутой цепочке 2 свиных и 4 говяжьих сосиски, то достаточно двух разрезов, чтобы разделить их поровну между двумя котами. Если бы звеньями незамкнутой цепочки из 300 сосисок являлись цепочки по 2 свиных и 4 говяжьих сосиски, то понадобилось бы не более $49+50\cdot 2=149$ разрезов. Если предположить, что в цепочку из 300 сосисок входят и звенья по 6 сосисок одного вида, то количество разрезов не увеличивается. Теперь, по-видимому, остаётся рассмотреть цепь, включающую звенья, в которых 1 свиная и 5 говяжьих сосисок или 5 свиных и 1 говяжья сосиска...

[Evgenjy]

Получил, что можно 102 разрезами. Кто меньше?

[ET]

(Оффтоп)

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

[NSKuber]

Каждый кот должен получить в итоге по 150 сосисок. Представьте, что у вас цепочка развёрнута в прямую, и вы отрезали правые 150 сосисок (сделали разрез посередине) и отдали первому коту. В хорошем (для кота) случае он получит сколько надо. А может, получить, например меньше пятидесяти свиных сосисок. Но в таком случае, если бы вы дали ему левые 150 сосисок, он получил бы свиных сосисок больше нормы. Истина где-то посередине.

[Evgenjy]

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

[ole-ole-ole]

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

ole-ole-ole, Вы установили, что если в незамкнутой цепочке 2 свиных и 4 говяжьих сосиски, то достаточно двух разрезов, чтобы разделить их поровну между двумя котами. Если бы звеньями незамкнутой цепочки из 300 сосисок являлись цепочки по 2 свиных и 4 говяжьих сосиски, то понадобилось бы не более $49+50\cdot 2=149$ разрезов. Если предположить, что в цепочку из 300 сосисок входят и звенья по 6 сосисок одного вида, то количество разрезов не увеличивается. Теперь, по-видимому, остаётся рассмотреть цепь, включающую звенья, в которых 1 свиная и 5 говяжьих сосисок или 5 свиных и 1 говяжья сосиска...

Если 1 свиная и 5 говяжьих, то распределение будет "неравномерным" (я имею ввиду, что все звенья не могут быть такими, а промежуточных вариантов очень много. Тоже самое касается ситуации 5 свиных и 1 говяжья сосиска.

-- 13.07.2015, 16:36 --

Evgenjy в сообщении #1036572 писал(а):

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

Идея про диаметр очень понравилось. Давайте рассмотрим 12 сосисок. Очень похоже на циферблат.

Если среди них 4 свиных и 8 говяжьих, то без проблем можно провести диаметр так, чтобы по одну сторону были две свиных, по другую две говяжьих (вроде как очевидно, требуется ли доказывать это?).
$300:12=25$, то есть если рассмотреть 25 таких звеньев, то потребуется $24+2\cdot 25=74$ разреза.

Но тут опять сложность. Чем больше мы сосисок берем в звено, тем больше случаев расположения внутри звена нужно рассматривать.
Пока что мне не очевидно разбиение на звенья по 6 сосисок. Опять сложно учесть ситуации, когда не в каждом звене по 4Г и 2С.

-- 13.07.2015, 16:39 --

А как непрерывный случай рассматривать? Это имеется ввиду, что у нас просто есть веревка, где 200 метров окрашено в синий цвет, а 100 метров в зеленый? Если да, то как это может помочь. Если нет, то что имеется ввиду?

[NSKuber]

ole-ole-ole
Да, про непрерывный вы правильно поняли. Пусть эта верёвка так же выложена кругом. Проведите произвольный диаметр и запомните какую-нибудь половину верёвки. А теперь проследите, как будет меняться соотношение синего и зелёного в этой половине, когда вы будете вращать диаметр (а лучше даже вращать верёвку, чтобы выбранная половина оставалась на месте), непрерывно повернув в итоге на 180 градусов.

[ole-ole-ole]

NSKuber в сообщении #1036690 писал(а):

ole-ole-ole
Да, про непрерывный вы правильно поняли. Пусть эта верёвка так же выложена кругом. Проведите произвольный диаметр и запомните какую-нибудь половину верёвки. А теперь проследите, как будет меняться соотношение синего и зелёного в этой половине, когда вы будете вращать диаметр (а лучше даже вращать верёвку, чтобы выбранная половина оставалась на месте), непрерывно повернув в итоге на 180 градусов.

В какой-то момент соотношение синего и зеленого по разные половины будет одинаковым. Да?

[angor6]

ole-ole-ole,

(Оффтоп)

может быть, кто-то уже писал об этом. Но вспоминая выполненное Вами решение примера с двумя свиными и четырьмя говяжьими сосисками, я склоняюсь к мысли, что трёх разрезов вполне достаточно. Нужно от одного из концов цепи сначала отрезок кусок, содержащий 50 свиных сосисок, посчитать, сколько между ними попало говяжьих сосисок...

[Nemiroff]

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

В какой-то момент соотношение синего и зеленого по разные половины будет одинаковым. Да?

Это нужно доказать.

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

что трёх разрезов вполне достаточно

Двух.

[angor6]

Nemiroff, да, двух. Прошу извинить за "фрейдовскую" оговорку.

[Shadow]

ole-ole-ole Еще задачка на тему: Докажите, что существует интервал из 10000 продряд идущих натуральных чисел, содержащий ровно 10 простых чисел.

[Nemiroff]

Shadow
а) как это связано?
б) это выглядит сложным (проще доказывать для общего случая $m$ натуральных и $n$ простых), или же я просто не знаю простого способа.

[Cash]

Достаточно заметить, что существует 10000 идущих подряд составных чисел

[Nemiroff]

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

Достаточно заметить, что существует 10000 идущих подряд составных чисел

Это один факт для доказательства. А ещё нужно заметить, что сдвиг на один меняет число простых не более, чем на один.
И здесь нет резона использовать $10000$, так что опять же, проще и красивее смотреть на общий случай.