保險箱密碼解鎖次數

解决问题

妈妈打算找出保险箱的密码序列，不按顺执行密码，但能测出最少按的次数。

妈妈们正在解决一个有趣的问题: 如何确保安全门开启。安全门将在发生特定三位数连续输入时打开。问题是：至少需要多少次输入才能确保出现所有可能的三位数组合呢？这让我想到，使用组合数学的方法来构建一个 de Bruijn 序列是个好主意。

寻找序列最短长度

我在寻找一个长度最短的序列，其中所有可能的3位数字组合都作为其子序列出现。通过分析3^3=27种可能的3位数字组合，确定了一个长度为27的序列。

寻找最小序列

我正在寻找满足条件的最短序列，考虑到了循环序列和非循环序列的情况，最终得出非循环序列的最小长度为 n^k + k - 1。

要确保输入了所有可能的三位密码组合，并使每个组合连续出现，最短的按键序列长度是：

• 总可能的密码组合数：对于数字1、2、3，每个位置有3种选择，所以共有 $3^3 = 27$ 种不同的三位密码组合。
• 最短按键序列长度：为了包含所有这些组合，并使每个组合都作为连续的子序列出现，需要构建一个De Bruijn序列，其最短长度为 $n^k + k - 1$，其中 $n$ 是数字的种类数，$k$ 是密码的长度。在本题中，$n = 3$，$k = 3$，因此最短长度为 $3^3 + 3 - 1 = 29$。

因此，我妈妈至少需要按 29 次按键才能保证打开保险箱。

答案：29