У нас есть N ключей {К1,К2,...,КN} и столько же замков {З1,З2,...,ЗN}. Будем считать, что и те как-то пронумерованы. Каждый ключ подходит ровно к одному замку.
Вы хотите определить какой ключ подходит к какому замку. Для этого разрешается проделывать следующую операцию:
Взять любое количество 1<=r<=N ключей и столько же замков и передать ключнику. Ключник проверяет все ключи и замки, отдает их обратно и говорит число пар ключ-замок, которые удалось подобрать, но не говорит сами пары.

За сколько таких операций можно узнать все пары соответствующих ключей/замков от количества N?

Для N=2 ответ 1.
Для N=3 ответ 3.

(0) А почему для N=3 ответ 3? Вполне можно и двумя обойтись, если первый и второй ключ подойдут с первой попытки.

(1) а если не подойдет?

+(0) пояснение "можно ГАРАНТИРОВАННО узнать"

(0)

Для N=2 ответ 1
Для N=3 ответ 2

хотя, нет. всё-таки 3, да

(3) Ну так, если сразу подойдет, то тоже гарантированно узнаешь. Имхо, правильное уточнение должно звучать так: "какое _максимальное_ кол-во операций для определения".
А для усложнения можно добавить "какое _минимальное_ и какое _максимальное_ кол-во операций."

каждый ключ поочередно проверяем с каждым замком(отдаем по одной паре ключ замок). Таким способом первый ключ отыщем гарантированно за N-1 операций(если предпоследний не подошел, последний можно не проверять), второй - за N-2 и т.д.
таким образом имеем арифметическую прогрессию - N-1, N-2, ... 2, 1.
Итого операций: N(N-1)/2

+(7) ааа, и проверку последней пары тоже можно не делать.
Тогда -  N(N-1)/2-1

+(8) хотя нет, все верно - N(N-1)/2

(8) Так неинтересно :)
А для минимального кол-ва операций посчитаешь?

(10) ))))))))
а про минимальное количество условия не было)
я вообще хотел сначала N*N написать, но потом сообразил, что это уж слишком избыточное количество

(3)
"которые удалось подобрать"
Ситуация:
ключ1 , ключ3, ключ15
и замок2 , замок8 , замок 28

Мое предположение, что при N=4 будет ответ 5

Что-то не пойму зачем в задачу добавлен выбор R. При R>1 количество операций только увеличивается

(7) Тоже по индукции нашёл такое решение, но ведь не факт, что это минимальное число операций.

(13) да, при N=4, попыток будет максимум 5, так что формула из 7 - не минимальное количество

(0) Не знаю ответ

(14) не факт. Проверяя 1 ключ вы получаете 1 бит информации, а проверяя 3 ключа - 2 бита.

(13) при N=4 меньше чем за 4 точно нельзя. А вот можно ли за 4?

(18) откуда там 2 бита?

(20) 4 результата проверки: 0,1,2,3
Конечно это если N>5.

(21) Тогда сколько бит получаем если проверяем два ключа?

(22)
Если бы три варианта были равновероятны (что в данном случае не так), то log2(3).
Только зря ты этот вопрос задал, сейчас опять срач не по теме будет ;)

Короче, максимально много информации получаем если проверяем половину ключей с первого раза.

Нужно теперь понять как получить максимально много информации на второй и последующих проверках.

(24) Это зависит от того какую задачу мы решаем (N=4 или общую).
В общем случае во второй проверке тоже должна быть половина (только в совершенно другой комбинации)

Если обрзначить каждый замок от 1 до н битом в позиции н,и аналогично ключи от 1 до н битом в позиции н
когда мы даем ключнику замки,то есть число из битов А, и ключи,то есть число из битов Б,то ключник вычисляет логическое И этих двух последовательностей битов,и возвращает как результат,количество битов в числе.
далее,требуется построить несколько последовательностей битов,чтобы они различались только одним битом и прогнать их через ключника

биты ключей мы знаем,а биты замков спрятаны от нас массивом С[з],массив знает только ключник,для каждого замка он выдает позицию бита
нужно определить этот массив

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

другими словами,делим замки и ключи на две кучи и гоняем 4 раза к ключнику,потом кучи переставляем по алгоритму срс и гоняем снова 4 раза и так по логарифму двух от количества мы прогоним всех по всем

(26)(27)(28) Звучит красиво, про "алгоритм СРС" правда даже яндекс ничего внятного не говорит.
Идея то на поверхности, проблема с "требуется построить несколько последовательностей битов,чтобы они различались только одним битом и прогнать их через ключника". Т.к. независимых последовательностей не так много, и построить по нужному условию не получится.

Давайте для N=4 решим

(26) Если честно не понял, как ты собрался набор из N ключей(количество перестановок = N!) собрался обозначать двоичным N-значным числом (количество возможных значений = 2^N)...

Может и правда, на примере N=4 продемонстрируешь?)

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

Для четырех получаются пары сначала к1,к2 и к3,к4 потом пары к1,к3 и к2,к6
так как из испытаний четверток избыточное,то гоняем 6 раз.
к1,к2 з[с[1]],з[c[2]]
к1,к2 и з[с[3]],з[с[4]]
к3,к4 и з[с[1]],з[с[2]]
к1,к3 и з[с[1]],з[с[3]]
к1,к3 и з[с[2]],з[с[4]]
к2,к4 и з[с[1]],з[с[3]]

хотя нет,в данном случае гонять первые ключи во вторую группу также не надо,т.к.
к1,к2 и з1,з2 это сколько ключей от первой группы подходит к замкам первой группы.очевидно,что к замкам второй группы подойдут остальные ключи.
к3,к4  з1,з2 сколько ключей из второй группы подходит к замкам первой группы.

