imported>Etone |
imported>Addbot |
Line 1: |
Line 1: |
| == Problem 1==
| | In [[number theory]] a '''Carmichael number''' is a [[composite number|composite]] positive [[integer]] <math>n</math>, which satisfies the [[congruence]] <math>b^{n-1}\equiv 1\pmod{n}</math> for all integers <math>b</math> which are [[coprime|relatively prime]] to <math>n</math>. Being relatively prime means that they do not have common divisors, other than 1. Such numbers are named after [[Robert Daniel Carmichael|Robert Carmichael]]. |
| 一个<math>k</math>-超图 (<math>k</math>-uniform hypergraph) <math>\mathcal{H}\subset{[n]\choose k}</math> 的 '''blocking set''' 是这样一个集合 <math>T\subseteq[n]</math>,使每一个超边 (hyper-edge) <math>S\in\mathcal{H}</math> 都有 <math>T\cap S\neq\emptyset</math>。
| |
|
| |
|
| 注:当 <math>k=2</math> 的时候,<math>\mathcal{H}</math> 就是一个图,而 blocking set <math>T</math> 就是这个图的顶点覆盖(vertex cover)。因此,blocking set 就是顶点覆盖在超图(hypergraph)上的推广。我们知道最小定点覆盖(minimum vertex cover)问题是 NP-hard 问题,因此求最小 blocking set 也是难的。
| | All [[prime number]]s <math>p</math> satisfy <math>b^{p-1}\equiv 1\pmod{p}</math> for all integers <math>b</math> which are relatively prime to <math>p</math>. This has been proven by the famous mathematician [[Pierre de Fermat]]. In most cases if a number <math>n</math> is composite, it does '''not''' satisfy this congruence equation. So, there exist not so many Carmichael numbers. We can say that Carmichael numbers are composite numbers that behave a little bit like they would be a prime number. |
| | | {{Math-stub}} |
| 证明:任何 <math>\mathcal{H}\subset{[n]\choose k}</math>, <math>|\mathcal{H}|=m</math>,都存在一个不大于 <math>\left\lceil\frac{n\ln m}{k}\right\rceil</math> 的 blocking set。
| | [[Category:Number theory]] |
| | |
| == Problem 2==
| |
| 一个图 <math>G(V,E)</math> 的'''支配集''' (dominating set) 是一个顶点集合 <math>D\subseteq V</math>,使得每个顶点 <math>v\in V</math> 要么属于 <math>D</math> 要么有邻居属于 <math>D</math>。最小支配集 (minimum dominating set) 是 NP-hard问题。
| |
| | |
| 证明:任何一个 <math>n</math> 个顶点的 <math>d</math>-regular 图(每个顶点恰好有 <math>d</math> 个邻居),必然存在一个不大于 <math>\frac{n(1+\ln(d+1))}{d+1}</math> 的支配集。
| |
| | |
| == Problem 3 ==
| |
| <math>H(W,F)\,</math> 为一个图,<math>n>|W|\,</math> 为一个整数。已知存在一个图 <math>G(V,E)\,</math> 有 <math>|V|=n, |E|=m\,</math> 且<font color=red>不包含</font> <math>H\,</math> 子图。
| |
| | |
| 证明:对于 <math>k>\frac{n^2\ln n}{m}</math>,存在一个对 <math>K_n\,</math>(<math>n</math>结点完全图)的<font color=red>边</font>的 <math>k</math> 着色,没有单色(monocharomatic)的<math>H\,</math>。
| |
| | |
| 注:令 <math>K_n</math> 的边集为 <math>E={V\choose 2}</math>,“对 <math>K_n</math> 的边的 <math>k</math> 着色",就是一个映射 <math>f: E\rightarrow [k]</math>。
| |
| 即,每个边选择 <math>k</math> 种颜色之一进行着色,可以任意着色,无需考虑相邻的边是否同色。
| |
| | |
| == Problem 4 ==
| |
| 令 <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{H}</math> 中不存在单色的集合 <math>S\in\mathcal{H}</math>。
| |
| | |
| ==Problem 5 ==
| |
| 我们称一个[http://en.wikipedia.org/wiki/Tournament_(graph_theory) '''竞赛图'''] <math>T([n],E)</math> 是[http://en.wikipedia.org/wiki/Tournament_(graph_theory)#Transitivity 传递(transitive)]的,如果存在一个 <math>[n]</math> 的全排列 <math>\pi</math> 使得 <math>(i,j)\in E</math> 当且仅当 <math>\pi_i<\pi_j</math>,即该竞赛图 <math>T([n],E)</math> 的边的方向符合传递性。
| |
| | |
| 证明:对任何 <math>k\ge 3</math>,存在 <math>N(k)</math>,对任何的 <math>n\ge N(k)</math> 个点的竞赛图,都存在一个 <math>k</math> 个点的子竞赛图满足传递性。
| |
In number theory a Carmichael number is a composite positive integer [math]\displaystyle{ n }[/math], which satisfies the congruence [math]\displaystyle{ b^{n-1}\equiv 1\pmod{n} }[/math] for all integers [math]\displaystyle{ b }[/math] which are relatively prime to [math]\displaystyle{ n }[/math]. Being relatively prime means that they do not have common divisors, other than 1. Such numbers are named after Robert Carmichael.
All prime numbers [math]\displaystyle{ p }[/math] satisfy [math]\displaystyle{ b^{p-1}\equiv 1\pmod{p} }[/math] for all integers [math]\displaystyle{ b }[/math] which are relatively prime to [math]\displaystyle{ p }[/math]. This has been proven by the famous mathematician Pierre de Fermat. In most cases if a number [math]\displaystyle{ n }[/math] is composite, it does not satisfy this congruence equation. So, there exist not so many Carmichael numbers. We can say that Carmichael numbers are composite numbers that behave a little bit like they would be a prime number.
Template:Math-stub