задачи по дискретной математике 1000 банок с пилюлями
занумеруем все банки числами 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 чел,но нельзя выбирать враждующих друг с другом.скольким числом способов можно это сделать?
спасибо!
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
взвешиваний.
Однако, при двоичном поиске мы пренебрегаем дополнительной информацией (истинный вес кучи). Возможно, удастся придумать такой план поиска, при котором вся информация будет учитываться, и тогда нам удастся обойтись меньшим числом взвешиваний. Но кажется, что ни фига такого придумать не получится. По-хорошему, надо рассчитывать энтропию, но это муторно.
Пусть 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*120*24 способа
объясни! по-моему 1 решение про кучки таблетками правильное!


наверно различаются, там же хотят все возможные способы, а это тоже способ. хотя.... как это можно предусмотреть в ответе на задачу? как 2 варианта написать?
это почетное право предоставляю тебе! а что ты сделала в свои годы для дискретной математики? внеси свою лепту в общее дело!

ну ты даешь! откуда все знаешь?тяжелое олимпиадное прошлое и ММ сделали свое дело
спасибо!

а про сестер?

Сейчас напишу про соседей-врагов

Пусть мы уже рассадили этих "человеков" в соответсвии с условием. Выберем одного из них. По бокам от него, по условию, не могут сидеть другие "человеки". Поэтому осталось найти число способом рассадить 4 человека на 9 стульях, поставленных в ряд, так, чтобы никакие два человека не сидели рядом. А это в точности условие задачи про львов и тигров: "тигры" - стулья, на которых сидит человек, а "львы" - пустые стулья. Таким образом, задача сведена к предыдущей.

ОТВЕТ: 15
(здесь люди считаются неразличимыми, поэтому умножать на 5!*4! не надо!)
А ту что про анаграмму я написала? посмотрел?
пусть есть 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 взвешивание определить банку?