в третьем варианте кажется тоже накосячил

BarloneТретий случай. check(1,2,15)=false, check(3,6,7)=true
Проверяем 7-14
При положительном результате (слева) всегда 3 + один из 7-14, который выберем за 3 шага делением пополам.
При отрицательном результате (справа) проверяем 3. Сверху + снизу -. Дальше понятно.
Это неправильно, на самом деле так: проверяем 4,5,6,7
слева отрицательный результат, справа положительный

Dima TPS Как ты это изобрел? У меня от проверки мозг закипает )))Так выписывал все возможные пары и подбирал проверки, делящие их пополам, дальше по рекурсии каждую половину. Иногда получается, что пополам никак не хочет делиться, и приходится вернуться назад и попробовать поделить по другому на более раннем шаге :)

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

Соколинский Борисmayton,
Мы один столбец матрицы рассматриваем. Когда N=1 - очевидно логарифм.
Я ошибся в таблице
7-10 611-14 715-18(?) 8
Отношение N/M, сдается мне, должно к гамма-распределению (N-параметр) сводиться.Ну для 7 то точно достаточно 5 тестов. Для 15 вроде после исправлений нормально за 7 шагов получается.

BarloneDima Tтогда для 15 неправильно С(2,15)=105, т.е. тоже 7, а ответ 8.

PS Я не считал, просто заметил что log2(91) = log2(105)А вы попробуйте доказать, что за 7 невозможно :)Я кстати начал с того, что пытался доказать невозможность. А получилось вот так.

Aleksandr SharahovBarloneпропущено...
Я кстати начал с того, что пытался доказать невозможность. А получилось вот так.

Теперь можно начать с того, что попытаться доказать невозможность для 2 из 16 )Ну на 2 из 16 точно нужно 8 шагов.

NC(2;N)steps3324635104615 5 7215828 6 9366104561155 7 12667137871491715105716120 8
Вот такая табличка пока. Для N = 6, 8, 11, 16 получается необходимое число измерений больше, чем округление вверх двоичного логарифма числа сочетаний по 2 из N.
Как вообще такое можно доказать? Ну примерно так:
До первого измерения все равноправны, поэтому тут важно только количество шаров, от выбора номеров ничего не зависит. Изначальное число вариантов C(2;N). Если у нас N шаров и на первом тесте мы проверяем K из них, то при отрицательном результате мы получаем задачу меньшей размерности: с N-K шарами. А при положительном результате первого теста ситуация получается более сложная, но общее количество оставшихся вариантов получается C(2;N)-C(2;N-K).
Для 6 я уже писал почему недостаточно 4 измерений, ну давайте еще раз напишу. Если на первом шаге измерять один шар, то при отрицательном ответе мы остались с 5 шарами, на которые надо 4 измерения. А если на первом шаге измерять 2 шара, то при отрицательном ответе у нас остается 4 шара (тут 3 измерений достаточно), но при положительном ответе у нас остается С(2;6) - С(2;4) = 15-6 = 9 вариантов, за 3 измерения их не разделить.

Переходим к 8 шарам. Можно попробовать взять для первого измерения 2 или 3 шара (в других случаях будет только хуже).
Если возьмем 2, то при отрицательном ответе приходим к задаче 6 шаров, для которой надо 5 измерений.
Если возьмем 3, то при положительном ответе остается С(2;8) - С(2;5) = 28 - 10 > 16 и опять нужно еще 5.

Теперь 11 шаров. Если первый раз будем мерять 3 шара, при отрицательном ответе приходим к задаче 8 шаров, на которую как только что показали, нужно 6 измерений. Если первый раз меряем 4, С(2;11) - С(2;7) = 55 - 21 > 32 и опять еще 6.

Ну и 16 шаров. Первый раз меряем 5 шаров, ну и тут по 7 измерений в обоих ветках - либо 11 шаров, либо 120 - 55 > 64.
При другом числе шаров для первого измерения в одной из веток получим еще больше вариантов.

Dima TА как же формула?
BarloneНижняя граница - двоичный логарифм числа сочетаний из N по M (с округлением вверх).
Так нижняя же, при некоторых значениях N недостижимая (дважды уже повторял). В чем вообще ее смысл - если нашли алгоритм с таким числом шагов, то быстрее точно не получится. А если не нашли - то надо либо искать дальше, либо пытаться доказать, что это невозможно.

Вот примерно с такого же я пытался начать доказывать, что 2 из 15 за 7 шагов нельзя, но С(2;15) - С(2;10) = 60, и эти 60 за 6 шагов получилось поделить.

kealon(Ruslan)Barlone,
доказать возможность гораздо легче, чем невозможность - достаточно пример
во втором же случае неудачные примеры доказательством не являются, если конечно речь не о доказательстве какого-то конкретного алгоритма, а у нас его пока нету

например, до прошлого века вообще считали, что невозможно умножать быстрее чем O(N^2)То есть мое доказательство 21827278 вас не убедило?

kealon(Ruslan), ну тут то количество возможных алгоритмов конечно - 2 ^N вариантов одного теста (2 ^N -2 если выкинуть явно бессмысленные варианты проверять 0 шаров или сразу все шары).