* Императорът и отровата
Публикувано на 21 юли 2009 в раздел Математика.
Владетелят на средновековна империя бил близо до навършване на 50 години. За да отпразнува подобаващо той решил да направи изключително пищно пиршество.
Малко по-малко от два дни преди бала, на който били поканени най-представителни гости от всички държави, бил подаден анонимен сигнал, че в една от бутилките вино е пусната смъртоносна отрова. Тя била толкова силна и коварна, че след около 24 часа убива здрав войн без да се появят каквито и да е видими симптоми. Абсолютно точен интервал на действие обаче не е неизвестен - може да варира дори с няколко часа. Дори една малка капчица от виното би била достатъчна, за да повали здрав мъж.
Императорът бил изкличитлно загрижен от този слух. За пиршеството вече били приготвени 1000 бутилки от най-скъпото вино. Той не можел да си позволи да бъдат унищожени. За императорският дегустатор пък било непосилно да се справи със задачата да открие отровната бутилка сам за един ден. Затова императорът решил да използва роби за дегустатори - при всички положения би му излезло по-евтино от 1000 бутилки скъпо вино.
Тук обаче се появил друг сериозен проблем. Откъде да събере 1000 роби за толкова кратко време? Императорът бил отчаян. За негово щастие тогава се появил придворния математик (блестящ учен надскочил времето си), който успял да направи схема на дегустация, по която са нужни значително по-малко роби и в крайна сметка открили отровната бутилка. Пиршеството се провело по план и всички три дни яли, пили и се веселили.
Задачите към вас:
1. Какво е минималното количество роби и по каква схема са дегустирали виното така, че с абсолютна сигурност да бъде открита отровната бутилка? Колко максимално от тях ще умрат?
2. Ако един милилитър е достатъчен за да бъдете отровен, то какво количество вино ще бъде изпито, ако използвате минимално количество роби?
3. Ако една бутилка от супер-качественото вино струва 30 лири, живота на един роб струва също 30 лири, разходите за докарване на роб до двореца са 1 лира, една бутилка вино е от 1 литър, а както казахме минималното количество за отпиване е 1 милилитър, то какво е оптималното количество роби, които бихме използвали, за да имаме минимални разходи? Приемаме, че се страхуваме от най-лошото развитие на дегустацията.
4. Колко вино ще остане за пиршеството с оптимално финансово решение?
П.С. Третата задача не съм я решавал въобще. Само сметнах колко са парите в краищата на интервала и се опитах да нагодя числата. Най-добре направете графика на решенията и по нея търсете минимума :)
1. 501 роби - 500 от тях пият от 500 бутилки. 1вия роб пие от бутилка 1 до бутилка 500, втория от бутилка 2 до бутилка 501, третия от 3 до 502 и тн. така ще покрият 999 бутлки и остава един роб да пие от последната. В най-добрия случай ще умре само той, в най-лошия умират 500 роби.
2. Всеки от 500те роби ще изпие по половин литър. Това прави 250 литра + 1мл от 501-вия роб, освен това ще трябва да унищожат отровната бутилка в която не се знае колко вино ще има.
Mertol - далече си от верния отговор на зад. 1. Препоръчвам ти да започнеш постепенно - от по-малко бутилки. Така ще ти се изясни по-добре.
Ще е добре да има едит бутонче докато чака одобрение.
Последно:
1. 10 роби - бутилките са от 0 до 999. За да се изпие по-малко вино и да умират по-малко роби, първия пие от нечетните, втория от 2и3, 6и7, 10и11 и тн. последния пие от 512 до 1000. Умрял се отбелязва с 1, а жив с 0, първия роб с нечетните бутилки е младши разряд. Полученото число е поредния номер на отровната бутилка. Ще умрат от 0 до 9 роби.
2. Изпитото вино е
500+500+500+496+496+488+488+488+488+488=4930мл.
Допълнителна оптимизация:
числата с много единици, като 0111111111 например може да се заменят с такива с по-малко от свободните от 1000 до 1023 - например 1111101000. От 24-те неизпозвани има 2 числа с 4 нули, 7 с 3 и 9 с 2. Така ще се елиминира възможността да умрат 9 роби. И дпоълнително се усложнява задача 3.
след оптимизацията изпитото вино е 4916мл.
задача 3:
При увеличаване броя на робите, разделяме 1000-та бутилки на по възможност равни части - на 2 равни части бихме могли при 18 роби - 2x500 за около 390-400 лири, при 32 на 4х250 за около 360 лири, при 56 на 8х125 за около 340 лири, при 96 на 8х62+8х63 за около 335 лири, при 155 на 24х31+8х32 за около 370 лири, при 256 на 40х16+24х15 за около 430 лири. Промяната на стойността в началото идва главно от по-малкия брой умрели роби, увеличаването при последните стойности идва главно от разхода за транспортиране. Намаляването на изпитото вино е около половин литър между две изброени или около 15лири.
Изброените бяха с възможно най-равно разделени бутилки, но е възможно да са разделени на други интервали. Очевидно минимума е някъде между 56 и 96 използвани роби. Намаляването на изпитото вино в този интервал идва от там че се замества дегустацията на 7 роби с по-малко. Например бутилка номер 63 трябва да е опитана от 6 роби, при добавяне на допълнителен роб, харчим 1 лира за транспорт и спестяваме 0.005л. вино х30 лири = 0.15 лири. Очевидно неможе да се спести от по-малко изпито вино, следователно остава да се спести от по-малко умрели роби.
Бутилките опитани от 6 роби са 47(Във всяка от 8те групи има по 7 числа с една нула, но 2 от тях са след 125. Понеже неможе да използваме повече от една нула във всички групи, в 7 от тях трябва да заменим нулата с едно от тези числа с една нула. Това прави 7*6+5.), те могат да се кодират с 6 роби. От тези 6 роби има 1 вариант при който умират и 6мата, него няма да ползваме. Има 6 варианта при които умират 5, има 15 варианта при които умират 4. От всичките 63 използваеми варианти имаме 16 излишни, тези излишни включват варианта с 6 умрели, 6те варианта при които умират 5 и 9 от вариантите при които умират 4. Остават 6 по 4 умрели, 20 по 3 умрели, 15 по 2 умрели и 6 по 1 умрял.
Равносметка:
62 роби = 62 лири за транспорт
+5 умрели * 30 лири = 150 лири
+56 роби опитали по ~62.5 бутилки = 3.500л.*30 лири = 105 лири
+6 роби опитали по ~23.5 бутилки = 0.141л.*30лири = 4.23 лири
общо 321.23 лири
зад. 1. Нужни са 10 роби. Представете си бутилките като битове. 10 роби правят 1024 комбинации - достатъчно да пробват бутилките. Максимално умират 9, но в някои източници пише 8. Не успях да намеря решение с 8 - изглежда се използват "празните" комбинации. Mertol даде насока, благодаря за което.
Mertol - как реши зад. 2.? Аз получих друг отговор, но реших задачата без доказаелство. Използвах следния факт:
за 4 бутилки вино са нужни 2ма души, които пият общо 4 пъти-
за 8 бутилки вино са нужни 3ма души, които ият общо 12 пъти (3 пъти повече)
Продължете по степените на двойката да увеличаваме по 3 и до 1024 и ще се получи над 26 литра вино.
Дано не бъркам, но таблично ми излезе така :)
Последният коментар - нищо общо с действителността. Добре - двама роби отпиват отппо 500 бутилки всеки. Единият след 24 часа ще умре. В коя бутилка е отровата? Няма отговор в твоето решение.
Задача: 1000бут x30лири=30,000лири
1роб x31лира= 31лири
___1бут=1000мл
__1мл=на отравяне________________________
2-ма роби дегустират x500бут
1-ви роб отпива от 500бут x1мл=500мл=1/2бут.
2-ри роб отпива от 500бут x1мл=500мл=1/2бут.
2-мата роби дегустират общо 1бут=1000мл
Остават 999 бут.
Разход:1бут=30лири
1роб=31лири
Общо: 61лири-чиста загуба
Но,тъй като останалия жив роб,не е чиста загуба,
но е разход по дегустацията,то би следвало да се
прибавят още 31лири
Или:61+31=92лири/разход по дегустацията
Тотал:30,000-92=29,908лири
Толкова минимално срува удоволствието на императора,
да се натряска и да остане жив.
п.п.Но какво би станало,ако един от двамата роби
се отрови в хода на дегустацията,а не накрая,както предвиждам,не знам.Явно нещо съм пропуснал в условието или съм на грешен път.
Какво пък от това.Автора ми е познат,и ще ми подскаже!?!?
10 роби максимум
Лесна работа, стига роби да има - налива се в една кана по една капка от 500 бутилки, ако умре 1-вия роб там е отровата, ако не - в другите 500. Пак се сипва по една капка от останалите 250 бутилки на едно място и т.н.
Нали 2 на степен 10 е 1024. Значи с 10 броя ще се оправим.
Да така е,съсредочих се в"Задачите към вас:"1,2,3,4 и пропуснах условието за 24ч.Не се оправдавам.Благодаря за подсещането.Сменям посоката.
за задача 2:
първия роб е пил от нечетните те. 500мл.
втория роб е пил от 2и3, 6и7, 10и11 и тн. те. пак 500 мл
...
...
четвъртия роб не е пил първите 8, пил е 2рите 8, не е пил 3тите 8, пил е 4тите и тн докато стигнал че пие от 984 до 991. те. 496мл.
...
шестия роб не пил първите 32, пил вторите 32, не пил 3тите...
пил от 928 до 959 и от 992 до 999 или общо 488
...
накрая сумирам:
500+500+500+496+496+488+488+488+488+488=4932мл.
Решението че стават 3 пъти повече е грешно, всъщност е броя на хората умножен по половината от бутилките при условие че броя на бутилките е степен на двойката.
Lesna Rabota - първо е "10 роби минимум", а не максимум и второ имаш грешка в метода. Има ограничение от 24 часа. Няма достатъчно време за да го направиш по този начин.
Както казах вече представете си бутилките като битове. Нека например са 4 бутилки. Задачата е решима с 2ма роби:
Ако x означава "пил", а o "не пил", то гледаме кой умира. Ако умре само R1 - значи е B1. Ако умрат двамата, то е B2. Ако умре само R3 => B3. Ако никой не умре - B4.
Метода се пренася към по-голямото множество по същия начин.
Хайде сега нататък действайте, че там е зор :)
Може да си прав. Аз разсъждавах не математически, а визуално. Ето решенията за 4 и 8 бутилки:
Какво забелязваме? Ами маркираната в дебело де дублира надясно, а от долу се добавя нов ред с четири отпивания. Не отчетох обаче, че на следващата стъпка ще се добяват на последен ред не 12, а 8!
Затова се обърках :)
Твоята корекция е логична и е съвсем вярна.
Така дотук благодарение на Mertol имаме решени зад.1. и зад.2. За зад.3. приемам решението въпреки, че би било добре да бъде малко по-добре структурирано, за да бъде по-убедително.
Мисля, че ако някой програмист напише програма, която да визуализира дискретна графика на функцията:
като естестмево по оста X стоят стойнтостите от 10 до 1000, което всъщност е брой роби, то ще може да се види много добре графично решението. Аз обаче не съм любител на писане на такива програми. Може някой студент :) :) :)