(32) вот про это и говорилось в (29) что не получится

(10) А разве минималоьное количество не равно N-1?

т.е. оно разве не равно "угадал с первой попытки"?

(34)(35) Тогда уж 0, угадал с первой попытки и не стал проверять.
Естественно в нормальной формулировке вопрос будет содержать
"за какое МИНИМАЛЬНОЕ число попыток можно ГАРАНТИРОВАННО узнать"

Для краткости 1,2,3,4 - замки; А,Б,С,Д ключи.
В простейшем случае. худший вариант
1а -0
1б -0
1с -0 значит 1д подходят +3 для поиска среди 3 ответ 6
более сложный вариант
Отдаем 1а,2б,3с получаем ответ 0,1,2,3
А вот дальше в зависимости от цифры различные действия

(36) Слово ГАРАНТИРОВАННО тут не приносит никакой пользы. Тот кто не понял оригинальную формулировку, может так же сказать что если угадать с первой попытки, то ГАРАНТИРОВАННО узнаешь какой ключ от какого замка.

(13) Похоже, для N=4 хватит четырёх попыток.

Не, тупанул. Но тему надо было поднять :)

(40) +100))
Для N=4 получается за 5, и вроде получается доказать, что нельзя 4.

ТС колись. Откуда задача? Она должна аналитически решаться для произвольного N?

(41) на просторах интернета нашел
решения не знаю
хочется верить в формулу

[log2(N!)]+1 при N>2

(42) Похоже на энтропию.
К планированию экспериментов отношения не имеет?

(0) а почему нельзя сразу N отдать, он все и подберет.
нет?

(44) он скажет, что совпало N. Подбирать самому придется)))

(42) ну ка при N = 3 посчитай этот факториал)))

а все понял
у меня получилось
(N-1) + (N-2) + ... + (N-(N-1)
для 2 - 1
для 3 - 3
для 4 - 6

(47) ИМХО, должно быть меньше...
нужно другую стратеги выбирать, а не просто перебирать пары...

(46) 3!=6
2<log2(6)<3
[log2(6)]=2
итого 3

(49) а теперь для 4)

(50) для 4 тоже сойдется

(48) так это и должна быть другая стратегия. В случае перебора  пар ~N^2 будет.

(42) а алгоритм под формулу есть, хотя бы приблизительный?

(51) не сойдется...и для 3 не сходится...для 3-х можно за 2 сравнения все сделать...
формула, вроде, почти правильная...только +1 надо убрать...

(52) Для 3-ех за 2 - докажи...

(53) тоже интересно))

(51)(52) алгоритма пока нет
есть общие соображения

всего вариантов ключ-замок равно N!
вот если мы сможем за каждый раз "увеличивать информацию вдвое", то вот так и получим

в частности при N=3 имеем 6 вариантов и за два хода не удается найти нужную перестановку

У меня получилось:
N = 3 -> 3
N = 4 -> 6
N = 5 -> 10
N = 6 -> 15
N = 7 -> 21
А тут мне сунули таракана... И я испугалась :(((((((((((((((

(53) Смотри (1).

(57) Если да кабы во рту росли грибы. (С)
Да, не простые...

(58) Просто для любых N ключей и N замков есть максимальное кол-во комбинаций, позволяющих подобрать все пары, а есть минимальное.
Для N = 3, минимум - это 2, а максимум 3.

(55) Уже при N=4 "увеличивать информацию вдвое" не получается. При проверке двух пар в 16 случаях из 24 мы получим 1, т.е в этом случае область поиска сократится только в полтора раза. Проверять одну пару ещё хуже.

(55) А как ты себе это представляешь?
По любому, нужно или один ключ к каждому замку проверять, или один замок к каждому ключу.
И получается треугольник с катетами N-1.

(60) тоже об этом думал, но мы еще автоматически узнаём, что и в другой паре 1.
но пока мало понятно

(62) "еще автоматически узнаём, что и в другой паре 1" это уже  учтено в том, что 8 вариантов исключены, а 16 осталось.
Правда вторая проверка (тоже 2 пар) позволяет сузить область до 8 вариантов. Т.е. заветный 1бит во второй проверке мы получаем.

А почему для четырех четыре нельзя?
гоним к1,к2 и з1,з2
результат 0,1 или 2
(попутно тот же результат получается для к3,к4 и з3,з4)
если ответ 0,то меняем замки местами з1,з2 на з3,з4 и мы как бы получили 2.
Если 1,то гоним пару к1,к3 з1,з3 тут тоже ответ будет 0,1 или 2
если ноль,то к1 для з4,а к4 для з1,к3 остается для з2,а к2 для з3
если 1,то мы уперлись в к1 для з3 или к3 для з1,что то одно,нужно прогнать к1 и з3,чтобы это получить
если 1,то к1 для з3,к3 для з2,к2 для з4 и к4 для з1
то есть,три прогона.

или что то не так?

Четыре прогона,т.к.вторую пару точно также нужно гнать.

Вообще,максимальная информативность,когда гоним половину,то есть Н/2,всего исходов Н факториал.
то есть грубая оценка ((Н/2)+1)^Х=Н!
наш х число прогонов.
только получается целая часть от Н/2.
когда 3,то 2^Х>=6, то есть х=3
когда 4,то 3^Х>=24,то получается 3, значит,нужно искать способ найти за 3 шага.

Для 5 получается 5 вариантов,нужно смотреть.

(66) Прочитай (60) и (63)
Исходы проверок сильно неравномерно распределены. Для проверки двух пар при N=4 в
четырех случаях вернется "0"
четырех - "2"
шестнадцати(!) - "1".
Твои рассуждения (и оценка) были бы верны, если после каждой проверки число вариантов сокращалось бы втрое.