Combinatorics (Fall 2010)/Problem set 2
Problem 1
8种颜色的小球,每种20只,放到6个盒子里。证明无论怎么放,一定有一个盒子包含两对不同颜色的球。
尝试推广到一般情况(自己设计如何推广)。
提示:用鸽笼原理。
Problem 2
一个图[math]\displaystyle{ G }[/math] 的 independence number [math]\displaystyle{ \alpha(G) }[/math] 为 [math]\displaystyle{ G }[/math] 中最大的独立集 (independent set) 的大小。证明Turán定理的对偶(dual)版本:
定理 - 如果图 [math]\displaystyle{ G }[/math] 有 [math]\displaystyle{ n }[/math] 个结点,[math]\displaystyle{ \frac{nk}{2} }[/math] 条边,[math]\displaystyle{ k\ge 1 }[/math],则 [math]\displaystyle{ \alpha(G)\ge\frac{n}{k+1} }[/math]。