Здравствуйте, Shmj, Вы писали:

S>Попадалась ли вам такая задача:

S>

S>Есть два типа шариков — шарики типа А и шарики типа Б. Так же есть специальное устройство — в него можно поместить множество шариков — устройство скажет сколько процентов шариков типа А.
S>Сколько нужно измерений, чтобы разделить на 2 кучи 1 миллион шариков (в одной куче только А, в другой гарантированно только Б)?

S>Можно чуть изменить:

S>

S>Есть один миллион яиц, среди которых часть тухлых а часть нормальных. Нужно отобрать все тухлые яйца. При этом есть прибор, в который можно поместить все яйца и получить количество тухлых — в лбом количестве. Сколько минимум измерений этим прибором нужно сделать, чтобы отобрать все тухлые яйца?

S>deepseek говорит что нужно 1 млн. измерений.
S>gpt o1 точно не знает, говорит что около ≈50000 измерений.

Мы минимизируем число измерений в худшем случае, или мат. ожидание?
Нам известно заранее число шариков каждого вида (M и N), или только M+N. Т.е. через какой параметр выражать ответ?
Принадлежность шарика к каждой группе равновероятна, или есть заранее известная диспропорция, как с яйцами?

Если равновероятно, и заранее известна только общая сумма, то (N+M) — в худшем, и примерно (N+M)*2/3 в среднем (для достаточно больших M+N).


Алгоритм:
0) Взвешиваем все. Узнаем M и N.
1) Если M==0 или N==0 — ничего делать не надо. (Вероятность 2^-(N+M-1)).
2) Делим группу примерно пополам, взвешиваем одну половину. Узнаем N', M' для каждой половины.
3.1) Выполнить П.1 для первой половины,
3.2) Выполнить П.1 для второй половины,