задачи по дискретной математике 1000 банок с пилюлями
за одно взвешивание определить, в какой банки подделка, можно следующим образом:
занумеруем все банки числами 1, 2, 3, ... , 1000
требуется найти номер N бракованной банки
на весы положим одну пилюлю из первой банки, две пилюли из второй банки, три пилюли из третьей банки и т.д.; и все это "хозяйство" взвешиваем.
если бы все пилюли были нормальные, то вес "хозяйства" = (число пилюль на весах)*(вес одной пилюли) = 1000*1001/2 = V1
мы же получим, что вес "хозяйства" V2 несколько больше, так на весах лежит N фальшивых пилюль из N-ой банки; поэтому ответом будет служить N = (V2 - V1)/0.1 = 10*(V2-V1)
вот и все
занумеруем все банки числами 1, 2, 3, ... , 1000
требуется найти номер N бракованной банки
на весы положим одну пилюлю из первой банки, две пилюли из второй банки, три пилюли из третьей банки и т.д.; и все это "хозяйство" взвешиваем.
если бы все пилюли были нормальные, то вес "хозяйства" = (число пилюль на весах)*(вес одной пилюли) = 1000*1001/2 = V1
мы же получим, что вес "хозяйства" V2 несколько больше, так на весах лежит N фальшивых пилюль из N-ой банки; поэтому ответом будет служить N = (V2 - V1)/0.1 = 10*(V2-V1)
вот и все
кто помнит или знает комбинаторику?
вот еще задачки:
1. скольким числом способов можно вывести на арену цирка 5 львов и 4 тигра так,чтобы никакие 2 тигра не шли друг за другом?
2.за столом 12 человек.из них каждый враждует со своим соседями.нужно выбрать 5 чел,но нельзя выбирать враждующих друг с другом.скольким числом способов можно это сделать?
вот еще задачки:
1. скольким числом способов можно вывести на арену цирка 5 львов и 4 тигра так,чтобы никакие 2 тигра не шли друг за другом?
2.за столом 12 человек.из них каждый враждует со своим соседями.нужно выбрать 5 чел,но нельзя выбирать враждующих друг с другом.скольким числом способов можно это сделать?
спасибо!
еще задача
4 сестры моют посуду по очереди.из 4 тарелок 3 разбито младшей,и поэтому ее называют неуклежей! можно ли ее оправдать,приписав эти неудачи случайности?(вы должны сами придумать,какие вероятности здесь считать)
4 сестры моют посуду по очереди.из 4 тарелок 3 разбито младшей,и поэтому ее называют неуклежей! можно ли ее оправдать,приписав эти неудачи случайности?(вы должны сами придумать,какие вероятности здесь считать)
задачу про тигров и львов можно легко решить с помощью производящей функции, но, подозреваю, такое решение не покатит
поэтому простой перебор
поэтому простой перебор
сколькими числом способов можно прочитать анаграмму C'est l'enfer qui m'a cree -"меня создал ад"? (кстати,при одном из способов расшифровки получается имя убийцы франзуского короля Генриха 3;противники короля,правда тоже не остались в долгу и из его имени- Henri de Valois-сделали анаграмму Vilain Herodes-"иродова мерзость" )анаграммы вырзить тайные мысли. не предложите ли вы какой-нибудь анаграммы на злобу дня?
Взвешивание на каких весах? Какое количество можно взвешивать одновременно? Зачем нам дополнительная информация (количество и вес пилюль)?
двоичная энтропия исходной задачи = log_2(1000) = 3*log_2(10)
Случай чашечных весов.
Если взвешивание производится на чашечных весах (то есть мы сравниваем веса двух наборов банок то энтропия такого опыта не превышает log_2(3):
1) энтропия равна нулю, если мы сравниваем веса двух наборов с различным числом банок (с вероятностью 1 перевесит тот набор, в котором банок больше)
2) если же мы сравниваем веса двух наборов по k банок, и при этом еще m банок имеют невыясненый вес (а про оставшиеся 1000 - 2k - m банок мы уже знаем, что они хорошие то энтропия взвешивания считается так:
исход "перевесила первая кучка" - вероятность k/(2k+m)=p1
исход "перевесила вторая кучка" - вероятность k/(2k+m)=p2
исход "кучки имеют равный вес" - вероятность m/(2k+m)=p3
энтропия h = -p1*log_2(p1) -p2*log_2(p2) - p3*log_2(p3)<= log_2(3)
Энтропия k взвешиваний не превышает kh<= k*log_2(3).
Чтобы выбрать исходную энтропию, потребуется не менее
k = ceil( log_2(1000)/ log_2(3) ) = ceil(6.28) = 7 взвешиваний.
Итак, менее чем за 7 определить не удастся. Осталось только проверить, есть ли такой план поиска, при котором 7 взвешиваний достаточно. Вот этот план:
делим 1000 банок на кучки по 333, 333 и 334, взвешиваем и определяем кучку, в которой плохая банка, размер кучи не превышает 334. Делим на кучки по 111, 111 и 112... и так далее. После 6 взвешиваний останется не более двух банок, после семи все будет определено.
Случай обычных весов.
Если взвешивание производится на обычных весах (показывающих вес то тут все хитрее. Можно, конечно, воспользоваться двоичным поиском, то есть не обращать внимание на собственно вес кучи, а только смотреть, есть ли во взвешиваемой куче фальшивка. Тогда энтропия (точнее, информация) одного опыта не превысит log_2(2)=1, и нужно не менее
ceil( log_2(1000)/1 )= 10
взвешиваний.
Однако, при двоичном поиске мы пренебрегаем дополнительной информацией (истинный вес кучи). Возможно, удастся придумать такой план поиска, при котором вся информация будет учитываться, и тогда нам удастся обойтись меньшим числом взвешиваний. Но кажется, что ни фига такого придумать не получится. По-хорошему, надо рассчитывать энтропию, но это муторно.
двоичная энтропия исходной задачи = log_2(1000) = 3*log_2(10)
Случай чашечных весов.
Если взвешивание производится на чашечных весах (то есть мы сравниваем веса двух наборов банок то энтропия такого опыта не превышает log_2(3):
1) энтропия равна нулю, если мы сравниваем веса двух наборов с различным числом банок (с вероятностью 1 перевесит тот набор, в котором банок больше)
2) если же мы сравниваем веса двух наборов по k банок, и при этом еще m банок имеют невыясненый вес (а про оставшиеся 1000 - 2k - m банок мы уже знаем, что они хорошие то энтропия взвешивания считается так:
исход "перевесила первая кучка" - вероятность k/(2k+m)=p1
исход "перевесила вторая кучка" - вероятность k/(2k+m)=p2
исход "кучки имеют равный вес" - вероятность m/(2k+m)=p3
энтропия h = -p1*log_2(p1) -p2*log_2(p2) - p3*log_2(p3)<= log_2(3)
Энтропия k взвешиваний не превышает kh<= k*log_2(3).
Чтобы выбрать исходную энтропию, потребуется не менее
k = ceil( log_2(1000)/ log_2(3) ) = ceil(6.28) = 7 взвешиваний.
Итак, менее чем за 7 определить не удастся. Осталось только проверить, есть ли такой план поиска, при котором 7 взвешиваний достаточно. Вот этот план:
делим 1000 банок на кучки по 333, 333 и 334, взвешиваем и определяем кучку, в которой плохая банка, размер кучи не превышает 334. Делим на кучки по 111, 111 и 112... и так далее. После 6 взвешиваний останется не более двух банок, после семи все будет определено.
Случай обычных весов.
Если взвешивание производится на обычных весах (показывающих вес то тут все хитрее. Можно, конечно, воспользоваться двоичным поиском, то есть не обращать внимание на собственно вес кучи, а только смотреть, есть ли во взвешиваемой куче фальшивка. Тогда энтропия (точнее, информация) одного опыта не превысит log_2(2)=1, и нужно не менее
ceil( log_2(1000)/1 )= 10
взвешиваний.
Однако, при двоичном поиске мы пренебрегаем дополнительной информацией (истинный вес кучи). Возможно, удастся придумать такой план поиска, при котором вся информация будет учитываться, и тогда нам удастся обойтись меньшим числом взвешиваний. Но кажется, что ни фига такого придумать не получится. По-хорошему, надо рассчитывать энтропию, но это муторно.
не, перебором это гемор
Пусть a_k - количеслво способов вывести k тигров и k+1 льва на арену так, чтобы тигры не шли подряд. Нам надо найти a_4.
найдем рекуррентную формулу для a_k:
1)если в начале стоит тигр, то за ним должен стоять лев; в это случае (мы уже зафиксировали ТЛ...) число расстановок равно a_{k-1};
2)если в начале стоит Л, то дела обстоят хуже: обозначим b_k - количеслво способов вывести k тигров и k львов на арену так, чтобы тигры не шли подряд. Тогда, при фиксированном первом Л число способов расставить оставшихся зверей равна b_k;
Получили a_k= a_{k-1} + b_k;
найдем рекуррентную формулу для b_k:
1)если в начале стоит тигр, то за ним должен стоять лев; в это случае (мы уже зафиксировали ТЛ...) число расстановок равно b_{k-1};
2)если в начале стоит Л, то дальше всего одна возможность: Л ТЛТЛТЛТ.
Поэтому b_k=b_{k-1}+1; b_1=2 => b_k=k+1
Итак, a_k = a_{k-1} + k+1, a_0 = 1 => a_1 = a_0+2=3; a_2 = a_1+3=6; a_3 = a_2+4=10; a_4 = a_3+5=15. А для произвольного k получим a_k=(k+1)*(k+2)/2
Пусть a_k - количеслво способов вывести k тигров и k+1 льва на арену так, чтобы тигры не шли подряд. Нам надо найти a_4.
найдем рекуррентную формулу для a_k:
1)если в начале стоит тигр, то за ним должен стоять лев; в это случае (мы уже зафиксировали ТЛ...) число расстановок равно a_{k-1};
2)если в начале стоит Л, то дела обстоят хуже: обозначим b_k - количеслво способов вывести k тигров и k львов на арену так, чтобы тигры не шли подряд. Тогда, при фиксированном первом Л число способов расставить оставшихся зверей равна b_k;
Получили a_k= a_{k-1} + b_k;
найдем рекуррентную формулу для b_k:
1)если в начале стоит тигр, то за ним должен стоять лев; в это случае (мы уже зафиксировали ТЛ...) число расстановок равно b_{k-1};
2)если в начале стоит Л, то дальше всего одна возможность: Л ТЛТЛТЛТ.
Поэтому b_k=b_{k-1}+1; b_1=2 => b_k=k+1
Итак, a_k = a_{k-1} + k+1, a_0 = 1 => a_1 = a_0+2=3; a_2 = a_1+3=6; a_3 = a_2+4=10; a_4 = a_3+5=15. А для произвольного k получим a_k=(k+1)*(k+2)/2
там наверно обычные весы подразумеваются,а не чашечные,хотя хз в задании ничего не написанно конкретного по этому поводу, разве что фраза фраза: дефектная банка легко обнаруживается взвешиванием (1000взвешиваний!)
А блин! Теперь понятно, зачем пилюли.
ну ты даешь! откуда все знаешь? 
спасибо!
спасибо!
если же львы и тигры различаются, т.е. расстановка "лев Петя - тигр Вася - лев Митя" и расстановка "лев Митя - тигр Вася - лев Петя" различные, то полученное число 15 надо умножить на 5!*4!
Тогда получим 15*120*24 способа
Тогда получим 15*120*24 способа
объясни! по-моему 1 решение про кучки таблетками правильное!
я запапил
ты лучше введи задачу со стихотворением, интересно узнать, ктонидь разгадает 
наверно различаются, там же хотят все возможные способы, а это тоже способ. хотя.... как это можно предусмотреть в ответе на задачу? как 2 варианта написать?
это почетное право предоставляю тебе! а что ты сделала в свои годы для дискретной математики? внеси свою лепту в общее дело!
решаю задачи по корфу-мой вклад в дискретную математику, могу сказать где все значки искать
ну ты даешь! откуда все знаешь?тяжелое олимпиадное прошлое и ММ сделали свое дело
спасибо!
а про сестер?
Про систер задача какая-то идиотская, т.е. я ее не понял
Сейчас напишу про соседей-врагов
Сейчас напишу про соседей-врагов
Ну спасибо!
Переформулировка: нужно найти число рассадок 5 человек за столом на 12 персон так, чтобы эти "человеки" не сидели рядом.
Пусть мы уже рассадили этих "человеков" в соответсвии с условием. Выберем одного из них. По бокам от него, по условию, не могут сидеть другие "человеки". Поэтому осталось найти число способом рассадить 4 человека на 9 стульях, поставленных в ряд, так, чтобы никакие два человека не сидели рядом. А это в точности условие задачи про львов и тигров: "тигры" - стулья, на которых сидит человек, а "львы" - пустые стулья. Таким образом, задача сведена к предыдущей.
ОТВЕТ: 15
(здесь люди считаются неразличимыми, поэтому умножать на 5!*4! не надо!)
Пусть мы уже рассадили этих "человеков" в соответсвии с условием. Выберем одного из них. По бокам от него, по условию, не могут сидеть другие "человеки". Поэтому осталось найти число способом рассадить 4 человека на 9 стульях, поставленных в ряд, так, чтобы никакие два человека не сидели рядом. А это в точности условие задачи про львов и тигров: "тигры" - стулья, на которых сидит человек, а "львы" - пустые стулья. Таким образом, задача сведена к предыдущей.
ОТВЕТ: 15
(здесь люди считаются неразличимыми, поэтому умножать на 5!*4! не надо!)
А ту что про анаграмму я написала? посмотрел?
ну там вообще просто формула есть:
пусть есть k_1 букв А, k_2 букв Б, k_3 букв В и т.д. - всего N букв.
тогда из этого набора букв можно составить
N!/{(k_1)!(k_2)!(k_3)!...} разных слов
пусть есть k_1 букв А, k_2 букв Б, k_3 букв В и т.д. - всего N букв.
тогда из этого набора букв можно составить
N!/{(k_1)!(k_2)!(k_3)!...} разных слов
C'est l'enfer qui m'a creeс - 2; e - 5; s - 1; t - 1; l - 1; n - 1; f - 1; r - 2; q - 1; u - 1; i - 1; m - 1; a - 1.
Всего 19, поэтому ОТВЕТ: 19!/{2*2*120}
а когда зачет то? а остальные решают? а со стихом сделали? кот я вам пишу....
Похожие темы:
Оставить комментарий
alex2008alex
В аптеку поступила партия лекарства-1000банок с пилюлями(в каждой банке 1000пилюль по 1 грамму) в одной из банок левые пилюли 1000штук(по 1.1 грамма) какое минимальное число взевишиваний надо сделать для определения дефективной банки. можно ли за 1 взвешивание определить банку?