2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

Если Вы зададите новый вопрос в существующей теме, то в случае нарушения оформления или других правил форума Ваше сообщение и все ответы на него могут быть удалены без предупреждения.

Не ищите на этом форуме халяву, правила запрещают участникам публиковать готовые решения стандартных учебных задач. Автор вопроса обязан привести свои попытки решения и указать конкретные затруднения.

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему На страницу 1, 2, 3, 4  След.
 
 Цепочка из сосисок, коты
Сообщение12.07.2015, 17:41 


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

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

 Профиль  
                  
 
 Re: Цепочка из сосисок, коты
Сообщение12.07.2015, 19:07 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Цепочка из сосисок, коты
Сообщение12.07.2015, 20:27 


03/06/12
209
Cash в сообщении #1036270 писал(а):
Не с того конца.
Когда требуется минимальное число, то лучше и начинать с наименьших.
То есть задаться вопросами:
Можно ли поделить с одного разреза?
А с двух?
Если не получится - задать следующий вопрос.

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

 Профиль  
                  
 
 Re: Цепочка из сосисок, коты
Сообщение12.07.2015, 20:56 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Цепочка из сосисок, коты
Сообщение12.07.2015, 21:24 


03/06/12
209
Cash в сообщении #1036323 писал(а):
Везение - не математическое понятие.
Так можно с одного разреза или нельзя?

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

 Профиль  
                  
 
 Re: Цепочка из сосисок, коты
Сообщение12.07.2015, 21:27 
Заслуженный участник


12/09/10
1547
ole-ole-ole в сообщении #1036343 писал(а):
За два -- тоже нельзя.

Почему?
ole-ole-ole в сообщении #1036343 писал(а):
За три -- тоже.

Почему?

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

 Профиль  
                  
 
 Re: Цепочка из сосисок, коты
Сообщение12.07.2015, 22:16 


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

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

 Профиль  
                  
 
 Re: Цепочка из сосисок, коты
Сообщение12.07.2015, 22:36 
Аватара пользователя


11/03/12
586
Беларусь, Минск
А цепочка замкнутая?

 Профиль  
                  
 
 Re: Цепочка из сосисок, коты
Сообщение12.07.2015, 22:39 


03/06/12
209
angor6 в сообщении #1036385 писал(а):
А цепочка замкнутая?

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

 Профиль  
                  
 
 Re: Цепочка из сосисок, коты
Сообщение12.07.2015, 22:51 
Аватара пользователя


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

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

(Оффтоп)

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

 Профиль  
                  
 
 Re: Цепочка из сосисок, коты
Сообщение12.07.2015, 23:08 


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

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

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

СГГ|ГСГ

С|ГCГ|ГГ --

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

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

 Профиль  
                  
 
 Re: Цепочка из сосисок, коты
Сообщение12.07.2015, 23:11 
Заслуженный участник


20/07/09
4026
МФТИ ФУПМ
ole-ole-ole в сообщении #1036364 писал(а):
Контр пример про один разрез: пусть у нас подряд идут 100 свиных, а затем к этому крепится цепочка 200 говяжьих.
Если разрезать пополам, то одному достанутся только говяжьи, другому смесь Г и С, что противоречит условию.
Если резать не пополам, то одному больше достанется сосисок, другому меньше, противоречие.

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

 Профиль  
                  
 
 Re: Цепочка из сосисок, коты
Сообщение12.07.2015, 23:19 


03/06/12
209
Да, я опечатался, имел ввиду два разреза

 Профиль  
                  
 
 Re: Цепочка из сосисок, коты
Сообщение12.07.2015, 23:25 
Заслуженный участник


12/09/10
1547
И не докажете. :wink:

 Профиль  
                  
 
 Re: Цепочка из сосисок, коты
Сообщение12.07.2015, 23:41 
Заслуженный участник


20/07/09
4026
МФТИ ФУПМ
На мой взгляд, с непрерывного случая начинать проще.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 57 ]  На страницу 1, 2, 3, 4  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group