Поиск заряженных шаров - исследование задачи

[General]

По ходу решения задачи про нахождение 2 радиоактивных шаров из 15 за 7 попыток, которая рассматривалась здесь, возникла идея вариации условий следующим образом:

Из n шаров один заряжен положительно, другой отрицательно, остальные - нейтральны. Существует прибор, который при поднесении его к группе шаров выдаст или "+" (если там есть положительный шар), или "-" (в случае отрицательного шара), или "0" (если там все шары нейтральны, либо находятся одновременно положительный и отрицательный шары).

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

Насколько сейчас можно сказать, из 5 можно найти за 3 измерения, из 8 выйти на 4 не получается, приходится тратить 5 измерений, из 12 тоже можно за 5.

[Руст]

Занумеруем шары от 0 до n-1. В двоичной системе всего $k=[log_2(n-1)]+1$ разрядов. Так как номера N+ шара + и N- шара - отличаются хотя бы в одном разряде. То поднося кучы шаров у которых на i-ом разряде 0 как махимум за к шагов отделим + шар от - шара, далее за к-1 ходов находим + шар и за к-1 - шар, т.е общее число ходов 3k-2.
На самом деле если при определении различающегося разряда сделано l ходов, которые не разделили кучы с + шаром от кучи - шара, то эта информация используется после определения позиции + шара при определении позиции - шара, так как в этих разрфдях у них одинаковые цифры. Поэтому можно обойтись за 2k-1 ходов. В случае, когда один разряд заполнен не более чем на половину можно уменьшить число ходов ещё на 1. С учётом этого получается если $2^{k-1}< n\le 3*2^{k-2}$ g(n)=2k-2, если $3*2^{k-2}<n\le 2^k$ то $g(n)=2k-1$.

[General]

Возможно, где-то надо уточнить оценку, т.к. для 5 шаров $2^2< 5\le 3*2^1$ g(5)=3. И (на всякий случай перепроверю, но скорее всего, так и будет) для 18 шаров нужно сделать 6 измерений, а для 19 - уже 7.

Оценку снизу можно провести таким образом: всего имеется n(n-1) вариантов расположения положительного и отрицательного шаров. За одно измерение мы, получая 1 ответ из 3х можем уменьшить неопределённость не более чем втрое. Таким образом, $g(n)\geqslant Ceil(log_3((n)(n-1)))$.

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

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