老师上课留的作业
还蛮简单的(
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$两个元素,正确性显然(