задача дня-17

[falcao]

Не так давно встретилась задача -- скорее всего, она известная. Слишком уж естественная у неё формулировка. В таких случаях кому-то может быть известно "авторское" решение, которое мне было бы интересно узнать

Comments

[kaktus77]

Можно рассуждать с конца.
Осталось два замка и два ключа это однозначно 1 проверка.
Нна предыдущем шаге - 3 замка и 3 ключа. Чтобы найти одну пару ключ-замок нужно 2 попытки. Это тоже однозначно. Меньше быть не может.
Таким образом получаем индукцию - каждый предыдущий шаг дает к+1 попыток.

И получаем по индукции, что это минимальное количество попыток (n(n-1)/2)

[mathreader]

Не обязательно определять сначала точно для какого замка подходит ключ номер 1. Можно сделать некоторое количество тестов (потыкав разные ключи в разные замки), и из этой информации попробовать вычислить соответствие. Поэтому индуктивный переход не работает.

[kaktus77]

Почему же, вполне работает

[mathreader]

"Так или иначе переход от n ключей к n-1 происходит через подбор одной пары."

Здесь вы используете допущение, что нам надо переходить от n ключей к n-1. Нам, вообще говоря, не надо. Надо восстановить всё соответствие, и не обязательно один ключ за одним.

[kaktus77]

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

[kaktus77]

Впрочем, есть один (и только один) способ подобрать 2 пары за один ход.
То есть перейти от n сразу к n - 2.
Но он требует n-1 + n-2 проб. То есть заведомо. не уменьшает кол-во проб

[falcao]

Рассуждение этого типа, наверное, возможно, но его не так легко изложить, обходя все возможные при этом "подводные камни". Если мы рассуждаем по индукции, то надо точно сформулировать доказываемое утверждение. И если в доказательстве участвуют "шаги", то нужно точно определить, что это означает. Скажем, если говорится, что "на шаге n все равно требуется минимум n-1 проб", то смысл этого утверждения ясен лишь в общих чертах. Нам приходится обращаться к ранее сделанным пробам, относя их к какому-то "шагу". Тогда должна быть задана функция, которая каждой пробе сопоставляет номер условного "шага". И я не думаю, что реализация такого плана является лёгким делом.

[kaktus77]

Конечно, это только план доказательства, и с неточностями:

Там не две стратегии, а три:

1) перебирать замки под ключ,
2) перебирать ключи для замка,
3) комбинация первых двух.

Вторая сводится к первой (симметрия ключей и замков) .

В первой возможен только переход от n к n-1, и для этого требуется минимум n-1 проб в n+ шагах (то есть при n или большем кол-ве свободных ключей). К какому именно шагу эти пробы относятся не имеет никакого значения, важно ведь только их количество (минимальное).

В третьей как раз возможен только переход от n к n-2 (иначе она сводится к первой) минимум за 2 n - 3 шага.

Надо, конечно, все строго и детально сформулировать, но вроде все довольно очевидно.
И проблем здесь возникнуть не должно.

[falcao]

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