旺达先生经常忘记该记住的数字，如朋友的手机号，保险柜的密码等等，为此厂家专门为他设计了办公室保险柜的密码锁．此密码锁的密码是三位数，但只要输入的三位数中有两个数位上的数字正确，保险柜的锁就会打开．旺达先生又忘记他设置的密码了．他至少要尝试多少次才能保证保险柜一定能打开？
【难度】
【出处】
2018年全国高中数学联赛江苏省预赛（复赛加试）
【标注】
【答案】
$50$ 次
【解析】
首先引入几个记号，设：
$E=\{1,3,5,7,9\},F=\{0,2,4,6,8\}$
$\Phi=E\bigcup F=\{0,1,2,3,4,5,6,7,8,9\}$
$\Omega=\{xyz|x,y,z\in\Phi\}$（所有三位码的集合）
$\Omega_{11}=\{xab\in\Omega|x\in\Phi,a,b\in E\}$
$\Omega_{12}=\{ayb\in\Omega|y\in\Phi,a,b\in E\}$
$\Omega_{13}=\{abz\in\Omega|z\in\Phi,a,b\in E\}$
$\Omega_1=X_{11}\bigcup X_{12}\bigcup X_{13}$（所有至少具有两个奇数的三位码集合）
$\Omega_2=\{cdw,cwd,wcd\in\Omega|w\in\Phi,c,d\in F\}$（所有至少具有两个偶数的三位码集合），则 $\Omega=\Omega_1\bigcup \Omega_2$．
（1）存在性，即我们构造 $\Omega$ 的一个具有 $50$ 个元素的子集 $X$ 满足：对 $\Omega$ 中的任一三位码都可用 $X$ 中的一个三位码打开．
分别任取 $25$ 个数 $x_{ab},y_{ab},z_{ab}\in\Omega,a,b\in E$，构造 $\Omega$ 的三个分别具有 $25$ 个元素的子集
$X_{11}=\{x_{ab}ab\in\Omega|a,b\in E\}$
$X_{12}=\{ay_{ab}b\in\Omega|a,b\in E\}$
$X_{13}=\{abz_{ab}\in\Omega|a,b\in E\}$
则对 $i=1,2,3$，显然集合 $\Omega_{1i}$ 中任一三位码都可用集合 $X_1i$ 中的一个三位码打开．
现在我们取特殊的 $X_{11},X_{12},X_{13}$，使得 $X_{11}=X_{12}=X_{13}$，从而 $X_1=X_{11}=X_{12}=X_{13}$ 是含有 $25$ 个元素的集合，例如：
$X_1=X_{11}=X_{12}=X_{13}=\begin{Bmatrix}
111 & 133 & 155 & 177 & 199\\
319 & 331 & 353 & 375 & 397\\
517 & 539 & 551 & 573 & 595\\
715 & 737 & 759 & 771 & 793\\
913 & 935 & 957 & 979 & 991\\
\end{Bmatrix}$
而且 $\Omega_1$ 中任一三位码都由 $X_1$ 中这 $25$ 个三位码中的一个打开．
同理可构造全部由偶数组成的 $25$ 个三位码的集合 $X_2$ 使得 $\Omega_2$ 中任一三位码都可由 $X_2$ 中一个三位码打开．令 $X=X_1\bigcup X_2$，由 $X_1,X_2$ 的构造知 $|X|=50$，且 $\Omega=\Omega_1\bigcup \Omega_2$ 中任一三位码都可由 $X$ 中一个三位码打开．
（2）$50$ 是最小的，即如果 $\Omega$ 的子集 $X$ 满足：$\Omega$ 中任一三位码都可由 $X$ 中一个三位码打开，则 $|X|\geqslant 50$．
反证法：假如 $w=|X|\leqslant 49$ 并设 $X=\{(a_1b_1c_1),(a_2b_2c_2),\cdots,(a_wb_wc_w)\}$．
考虑三个数列 $a_1,a_2,\cdots,a_w;b_1,b_2,\cdots,b_w;c_1,c_2,\cdots,c_w$，则这三个数列中，至少有两个数列，使得 $0,1,\cdots,9$ 这 $9$ 个数字均出现．否则，不妨设数字 $a\in\Phi$ 不在 $a_1,a_2,\cdots,a_w$ 中出现，数字 $b\in\Phi$ 不在 $b_1,b_2,\cdots,b_w$ 中出现，那么三位码 $ab0\in\Omega$ 就不能用 $X$ 中任一三位码打开，矛盾．
不妨设 $a_1,a_2,\cdots,a_w$ 中出现的不同数字构成的集合为 $A$，并且设 $x\in A$ 在 $a_1,a_2,\cdots,a_w$ 中出现的次数最少，为 $m_1$ 次．同理，在 $b_1,b_2,\cdots,b_w$ 中出现的不同数字构成的集合为 $B$，并且设 $y\in B$ 在 $b_1,b_2,\cdots,b_w$ 中出现的次数最少，为 $m_2$ 次．在 $c_1,c_2,\cdots,c_w$ 中出现的不同数字构成的集合为 $C$，并且 $z\in C$ 在 $c_1,c_2,\cdots,c_w$ 中出现的次数最少，为 $m_3$ 次．
令 $m=\min \{m_1,m_2,m_3\}$．不妨设 $m=m_3$，由于至少有两个数列 $0,11\cdots,9$ 均出现，从而 $m\leqslant [49/10]=4$．考虑 $X$ 中个位为 $z$ 的元素构成的子集 $Y$，不妨设为 $Y=\{(a_1b_1z),(a_2b_2z),\cdots,(a_mb_mz)\}$．令 $U=\{a_1,a_2,\cdots,a_m\},V=\{b_1,b_2,\cdots,b_m\}$，并且 $U$ 中不同的数字有 $s$ 个，$V$ 中不同的数字有 $t$ 个，则 $1\leqslant s\leqslant m,q\leqslant t\leqslant m$．注意：$0,1,\cdots,9$ 在 $U$ 中不出现的数字有 $10-s$ 个，在 $V$ 中不出现的数字有 $10-t$ 个．
构造集合 $Z=\{abz\in\Omega|a\not\in U且b\not\in V\}$．因此，$|Z|=(10-s)(10-t)$．对每个 $abz\in\mathbf Z$，则至少存在一个三位码 $\alpha\beta\gamma\in X$ 能打开 $abz$，由 $Z$ 的构造知 $\alpha=a,\beta=b,\gamma\ne z$．记 $Z^\prime=\{abin X|a\not\in U,b\not\in V,c\ne z\}$．那么 $|Z^\prime|\geqslant (10-s)(10-t)$．
再构造 $X$ 的子集 $W=\{(abc)|(abc)\in X其中a\in U\}$．
由于 $U$ 中共有 $s$ 个不同的数字，每个数字在 $X$ 中至少出现 $m$ 次，从而 $|W|\geqslant ms$．由集合 $Z^\prime ,W$ 的构造显然有 $W\bigcap Z^\prime=\varnothing$．因此，$49\geqslant w=|X|\geqslant ms+(10-s)(10-t)$．因此，$49\geqslant 100-10(s+t)+st+ms=2(5-s)(5-t)+50+s(m-t)\geqslant 50$，矛盾．
$E=\{1,3,5,7,9\},F=\{0,2,4,6,8\}$
$\Phi=E\bigcup F=\{0,1,2,3,4,5,6,7,8,9\}$
$\Omega=\{xyz|x,y,z\in\Phi\}$（所有三位码的集合）
$\Omega_{11}=\{xab\in\Omega|x\in\Phi,a,b\in E\}$
$\Omega_{12}=\{ayb\in\Omega|y\in\Phi,a,b\in E\}$
$\Omega_{13}=\{abz\in\Omega|z\in\Phi,a,b\in E\}$
$\Omega_1=X_{11}\bigcup X_{12}\bigcup X_{13}$（所有至少具有两个奇数的三位码集合）
$\Omega_2=\{cdw,cwd,wcd\in\Omega|w\in\Phi,c,d\in F\}$（所有至少具有两个偶数的三位码集合），则 $\Omega=\Omega_1\bigcup \Omega_2$．
（1）存在性，即我们构造 $\Omega$ 的一个具有 $50$ 个元素的子集 $X$ 满足：对 $\Omega$ 中的任一三位码都可用 $X$ 中的一个三位码打开．
分别任取 $25$ 个数 $x_{ab},y_{ab},z_{ab}\in\Omega,a,b\in E$，构造 $\Omega$ 的三个分别具有 $25$ 个元素的子集
$X_{11}=\{x_{ab}ab\in\Omega|a,b\in E\}$
$X_{12}=\{ay_{ab}b\in\Omega|a,b\in E\}$
$X_{13}=\{abz_{ab}\in\Omega|a,b\in E\}$
则对 $i=1,2,3$，显然集合 $\Omega_{1i}$ 中任一三位码都可用集合 $X_1i$ 中的一个三位码打开．
现在我们取特殊的 $X_{11},X_{12},X_{13}$，使得 $X_{11}=X_{12}=X_{13}$，从而 $X_1=X_{11}=X_{12}=X_{13}$ 是含有 $25$ 个元素的集合，例如：
$X_1=X_{11}=X_{12}=X_{13}=\begin{Bmatrix}
111 & 133 & 155 & 177 & 199\\
319 & 331 & 353 & 375 & 397\\
517 & 539 & 551 & 573 & 595\\
715 & 737 & 759 & 771 & 793\\
913 & 935 & 957 & 979 & 991\\
\end{Bmatrix}$
而且 $\Omega_1$ 中任一三位码都由 $X_1$ 中这 $25$ 个三位码中的一个打开．
同理可构造全部由偶数组成的 $25$ 个三位码的集合 $X_2$ 使得 $\Omega_2$ 中任一三位码都可由 $X_2$ 中一个三位码打开．令 $X=X_1\bigcup X_2$，由 $X_1,X_2$ 的构造知 $|X|=50$，且 $\Omega=\Omega_1\bigcup \Omega_2$ 中任一三位码都可由 $X$ 中一个三位码打开．
（2）$50$ 是最小的，即如果 $\Omega$ 的子集 $X$ 满足：$\Omega$ 中任一三位码都可由 $X$ 中一个三位码打开，则 $|X|\geqslant 50$．
反证法：假如 $w=|X|\leqslant 49$ 并设 $X=\{(a_1b_1c_1),(a_2b_2c_2),\cdots,(a_wb_wc_w)\}$．
考虑三个数列 $a_1,a_2,\cdots,a_w;b_1,b_2,\cdots,b_w;c_1,c_2,\cdots,c_w$，则这三个数列中，至少有两个数列，使得 $0,1,\cdots,9$ 这 $9$ 个数字均出现．否则，不妨设数字 $a\in\Phi$ 不在 $a_1,a_2,\cdots,a_w$ 中出现，数字 $b\in\Phi$ 不在 $b_1,b_2,\cdots,b_w$ 中出现，那么三位码 $ab0\in\Omega$ 就不能用 $X$ 中任一三位码打开，矛盾．
不妨设 $a_1,a_2,\cdots,a_w$ 中出现的不同数字构成的集合为 $A$，并且设 $x\in A$ 在 $a_1,a_2,\cdots,a_w$ 中出现的次数最少，为 $m_1$ 次．同理，在 $b_1,b_2,\cdots,b_w$ 中出现的不同数字构成的集合为 $B$，并且设 $y\in B$ 在 $b_1,b_2,\cdots,b_w$ 中出现的次数最少，为 $m_2$ 次．在 $c_1,c_2,\cdots,c_w$ 中出现的不同数字构成的集合为 $C$，并且 $z\in C$ 在 $c_1,c_2,\cdots,c_w$ 中出现的次数最少，为 $m_3$ 次．
令 $m=\min \{m_1,m_2,m_3\}$．不妨设 $m=m_3$，由于至少有两个数列 $0,11\cdots,9$ 均出现，从而 $m\leqslant [49/10]=4$．考虑 $X$ 中个位为 $z$ 的元素构成的子集 $Y$，不妨设为 $Y=\{(a_1b_1z),(a_2b_2z),\cdots,(a_mb_mz)\}$．令 $U=\{a_1,a_2,\cdots,a_m\},V=\{b_1,b_2,\cdots,b_m\}$，并且 $U$ 中不同的数字有 $s$ 个，$V$ 中不同的数字有 $t$ 个，则 $1\leqslant s\leqslant m,q\leqslant t\leqslant m$．注意：$0,1,\cdots,9$ 在 $U$ 中不出现的数字有 $10-s$ 个，在 $V$ 中不出现的数字有 $10-t$ 个．
构造集合 $Z=\{abz\in\Omega|a\not\in U且b\not\in V\}$．因此，$|Z|=(10-s)(10-t)$．对每个 $abz\in\mathbf Z$，则至少存在一个三位码 $\alpha\beta\gamma\in X$ 能打开 $abz$，由 $Z$ 的构造知 $\alpha=a,\beta=b,\gamma\ne z$．记 $Z^\prime=\{abin X|a\not\in U,b\not\in V,c\ne z\}$．那么 $|Z^\prime|\geqslant (10-s)(10-t)$．
再构造 $X$ 的子集 $W=\{(abc)|(abc)\in X其中a\in U\}$．
由于 $U$ 中共有 $s$ 个不同的数字，每个数字在 $X$ 中至少出现 $m$ 次，从而 $|W|\geqslant ms$．由集合 $Z^\prime ,W$ 的构造显然有 $W\bigcap Z^\prime=\varnothing$．因此，$49\geqslant w=|X|\geqslant ms+(10-s)(10-t)$．因此，$49\geqslant 100-10(s+t)+st+ms=2(5-s)(5-t)+50+s(m-t)\geqslant 50$，矛盾．
答案
解析
备注
