Combinatorics (Fall 2010)/Problem set 6

From TCS Wiki
Revision as of 09:09, 12 January 2011 by imported>WikiSysop (Protected "Combinatorics (Fall 2010)/Problem set 6" ([edit=sysop] (indefinite) [move=sysop] (indefinite)))
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search

Problem 1

[math]\displaystyle{ 2m }[/math] 个小球,共m种颜色,每种颜色两个球,相同颜色的球不可区分。

取k个球,有多少种取法。

Problem 2

共有 [math]\displaystyle{ r\ge 5 }[/math] 种颜色。对于如下的图,有多少个对顶点的着色,使得任意相邻两点不共色。

File:Color graph.png

Problem 3

[math]\displaystyle{ \phi(x_1,x_2,\ldots,x_n) }[/math][math]\displaystyle{ n }[/math]个变量的[math]\displaystyle{ m }[/math]个子句 (clause) 的 conjunctive normal form (CNF) 逻辑表达式。

证明:对于任何如上的[math]\displaystyle{ \phi }[/math],总存在一个[math]\displaystyle{ (x_1,x_2,\ldots,x_n)\in\{\text{true},\text{false}\}^n }[/math]的赋值,满足至少[math]\displaystyle{ \frac{m}{2} }[/math]个子句。

Problem 4

[math]\displaystyle{ S_1,\ldots,S_m }[/math]一系列集合,满足

  • 任何 [math]\displaystyle{ S_i }[/math] 有至少 [math]\displaystyle{ k }[/math] 个元素;
  • 任何元素至多属于 [math]\displaystyle{ k }[/math] 个集合

证明:[math]\displaystyle{ S_1,\ldots,S_m }[/math] 有 system of distinct representatives (SDR)。

Problem 5

[math]\displaystyle{ \mathcal{F}\subseteq 2^{[n]} }[/math] 为一个antichain,即 [math]\displaystyle{ \forall S,T\in\mathcal{F}, S\not\subset T }[/math]。此外,[math]\displaystyle{ \forall S\in\mathcal{F}, |S|\le k }[/math]

证明:[math]\displaystyle{ |\mathcal{F}|\le{n\choose k} }[/math]

(使用课上教的某定理)