组合数学 (Fall 2011)/Problem set 3: Difference between revisions
imported>Etone |
imported>Etone |
||
| (15 intermediate revisions by the same user not shown) | |||
| Line 1: | Line 1: | ||
== Problem 1== | == Problem 1== | ||
令 <math>a_1,a_2,\ldots,a_n</math> 为任意长为 <math>n</math> 的整数序列。 | |||
证明：存在 <math>j,k</math> 满足 <math>1\le j\le k\le n</math> 使得 <math>\sum_{i=j}^ka_i</math> 可被 <math>n</math> 整除。 | |||
==Problem 2== | ==Problem 2== | ||
<font color=red size=3> Attention：这道题目我上课之前临时改了一下，现在发现改错了，于是又改回去了。请同学们相互转告。</font> | |||
一个无向图 <math>G(V,E)</math> 的切 (cut) 被某个点集 <math>S</math>定义，为 <math>C(S,\bar{S})=\{uv\in E\mid u\in S, v\not\in S\}</math>，即那些一头在 <math>S</math> 中另一头在 <math>S</math> 的补中的边。求一个图的最大切 ([http://en.wikipedia.org/wiki/Maximum_cut maximum cut]) 是 [http://en.wikipedia.org/wiki/Karp%27s_21_NP-complete_problems Karp 的21个NP完全问题之一]。 | |||
证明：任意一个有 <math>m</math> | 证明：任意一个有 <math>m</math> 条边的无向图都存在一个不<font color=red>小</font>于 <math>\frac{m}{2}</math> 的切。 | ||
==Problem 3 == | ==Problem 3 == | ||
令 <math>\mathcal{ | 令 <math>\mathcal{H}\subseteq{[n]\choose k}</math> 为一个 <math>k</math>-uniform <math>k</math>-regular hypergraph，即 <math>\forall i\in[n]</math>，刚好有 <math>k</math> 个不同的 <math>S\in\mathcal{H}</math> 满足 <math>i\in S</math>。 | ||
假设 <math>k\ge 10</math>。证明：存在一个对 <math>[n]</math> 的 2着色 <math>f:[n]\rightarrow\{0,1\}</math> 使得 <math>\mathcal{ | 假设 <math>k\ge 10</math>。证明：存在一个对 <math>[n]</math> 的 2着色 <math>f:[n]\rightarrow\{0,1\}</math> 使得 <math>\mathcal{H}</math> 中不存在单色的集合 <math>S\in\mathcal{H}</math>。 | ||
Latest revision as of 04:24, 29 October 2011
Problem 1
令 [math]\displaystyle{ a_1,a_2,\ldots,a_n }[/math] 为任意长为 [math]\displaystyle{ n }[/math] 的整数序列。
证明：存在 [math]\displaystyle{ j,k }[/math] 满足 [math]\displaystyle{ 1\le j\le k\le n }[/math] 使得 [math]\displaystyle{ \sum_{i=j}^ka_i }[/math] 可被 [math]\displaystyle{ n }[/math] 整除。
Problem 2
Attention：这道题目我上课之前临时改了一下，现在发现改错了，于是又改回去了。请同学们相互转告。
一个无向图 [math]\displaystyle{ G(V,E) }[/math] 的切 (cut) 被某个点集 [math]\displaystyle{ S }[/math]定义，为 [math]\displaystyle{ C(S,\bar{S})=\{uv\in E\mid u\in S, v\not\in S\} }[/math]，即那些一头在 [math]\displaystyle{ S }[/math] 中另一头在 [math]\displaystyle{ S }[/math] 的补中的边。求一个图的最大切 (maximum cut) 是 Karp 的21个NP完全问题之一。
证明：任意一个有 [math]\displaystyle{ m }[/math] 条边的无向图都存在一个不小于 [math]\displaystyle{ \frac{m}{2} }[/math] 的切。
Problem 3
令 [math]\displaystyle{ \mathcal{H}\subseteq{[n]\choose k} }[/math] 为一个 [math]\displaystyle{ k }[/math]-uniform [math]\displaystyle{ k }[/math]-regular hypergraph，即 [math]\displaystyle{ \forall i\in[n] }[/math]，刚好有 [math]\displaystyle{ k }[/math] 个不同的 [math]\displaystyle{ S\in\mathcal{H} }[/math] 满足 [math]\displaystyle{ i\in S }[/math]。
假设 [math]\displaystyle{ k\ge 10 }[/math]。证明：存在一个对 [math]\displaystyle{ [n] }[/math] 的 2着色 [math]\displaystyle{ f:[n]\rightarrow\{0,1\} }[/math] 使得 [math]\displaystyle{ \mathcal{H} }[/math] 中不存在单色的集合 [math]\displaystyle{ S\in\mathcal{H} }[/math]。