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

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

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

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

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

999999 измерений достаточно

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

S>

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

Если ты делаешь только измерения и больше ничего другого, то у тебя как было так и останется миллион перемешанных шариков.

Ответ наверное такой:
1) Например, шарики можно мерять группами по два. Если оба чёрные, то ты знаешь, что они оба чёрные.
2) Если оба белые, то аналогично.
3) А если один чёрный другой белый, то дополнительно меряешь один шарик, а другой имеет противоположный цвет.

То есть в случае 3 у тебя число измерений равно числу шариков.
А в случаях 1 и 2 ты одно измерение экономишь.

Наверное эту идею можно развить и для более крупных групп.

ЧатГПТ — дурак.

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

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

S>>

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

A>Если ты делаешь только измерения и больше ничего другого, то у тебя как было так и останется миллион перемешанных шариков.

A>Ответ наверное такой:
A>1) Например, шарики можно мерять группами по два. Если оба чёрные, то ты знаешь, что они оба чёрные.
A>2) Если оба белые, то аналогично.
A>3) А если один чёрный другой белый, то дополнительно меряешь один шарик, а другой имеет противоположный цвет.

A>То есть в случае 3 у тебя число измерений равно числу шариков.
A>А в случаях 1 и 2 ты одно измерение экономишь.

A>Наверное эту идею можно развить и для более крупных групп.

A>ЧатГПТ — дурак.


Вот если у нас есть уже несколько групп шариков для которых уже было произведено измерение, можем ли мы теперь их как-то между собой смешать, что бы получилась группа в которой процент шариков А больше чем в любой группе до этого? Ответ очевиден. Так что возможно все мерить придется.

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

для трёх щариков аналогично получается 75%:
а 1/4 случаев потребуется одно измерение ААА и БББ
если одного типа — 2, а другого 1, тогда берём любой шарик и проверяем его цвет. В 1/3 случаев второго измерения не понадобится. То есть в 3/4 * 1/3 = 1/4 случаев потребуется 2 измерения.
В остальных случаях — 3.
Суммируя получаем те же 75%.
Так что может больше выжать на такой идее и не получится.

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

A>Если ты делаешь только измерения и больше ничего другого, то у тебя как было так и останется миллион перемешанных шариков.

Ну можно разделять на кучки — сортировать кучки по количеству шариков типа А.

A>Ответ наверное такой:
A>1) Например, шарики можно мерять группами по два. Если оба чёрные, то ты знаешь, что они оба чёрные.
A>2) Если оба белые, то аналогично.
A>3) А если один чёрный другой белый, то дополнительно меряешь один шарик, а другой имеет противоположный цвет.

А если больше чем 2 — не получится более оптимально?

A>Наверное эту идею можно развить и для более крупных групп.

Вот это и интересно.

З.Ы.
При кажущейся малозначимости задачи — возможно в ней отражен смысл существования человечества.

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

S>З.Ы.
S>При кажущейся малозначимости задачи — возможно в ней отражен смысл существования человечества.

Да это-то понятно. У тебя разве есть другие задачи.

Здравствуйте, 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 для второй половины,

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

R>У тебя разве есть другие задачи.
rg45...
«Шо? Опять?» (голосом волка из известного мульта)...
Давненько Шмыджика не склоняли....

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

C>Мы минимизируем число измерений в худшем случае, или мат. ожидание?

Обычно в задачах подобного рода требуется найти число измерений (взвешиваний), которым гарантированно можно достичь поставленной цели. Т.е. худший случай. Конечно, существуют и задачи на нахождение матожидания, но в этих задачах обычно говорится об этом явно.

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

S>deepseek говорит что нужно 1 млн. измерений.

Это тупая оценка сверху, просто берём и проверяем каждый шарик отдельно.

Сформулируем такую гипотезу.
Если число шариков первого сорта a из n известно, то нужно V(a,n) взвешиваний.
Если неизвестно, то нужно U(n) взвешиваний.
Очевидно, что U(n) <= V(a,n)+1, потому что мы можем первым взвешиванием узнать a из n, и сведём задачу к предыдущей.

