老师上课留的作业

还蛮简单的(


X3C-1问题

首先你需要知道什么是X3C问题(假装你知道了,其实是我懒得写了

X3C-1问题是任意两个元素的交的大小小于等于1

证明

我们尝试用X3C来归约到X3C-1来证明这件事情。

其实蛮简单的,假设\((a,b,c)\)是X3C集合的一个元素。

我们把它拆成以下5个元素

\[(a, e1, e2) \\ (b, e3, e4) \\ (c, e5, e6) \\ (e1, e3, e5) \\ (e2, e4, e6)\]

正确性显然(

广义划分问题

狭义的划分问题是将集合里的元素划分成两个部分,每个部分的和相等

而广义划分问题便是使得两个部分保持1:2的关系

证明

尝试从划分问题归约到这个问题。

假设原集合为S

加入\(\frac{3}{2}S\)\(\frac{7}{2}S\)两个元素,正确性显然(