Вот и у меня как-то так выходит: первый раз по чуть-чуть из ста бочек на рыло, одного урку не трогать(оставляем 100 бочек в "запас"). Так определяем, в какой сотне отравленная бочка(Если никто не умер, она в "запасной"). Далее аналогично определяем, в каком десятке бочек отравленная.(Если осталось 9 урок, наливаем всем, если 10 - одного не трогаем.) Итого за два часа проверено 990 бочек. Пока гости будут их выпивать, можно проверить остальные:)
Но как это ужать в два приема не знаю. В лучшем случае у меня получается три, в худшем -четыре.
Бочки с вином напомнили одну добротную задачку:
Есть 100-этажка. При броске с кирпича с определённого этажа кирпич ломается (и со всех более высоких этажей - тоже сломается, а с более низких - нет). У нас есть 2 одинаковых кирпича. Требуется как можно быстрее (за наименьшее число бросков) выяснить этот самый номер этажа, с которого кирпичи начинают ломаться.
За сколько бросков вы справились бы?
> [Вбрасывает] > Это картина "Масленица", написанная душевнобольным человеком. Суть его болезни заключалась в том, что человек не видел вокруг себя НИЧЕГО, кроме своих фантазий и желаемого. Долгое время картина висела в холле гостиницы "Украина", но никто даже не подозревал, что ее художник - глубоко больной человек. В этой картине есть признак, который со 100%-й вероятностью показывает, что художник - с психическими отклонениями. Укажите этот признак. > > [censored] > [censored]
[бегает кругами, бросает все подряд]
Ха!! Я понял! С психическими отклонениями, не ходожник, а прохфесор, ее анализировавший. [рудется безмерно]
> Есть 100-этажка. При броске с кирпича с определённого этажа кирпич ломается (и со всех более высоких этажей - тоже сломается, а с более низких - нет). У нас есть 2 одинаковых кирпича. Требуется как можно быстрее (за наименьшее число бросков) выяснить этот самый номер этажа, с которого кирпичи начинают ломаться. > За сколько бросков вы справились бы?
т.е. надо составить наиболее оптимальный алгоритм для произвольного этажа?
Вечер вроде наступил :) Попробую ответить. Или мозг "замылился" или это решение.
Разбиваем бочки на сотни и присваиваем их каждому зэку
Разбиваем каждую сотню на десятки.
Первый зэк пробует свою сотню и все первые десятки из сотен других зэков
Второй зэк пробует свою сотню и все вторые десятки из сотен других зэков
Третий зэк и т.д
Тут варианты Первый вариант
Если умирает только один (допустим первый) ясно, что яд в первой сотне в первой десятке (ведь все остальные десятки попробовали другие зэки). И у нас остается еще 9 зэков. Если каждый попробует по одной бочке, а одну отставят в сторонку то или один умрет ( кэп говорит, что яд в бочке из которой он пил) или все выживут и значит яд в отстасленной в сторону Второй вариант
Умирают двое. Допустим первый и второй. А значит яд или первом десятке второй сотни или во втором десятке первой. Под подозрением 20 бочек, а у нас 8 зэков.
Проверяем тем же способом Из каждой бочки пьют уникальными парами.
Первый столбец бочки. второй пары зэков.
1 1/2
2 2/3
3 3/4
4 5/6
5 7/8
6 1/3
7 2/4
8 3/5
9 4/6
10 5/7
11 6/8
12 1/4
13 2/5
14 3/6
15 4/7
16 5/8
Если остановиться на этом то под подозрением еще 4 бочки.
Поэтому не остнавливаясь быстренько создадим уникальные тройки.
17 1/2/3
18 3/4/5
19 6/7/8
20 1/4/8
А потом смотрим . Если умерло двое - то смотри какая пбочку пила эта пара.
Если умерли трое - смотри какую бочку они вместе пили.
Вроде так :) Возможно ошибся, но не могу найти ошибку
> Бочки с вином напомнили одну добротную задачку: > Есть 100-этажка. При броске с кирпича с определённого этажа кирпич ломается (и со всех более высоких этажей - тоже сломается, а с более низких - нет). У нас есть 2 одинаковых кирпича. Требуется как можно быстрее (за наименьшее число бросков) выяснить этот самый номер этажа, с которого кирпичи начинают ломаться. > За сколько бросков вы справились бы?
Так кирпича только два. Значит и броска только два? Если больше, то традиционнвм спообом угадывания "больше-меньше"
>> Так кирпича только два. Значит и броска только два? Если больше, то традиционнвм спообом угадывания "больше-меньше" > > ну почему? > бросил с 1го - не разбился, со 2го - не разбился, с 3го... на 63 - разбился. > ответ готов =)
Дешевле бросать с каждого второго.
Типа со 2го, 4го, ... 64го - разбился первый кирпич, бросаем с 63 - разобьется или нет.
>> Так кирпича только два. Значит и броска только два? Если больше, то традиционнвм спообом угадывания "больше-меньше" > > ну почему? > бросил с 1го - не разбился, со 2го - не разбился, с 3го... на 63 - разбился. > ответ готов =)
прошли уже сутки, поэтому даю ответ на задачу про 1000 бочек
эту задачу хорошо решать, будучи программистом, потому как решается она при помощи двоичной системы счисления.
любое число до 1024 можно представить в двоичном виде при помощи всего 10 разрядов.
например 1000 = "1111101000", 666 = "1010011010", 77 = "0001001101"
(для тех, кто не понял как я это сделал - при помощи стандартного калькулятора винды, "вид - инженерный")
нумеруем все бочки таким образом.
а каждый смертник будет отвечать за свой разряд.
потом поим из бочек по принципу - стоит 1 в твоем разряде - пьешь, стоит 0 - пропускаешь.
после часа некоторая часть - умрет. зная их разряды, ставим в соответствующие места 1, а в остальные - 0.
после чего переводим в 10 систему и имееем отравленную бочку.
-------------------------------
в среднем каждый перепробует 500 бочек,
а из каждой бочки - не более 9
> прошли уже сутки, поэтому даю ответ на задачу про 1000 бочек > > эту задачу хорошо решать, будучи программистом, потому как решается она при помощи двоичной системы счисления. > любое число до 1024 можно представить в двоичном виде при помощи всего 10 разрядов. > > например 1000 = "1111101000", 666 = "1010011010", 77 = "0001001101" > (для тех, кто не понял как я это сделал - при помощи стандартного калькулятора винды, "вид - инженерный") > > нумеруем все бочки таким образом. > а каждый смертник будет отвечать за свой разряд. > > потом поим из бочек по принципу - стоит 1 в твоем разряде - пьешь, стоит 0 - пропускаешь. > > после часа некоторая часть - умрет. зная их разряды, ставим в соответствующие места 1, а в остальные - 0. > после чего переводим в 10 систему и имееем отравленную бочку. > ------------------------------- > в среднем каждый перепробует 500 бочек, > а из каждой бочки - не более 9
Прикольно. Каждую бочку пьет уникальная комбинация зэков. Вот я тупень... Про двоичные числа даже не подумал, хотя казалось бы..
Э! А ты хитрый! Тогда надо было в условиях задачи указать что не два часа, а час!
А теперь правильные ответы от Бати: 1)Задача о таблетках.
Ответ: пополам разрезать 2)Задача о вине.
Ответ: 3 часа
самый удачный вариант: 3 часа и никто не умрет
самый неудачный вариант: 3 часа и 3 трупа 3)Задача о картине.
Ответ:[censored]
>> Про двоичные числа даже не подумал, хотя казалось бы > > а в комментах предлагали округлить до 1024!!!
Хм.. Т.е подумал, но неправильно подумал и вернулся к тысяче. Сейчас вспоминается, что давно подобную задачку решал и подобным способом. Остается утешаться, что эту задачу решил другим способом.
Пойду стукнусь головой.
> Бочки с вином напомнили одну добротную задачку: > Есть 100-этажка. При броске с кирпича с определённого этажа кирпич ломается (и со всех более высоких этажей - тоже сломается, а с более низких - нет). У нас есть 2 одинаковых кирпича. Требуется как можно быстрее (за наименьшее число бросков) выяснить этот самый номер этажа, с которого кирпичи начинают ломаться. > За сколько бросков вы справились бы?
Отблин, заснуть не мог, про бочки думал. Придумал )
А тут уже решение.. эхх..
Ну, для тех, кто ещё не понял вдруг, на пальцах свои мысли..
Сначала подумал, можно ли организовать для случая попроще, когда бочек 4, а смертников только 2.
Если первому скормить пойло из бочек 1 и 3, а второму - пойло из 1 и 2, то если
1. оба загнулись, то бочка 1 с ядом
2. первый загнулся, то бочка 3 с ядом
3. второй загнулся, то бочка 2 с ядом
4. никто не загнулся, то бочка 4 с ядом
Если обозначить факт пития из бочки циферкой, 1 - пить, 0 - не пить, то получится схематично так:
первому: 1010 (из 1 и 3 - наливать, из 2 и 4 - не наливать)
второму: 1100 (из 1 и 2 - наливать, из 3 и 4 - не наливать)
Расширил дальше на случай из 8 бочек и 3 смертников:
1: 10101010
2: 11001100
3: 11110000
Если заметить, то справа-налево в столбиках идут числа от 0 до 7 в двоичной системе счисления.
Таким же макаром расширяем до 10 смертников и 1024 бочек.
Выходит, 2 часов - много, достаточно одного часа!!
эх... а я уже "доказал" что это невозможно и разработал формулу для общего случая...
----------------------------------
кстати, камрады, кто-нибудь в курсе, каким образом анализируются задачи на взвешивание?
задачи типа "среди 10 монет одна фальшивая. фальшивая более легкая. на весах без гирь за 3 взвешивания найти фальшивую".
так вот вопрос - а как определяется минимальное число взвешиваний при котором задача еще решается? особенно если монет скажем 40, фальшивых несколько, да и с весом непонятки.
> так вот вопрос - а как определяется минимальное число взвешиваний при котором задача еще решается?
Можно сказать, при каких условиях однозначно не решается.
Условие:
число_вариантов_результата_взвешивания^число_попыток_взвешивания >= число_возможных_вариантов_ответа
Если условие нарушено, то однозначно не решается. Если выполнено - возможно решается.
Классический пример: за 3 взвешивания узнать какая из 12 монет фальшивая (легче или тяжелее остальных) и сказать, тяжелее она или легче.
Здесь:
число_вариантов_результата_взвешивания = 3 (больше, меньше, равно)
число_попыток_взвешивания = 3
число_возможных_вариантов_ответа = 24 (первая легче, первая тяжелее, вторая легче, вторая тяжелее, ...., 12-ая легче, 12-ая тяжелее)
Проверяем:
3^3=27 >= 24
Значит вполне возможно, что задачка разрешима (она разрешима, проверено).
А вот если б монет было не 12, а 14 - то задачка бы не решилась (т.к. 27>=28 не выполнено)
>> Нужна трудоёмкость в наихудшем случае. 51 - многовато будет! > И как же быстрее, если у тебя всего 2 кирпича?
> в среднем каждый перепробует 500 бочек, > а из каждой бочки - не более 9
А персчитай в литрах на рыло сколько получится?
ИМХО самый простой вариант разбить на сотни, а потом перекрестным способом уже вычислить отравленную бочку. Для перекрёстного способа хватит и 9 негров зеков.
Ну как же, вот хотя бы почти вдвое лучше метод: бросаем первый (пока живой кирпич) с 25, 50, 75 и 100 этажей последовательно. Если на каком-то разобьётся (например, на 50), то вторым кирпичом добиваем от предыдущего проверенного до номера на котором разбилось (от 26 до 49) невключительно. В худшем случае до 28 (4+24) бросков.
> А персчитай в литрах на рыло сколько получится?
Если по чайной ложке из бочки, то хоть из полтыщщи бочек наливай, сильно больше литра на рыло не выйдет никак.
> ИМХО самый простой вариант разбить на сотни, а потом
> Ну как же, вот хотя бы почти вдвое лучше метод: бросаем первый (пока живой кирпич) с 25, 50, 75 и 100 этажей последовательно. Если на каком-то разобьётся (например, на 50), то вторым кирпичом добиваем от предыдущего проверенного до номера на котором разбилось (от 26 до 49) невключительно. В худшем случае до 28 (4+24) бросков.
Хехе :-)
У меня получилось от 2-х до 14 бросков :-)
>> Ну как же, вот хотя бы почти вдвое лучше метод: бросаем первый (пока живой кирпич) с 25, 50, 75 и 100 этажей последовательно. Если на каком-то разобьётся (например, на 50), то вторым кирпичом добиваем от предыдущего проверенного до номера на котором разбилось (от 26 до 49) невключительно. В худшем случае до 28 (4+24) бросков. > Ан, нет! > Извиняюсь, перепроверил, получилось от 2-х до 18 :-)
Хм. Действительно, если бросать каждый 10 этаж то от 1 до 18 попыток. Самое оптимальное.
> Бочки с вином напомнили одну добротную задачку: > Есть 100-этажка. При броске с кирпича с определённого этажа кирпич ломается (и со всех более высоких этажей - тоже сломается, а с более низких - нет). У нас есть 2 одинаковых кирпича. Требуется как можно быстрее (за наименьшее число бросков) выяснить этот самый номер этажа, с которого кирпичи начинают ломаться. > За сколько бросков вы справились бы?
Интересно, а с тремя кирпичами? И еще интереснее - оптимальное количество кирпичей для опытов!
Сейчас, сейчас
Но как это ужать в два приема не знаю. В лучшем случае у меня получается три, в худшем -четыре.