0209 环形逻辑
* * * *
拉格朗日计划
* * * *
环形逻辑

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.$$ 本题无需编程。