Заметим, что у нас тут симметрия: V(n-a, n) = V(a, n).
Просто переименовываем шарики первого и второго сортов.

Интуитивно кажется очевидным, что самый худший случай — это V(n/2, n). Наибольшая неопределённость.
А наилучший случай — это V(0, n) = V(n, n) = 0. Ничего взвешивать не надо.

Ну и понятно, что U(0) = V(0, 0) = 0.

Vmax(n) = max V(a, n) | a <- 0..n

Vmax(1) = max{V(0,1), V(1,1)} = max{0, 0} = 0.

Сформулируем нашу интуитивную гипотезу, что Vmax(n) = V(n/2,n).
Или, в целых числах, Vmax(2n) = V(n,2n), Vmax(2n+1) = V(n,2n+1) = V(n+1,2n+1).
Доказывать не буду, но посмотрю, что из этого следует.

Попробуем родить рекуррентную формулу.

Разобъём n на x + y.
Взвесим x, найдём там ax.
Автоматически найшли ay = a-ax.
V(a, n) = 1 + V(ax, x) + V(a-ax, n-x).
Худший случай — это чтобы ax ~ x/2 и a-ax ~ (n-x)/2

Посмотрим стратегию x = 1.

V(ax,1) = 0, это мы уже выяснили.

V(a, 2n) = 1 + V(ax, 1) + V(a-ax, 2n-1) = 1 + V(a-ax, 2n-1).
Худший случай, это a=n, a-ax ~ (2n-1)/2 = n-1/2 ~ n-1
V(n, 2n) = 1 + V(n-1, 2n-1).

V(a, 2n+1) = 1 + V(ax, 1) + V(a-ax, 2n) = 1 + V(a-ax, 2n)
Худший случай — a=n, a-ax = n, то есть, ax = 0.
V(n, 2n+1) = 1 + V(n, 2n).

Получается, что Vmax(n) = 1 + Vmax(n-1) = 2 + Vmax(n-2) = ... n-1 + Vmax(1) = n-1.

Посмотрим на стратегию x = n/2.
Худшие случаи:
V(2n, 4n) = 1 + V(n, 2n) + V(n, 2n)
V(2n, 4n+1) = 1 + V(n, 2n) + V(n, 2n+1)
V(2n+1, 4n+2) = 1 + V(n+1, 2n+1) + V(n+1, 2n+1)
V(2n+1, 4n+3) = 1 + V(n, 2n+1) + V(n+1, 2n+2)

Vmax(4n) = 1 + Vmax(2n) + Vmax(2n)
Vmax(4n+1) = 1 + Vmax(2n) + Vmax(2n+1)
Vmax(4n+2) = 1 + Vmax(2n+1) + Vmax(2n+1)
Vmax(4n+3) = 1 + Vmax(2n+1) + Vmax(2n+2)

то есть
Vmax(2n) = 1 + 2 * Vmax(n)
Vmax(2n+1) = 1 + Vmax(n) + Vmax(n+1)

Раскрутим рекурсию в индукцию
Vmax(0) = 0
Vmax(1) = 0
Vmax(2) = 1 + Vmax(1) + Vmax(1) = 1
Vmax(3) = 1 + Vmax(1) + Vmax(2) = 2
Vmax(4) = 1 + Vmax(2) + Vmax(2) = 3
Vmax(5) = 1 + Vmax(2) + Vmax(3) = 4

Гипотеза. Vmax(n) = n-1
Тогда
Vmax(2n) = 1 + (n-1) + (n-1) = 2n-1
Vmax(2n+1) = 1 + (n-1) + (n) = 2n
Индукция доказана.

Таким образом, из предположения, что Vmax(n) = V(n/2, n), следует, что Vmax(n) = n-1, а значит, U(n) = 1 + Vmax(n) = n.

