Двое воров украли ожерелье, состоящее из драгоценный камней и хотят поделить его между собой. Ожерель пердставляет собой драгоценные камни d видов, нанизанные на незамкнутую проволку, камней каждого вида четное число. Воры хотят разделить ожерелье на минимальное количество кусков и распределить их между собой так, чтобы каждый из них получил попровну камней каждого вида. Докажите два утверждения: 1) Для некоторых ожерелий им потребуется хотя бы d разрезов. 2) d разрезов хватит для любого ожерелья

задан 9 Сен '19 3:43

Пункт 1) достаточно лёгкий. Если группы камней каждого типа расположены подряд, то при < d разрезов какая-то из групп не разрезается, и одному достаётся вся группа.

Для пункта 2) я пока умею доказывать только при d=2.

(9 Сен '19 9:40) falcao

Крайне интересная задача для d>2. А источник не подскажете?

(9 Сен '19 16:11) knop

@falcao Если Вам не сложно не могли Вы изложить решение для $%d=2$%, либо привести ссылку? @knop Сейчас наверное не вспомню, но это был какой-то листок с олимпиадными задачами.

(30 Сен '19 15:12) sapere aude

Делаем засечку, которая делит поровну камни первого вида. Левому куску приписываем 0, правому 1. И так далее. Получим не более d засечек, каждой приписан набор длины d из 0 и 1. Один берет любой кусок, второй - инверсный, где 0 и 1 меняются на 1 и 0.

Мне это не нравится.

(30 Сен '19 16:19) FEBUS
10|600 символов нужно символов осталось
1

Случай d=2.

Пусть у нас 2k белых и 2m черных камней. Рассматриваем k+m последовательных камней от (i+1)-й позиции до (i+k+m)-й. Здесь i любое от 0 до k+m. Если для некоторого i в рассматриваемой "вырезке" будет ровно k белых камней, то там же будет m чёрных, и задача разделения камней поровну при помощи двух разрезов решена.

Обозначим через f(i) число белых камней для данного i. В последовательности f(0), f(1), ... , f(k+m) каждое следующее число либо равно предыдущему, либо отличается от него на единицу в ту или другую сторону. Легко видеть, что f(0)+f(k+m)=2k, так как "вырезки" для случаев i=0 и i=k+m не пересекаются и покрывают всё ожерелье. Тогда, если f(0) < k, то f(k+m) > k или наоборот.

При переходе от числа, меньшего k, к числу, большему k, мы по принципу "дискретной непрерывности" получим такое i, для которого f(i)=k.

Было бы интересно разобрать хотя бы следующий случай d=3. Если у меня это получится, то я сделаю добавление.

ссылка

отвечен 30 Сен '19 19:46

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×1,220

задан
9 Сен '19 3:43

показан
135 раз

обновлен
30 Сен '19 19:46

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru