Естественные науки

За место в постоялом дворе постоялец расплачивается ежедневно, по одному звену из своей золотой цепи, которая...

...изначально была замкнута в круг, т. е. не имела концов. На какое наибольшее число дней он может проживать в постоялом дворе (т. е. каково наибольшее число звеньев у цепи), если для оплаты он цепь разделил на р кусков той или иной длины, "откусив" р звеньев? Повреждённые звенья тоже идут на оплату.
Павел Леонидович
Павел Леонидович
68 229
Может, натолкнёт на мысль: помню задачку про минимальное количество откусов, чтобы сохранить цепь как можно длинее.
6-ти звенная цепь кусается 2 раза, получается 3 звена (1,2 и 3 кольца) - хватит на 6 дней
7-ми звенная цепь кусается 2 раза, получается 3 звена (1,2 и 4 кольца) - хватит на 7 дней
8-ми звенная цепь кусается 3 раза, получается 4 звена (1,1,2 и 4 кольца) - хватит на 8 дней
9-ти звенная цепь кусается 3 раза, получается 4 звена (1,2,2 и 4 кольца) - хватит на 9 дней
10-ти звенная цепь кусается 3 раза, получается 4 звена (1,2,3 и 4 кольца) - хватит на 10 дней
и т. п., то есть количество кусков и звеньев разное

А в Вашей задаче р кусков по р звеньев... Даже не знаю...
ХГ
Хазби Годжиев
7 411
Лучший ответ
Павел Леонидович Но и 11-звенная цепь кусается всего 2 раза! Получается 2 откушенных звена и 2 куска по 3 и 6 звеньев - хватит на 11 дней. Можете проверить. Это - максимально возможное число звеньев при откусывании из них двух.
В моей задаче не р кусков ПО р звеньев, а р откушенных звеньев и р кусков различной длины.
Павел Леонидович Впрочем, это у вас "открытая" цепь - о два конца? Тогда 7-извенная кусается 1 раз, на третьем звене с какого-либо конца: получается одно откушенное звено и два куска по 2 и 4 звена... Эта простенькая задача давным-давно была задана в ж-ле "ТМ". Впрочем, именно благодаря ей я здесь задал серию задач по этой теме.
Павел Леонидович Что же. Решения никто не нашёл. Но хоть вы предприняли какие-то попытки.
При р= 1 имеем: 1 кусок из 2-х зв. Р= 1+2= 3 (3 дня)
При р= 2 имеем: куски из 3-х и 6-и зв. Р= 2+3+6= 11 (11 дней)
При р= 3 имеем: куски из 4-х, 8-и и 16 зв. Р= 3+4+8+16= 31 (31 дней)…
При произвольных р имеем р кусков. i-й кусок (1 <= I <= p) имеет звеньев zi= (p+1)*2^(i-1) шт. Наибольшее число звеньев в цепи P= (p+1)*2^p-1 шт.
Насколько я помню (так же, как и с весами, на обе чашки которых можно класть гирьки), нужно идти по степеням тройки: 1, 3, 9, 27...
Так можно получить любой набор до (3 в степени n) минус 1 и пополам.
Две гирьки - до 4-х ((9-1)/2)
Три гирьки - до 13-и ((27-1)/2)
И так далее.
Елена Рудакова
Елена Рудакова
54 305
Павел Леонидович Настоящая задача похожа на задачу с гирьками, и только. С гирьками в 1 и 3 г можно взвешивать все граммы от 1 до 4 вкл., но расплачиваться с 1 звеньем и куском из 3 звеньев ежедневно за 4 дня - нет.
Игорь Семин Таким набором гирек, как, например, 1+3+9+27 (всего 40 г), вы не сможете набрать вес 33, 34 или 35 г. Или я что-то не так понял?
Павел Леонидович Если не пропал интерес, можете см. посл. коммент лучшему ответу.
а в чем проблема то? устный счет пока не отменили вроде и с кусачками проблем нет, или есть?
Оксана Струсинская
Оксана Струсинская
91 825
Павел Леонидович Я и не говорю, что тут есть какая-то проблема. Просто свет не сошёлся клином на одних постояльце и хозяине постоялого двора. Данная математическая задача на "размен-сдачу" может встречаться и при совершенно иных ситуациях, когда р может приобретать и довольно большие значения. Поэтому далеко не лишено смысла отыскать значение Р в общем виде, как разделить это максимальное значение на части... Конечно всё это - лишь для тех, кого интересует вопрос.
уважаю.
трижды прочёл а сути не понял. сути проблемы.
Сергей Молдаков
Сергей Молдаков
66 524
Павел Леонидович Уважаю и понимаю. Думал с ночи, но чтобы изложить доходчивее - ничего придумать не смог. Может, приведённое только-что дополнение прольёт некоторый свет в проблему.
Павел Леонидович Если не пропал интерес, можете см. посл. коммент лучшему ответу.
Будет жить пока дядька из Киева бузину не привезет.
Сергей Александров
Сергей Александров
9 075
Павел Леонидович Вот видите: дядьки один за другим являются. Хотя бузины-то пока маловато...

Похожие вопросы