Вуаля.
Нам в худшем случае потребуется миллион взвешиваний для миллиона шариков.

Теперь надо как-то доказать предположение.
Так-то понятно, что
V(0,n) = 0,
V(1,n) сводится к дихотомии (поиск одного шарика в куче) = log2(n)
V(2,n) сводится к двум дихотомиям: найти кучку, в которой оказались оба шарика, но каждый в своей под-кучке, — в плохом случае мы на первом же шаге такое получили, V(2,n) = 1 + V(1,n/2) + V(1,n-n/2) = 1 + 2*log2(n/2) = 2*log2(n) — 1
V(3,n) в общем-то, та же история: сперва дихотомией концентрируем шарики в одной кучке, затем один шарик в одной и два в другой, затем те по разным. 1 + V(1,n/2) + V(2,n/2) = 3*log2(n/2) = 3*log2(n) — 3
V(4,n) — два налево два направо, и так далее: 1 + V(2,n/2)*2 = 4*log2(n/2) — 1 = 4*log2(n) — 5
V(a,n) ~ a*(log2(n)-2) + 1
Это, понятное дело, примерные оценки.
Видно, что оценка V(a,n) монотонно растёт, но мы-то знаем, что V(a,n) = V(n-a,n), поэтому где-то эта оценка должна засбоить и встретиться в точке симметрии V(n/2,n).

Железобетонное доказательство этого факта оставлю кому-нибудь другому.

-------
Можем ли мы поступить как-то иначе?
Разбить одну кучу несколькими способами, взвесить их и дальше работать с синдромом — вектором весов?

Ну, грубо говоря, пусть у нас 4n.
Разбили на 4 кучи по n.
Взвесили и получили a12 и a13.
a1 + a2 = a12; a3 + a4 = 4n — a12
a1 + a3 = a13; a2 + a4 = 4n — a13

откуда следует, что
a2 — a3 = a12 — a13

Для примера, пусть a12 = a13 = 2n
a1 + a2 = 2n
a1 + a3 = 2n
a2 + a4 = 2n
a3 + a3 = 2n

a1 = a4
a2 = a3
но мы не знаем, чему именно они равны. Там может быть что угодно от 0 до 2n.

Окей, потратим ещё одно взвешивание кучки номер 1.
Итого, за три взвешивания мы нашли a1, a2, a3 и автоматически a4.
Но мы и так могли это сделать. По отдельности.

Поэтому мне кажется, что синдромы нам тут не помогут. По крайней мере, в худшем случае.

------
Но это мы искали для худшего случая. Для среднего случая может быть всякое.
Кажется, что дихотомия — это самый простой, но в то же время самый верный способ.
За первое взвешивание узнали общее количество, а затем спускаемся делением пополам.

Посчитать матстат я не готов.
Можно разве что прикинуть лучший случай.
Пусть все искомые шарики находятся строго слева.
Тогда мы просто спустимся половинным делением к точке их разделения. На это уйдёт 1 + log2(n)-log2(a) или что-то в таком роде, лень думать уже.

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

C>>Мы минимизируем число измерений в худшем случае, или мат. ожидание?

Для худшего случая — миллион. Я доказаль.

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

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

Моя интуиция мне подсказывает, что оптимизировать количество измерений можно пытаться только если процентное соотношение не близко к 50%.
Это просто: взвешиваем миллион. Если результат 50%, то взяв и взвесив половину мы получим те же 50%, Не, конечно, если перед взвешиванием в одну руку зажать четырехлистный клевер, а в другую подкову, то результат второго взвешивания будет 100% и задача решена. Таким образом, минимальное количество взвешиваний = 2.
Если же первое взвешивание покажет, что количество первого типа 1, а другого 999'999, то задача сводится к задаче о фальшивой монете...
Если же соотношение будет около 25%, то всё сложно... Тогда надо взвешивать группами, то ли по 8, то ли по 4. Однако если нам очень-очень не повезёт, то во всех группах получится то же процентное число...

