Сообщение Re: Необычная задача на измерения (два типа шариков) от 09.04.2025 8:06
Изменено 09.04.2025 8:20 Chorkov
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 в среднем (точно равно (N+M)/2, только для N+M, равных степени двойки).
S>Попадалась ли вам такая задача:
S>
S>Есть два типа шариков — шарики типа А и шарики типа Б. Так же есть специальное устройство — в него можно поместить множество шариков — устройство скажет сколько процентов шариков типа А.
S>Сколько нужно измерений, чтобы разделить на 2 кучи 1 миллион шариков (в одной куче только А, в другой гарантированно только Б)?
S>Можно чуть изменить:
S>
S>Есть один миллион яиц, среди которых часть тухлых а часть нормальных. Нужно отобрать все тухлые яйца. При этом есть прибор, в который можно поместить все яйца и получить количество тухлых — в лбом количестве. Сколько минимум измерений этим прибором нужно сделать, чтобы отобрать все тухлые яйца?
S>deepseek говорит что нужно 1 млн. измерений.
S>gpt o1 точно не знает, говорит что около ≈50000 измерений.
Мы минимизируем число измерений в худшем случае, или мат. ожидание?
Нам известно заранее число шариков каждого вида (M и N), или только M+N. Т.е. через какой параметр выражать ответ?
Принадлежность шарика к каждой группе равновероятна, или есть заранее известная диспропорция, как с яйцами?
Если равновероятно, и заранее известна только общая сумма, то (N+M) — в худшем, и примерно (N+M)/3 в среднем (для достаточно больших M+N).
Алгоритм:
0) Взвешиваем все. Узнаем M и N.
1) Если M==0 или N==0 — ничего делать не надо. (Вероятность 2^-(N+M-1)).
2) Делим группу примерно пополам, взвешиваем одну половину. Узнаем N', M' для каждой половины.
3.1) Выполнить П.1 для первой половины,
3.2) Выполнить П.1 для второй половины,