开锁问题 --- 魔方最少覆盖问题

ggglgq

好象可以这样想：

只考虑两位，设每个转盘有 N 个数字，共有 N*N 种打开方法。 因此，最多试 N*N - 1 次（最后那一次，不试也知道）。

ggglgq

看样子是不太容易呀！ 初步结论：最小值下界大于 N*N/3 。 我暂时找到最小值为 N*N-N 的方案！

ggglgq

比如：

001 110 002 220 ... ... 00N NN0

112 221 113 331 ... ... 11N NN1

... ... ... ...

(N-1)(N-1)N NN(N-1)

不知你现在能给出最优解吗？具体到某一个 N ，应该可以找出更优的解吧！

ggglgq

好主题，固顶。原来“开锁问题”就是“魔方最少覆盖问题”呀，楼主厉害！[em17] 建议大家再进一步研究一下以下两个问题：

一把密码锁，有n位数字（ 0 - 9 ），现已损坏，只要k位数字对，就能打开。 现在，密码忘记了，问：最少试多少次，就肯定能打开锁？（ k < n ）

一把密码锁，有n位数字（ 0 - P ），现已损坏，只要k位数字对，就能打开。 现在，密码忘记了，问：最少试多少次，就肯定能打开锁？（ P > 0， k < n ）