Короче, в среднем измерений нужно меньше миллиона, но в редких случаях их потребуется миллион.

Кстати, задача была бы интереснее, если шары нельзя помечать, а измерение перемешивает шары и выдаёт только соотношение, но не даёт информации о принадлежности к группе:
Есть два типа шариков — шарики типа А и шарики типа Б. Так же есть специальное устройство — в него можно поместить множество шариков.
Устройство измеряет соотношение типов шариков: x/y, где x <= y в зависимости от того, какого типа шариков больше.
Сколько нужно измерений, чтобы разделить на 2 кучи 1 миллион шариков (в одной куче только А, в другой гарантированно только Б)?

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

M>999999 измерений достаточно
разве?

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

BFE>Кстати, задача была бы интереснее, если шары нельзя помечать, а измерение перемешивает шары и выдаёт только соотношение, но не даёт информации о принадлежности к группе:
BFE>Есть два типа шариков — шарики типа А и шарики типа Б. Так же есть специальное устройство — в него можно поместить множество шариков.
BFE>Устройство измеряет соотношение типов шариков: x/y, где x <= y в зависимости от того, какого типа шариков больше.
BFE>Сколько нужно измерений, чтобы разделить на 2 кучи 1 миллион шариков (в одной куче только А, в другой гарантированно только Б)?

А вот это уже, наверное, прикольно.

Начнём с малого.

1 шарик. Тривиально. Разбиваем на 0 и 1, в одной куче ничего, в другой гарантированно одно и то же.

2 шарика.
— взвешиваем 2.
— — если соотношение 0:2, то разбиваем на 0 и 2
— — если 1:1, то на 1 и 1

3 шарика.
А вот тут, кажется, мы зациклимся. Смотрите:
обозначим шарики номерами 1, 2, 3. И будем отслеживать все возможные их сочетания, с точностью до симметрии.

Первое взвешивание {1,2,3}.
Если соотношение 0:3, то тривиально. {} и {1,2,3}.
Если же нет, то...

Взвешиваем {1,2}.
Если 0:2, то {1,2} и {3}.
Если же нет, то...

Взвешивать шарики по одному, очевидно, бессмысленно. По три уже взвесили. Будем взвешивать пары...
Взяли из {1,2} один шарик (пусть 1), соединили с 3.

{1,3}
Если 0:2, то {1,3} и {2}.
Если же нет, то... 3 != 1 != 2, вот только мы не знаем, который из 1 и 3 — номер 1.

Взяли один шарик, соединили с 2.
Получилась куча {1,2} либо {2,3}.

Опять же, в плохом случае, пусть результат взвешивания 1:1.
Если это была куча {1,2} — мы зациклились.
Если это была {2,3}, ну ок, — 1 != 2 != 3, но мы теперь не знаем, который из них — номер 2.

Вердикт: это неприкольно. Задача просто стала нерешаемой.

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

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

M>>999999 измерений достаточно
BFE>разве?

Только если нам надо разделить на две группы в каждой из которых содержатся шарики одного сорта, но ненужно знать, какого сорта шарики содержатся в конкретной группе.
Например, взвешивая два шарика мы гарантированно узнаем принадлежат ли они одной группе, и только с вероятность 50% (если они принадлежат одной группе) узнаем к какой именно группе.

Взвешиваем пары шариков: 1й + 2й, 1й+3й, ... 1й+100000й. Всего 999999 взвешиваний. Гарантированно узнаем должен ли каждый шарик лежать в одной группе с первым, или нет. Но, если не повезет, и первый шарик имеет не тот же тип что остальные — то не узнаем кто в какой кучке.

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

C>Взвешиваем пары шариков: 1й + 2й, 1й+3й, ... 1й+100000й. Всего 999999 взвешиваний. Гарантированно узнаем должен ли каждый шарик лежать в одной группе с первым, или нет.

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

C> Но, если не повезет, и первый шарик имеет не тот же тип что остальные — то не узнаем кто в какой кучке.
Этого я не понял.