环形逻辑

k元真值表是从k位二进制数到到1位二进制数的映射（分别以k个二进制位为变量的k元函数）。 例如，逻辑运算符AND（与）和XOR（异或）的二元真值表如下所示： $$\begin{matrix} \mathrm{AND} & \quad & \mathrm{XOR} \\ 00\mapsto 0 & \quad & 00\mapsto 0\\ 01\mapsto 0 & \quad & 01\mapsto 1\\ 10\mapsto 0 & \quad & 10\mapsto 1 \\ 11\mapsto 1 & \quad & 11\mapsto 0 \end{matrix}$$ 对于任意六位二进制数abcdef始终满足下述等式六元真值表$\tau$共有几个？ $$\tau(a,b,c,d,e,f) \;\mathrm{AND}\; \tau(b, c, d, e, f, a \;\mathrm{XOR }\; (b\;\mathrm{AND}\;c))=0.$$

本题难度:

解答

记 $$g: (a,b,c,d,e,f)\mapsto (b, c, d, e, f, a \;\mathrm{XOR }\; (b\;\mathrm{AND}\;c)),$$ 则g是单射。 这是因为两个六位二进制数x,x'的后五位中只要有一位不同，则显然$g(x)\neq g(x')$。 否则若$x=(a,b,c,d,e,f)$，$x'=(a',b,c,d,e,f)$，则$g(x)$和$g(x')$的前五位都相同，只要$a\neq a'$，则无论$(b\;\mathrm{AND}\;c)$取何值，它与a和a'的异或都必然分别是0和1，从而不同。 六位二进制数共有$64$个，容易计算出它们在g下共有六个轨道: \begin{align*} \begin{aligned} & 0\mapsto0\\ &1\mapsto32\mapsto16\mapsto8\mapsto4\mapsto2\mapsto1\\ &3\mapsto33\mapsto48\mapsto24\mapsto12\mapsto6\mapsto35\mapsto49\mapsto56\mapsto28\mapsto14\mapsto39\mapsto19\mapsto41\mapsto52\mapsto26\\ &\mapsto13\mapsto38\mapsto51\mapsto57\mapsto60\mapsto30\mapsto47\mapsto23\mapsto11\mapsto37\mapsto50\mapsto25\mapsto44\mapsto22\mapsto43\\ &\mapsto53\mapsto58\mapsto29\mapsto46\mapsto55\mapsto27\mapsto45\mapsto54\mapsto59\mapsto61\mapsto62\mapsto63\mapsto31\mapsto15\mapsto7\mapsto3\\ &5\mapsto34\mapsto17\mapsto40\mapsto20\mapsto10\mapsto5\\ & 9\mapsto36\mapsto18\mapsto9\\ &21\mapsto42\mapsto21 \end{aligned} \end{align*} 要使题中等式始终成立，对任意六位二进制数x而言，$\tau(x)$和$\tau(g(x))$中都必须至少有一个是0。 因此可以把上述每一条轨道都视作是一个由n个节点（n是轨道中互异的数的数量）组成的环路，给每个节点染成黑色或白色（赋值0或1），要求任意两个相邻的节点不能都是白色，求总的染色方案数$f(n)$。 这就得到一个经典的组合问题，$f(n)$的值称为Lucas数，满足 $$f(n)=f(n-1)+f(n-2), \quad f(1)=1, f(2)=3.$$ 以上六个轨道中的节点数依次是$1,6,46,6,3,2$，查OEIS A000204可得结果是 $$f(1)\cdot f(6)\cdot f(46)\cdot f(6) \cdot f(3)\cdot f(2)=1\cdot 18\cdot 4106118243 \cdot 18 \cdot 4 \cdot 3=15964587728784.$$ 本题无需编程。