通过计算概率证明存在性

hbghlyj

PDF
2 Basic Techniques
Proposition 1 (Union Bound). Given events $A_{1}, A_{2}, \ldots, A_{n}$, we have
$$
P\left(A_{1} \cup A_{2} \cup \cdots\cup A_{n}\right) \leq P\left(A_{1}\right)+P\left(A_{2}\right)+\cdots+P\left(A_{n}\right)
$$
From Union Bound, we see that if the sum of the probabilities $P\left(A_{1}\right), \ldots$, $P\left(A_{n}\right)$ is less than 1 , then the probability that none of the events $A_{1}, \ldots, A_{n}$ occur is positive.

Example 3. (Hong Kong) In each cell of a $100 \times 100$ matrix $A=\left\{a_{i j}\right\}$, one of the integers $1,2, \ldots, 5000$ is written. Moreover, each integer appears in the matrix exactly twice. Prove that one can choose 100 cells in the matrix satisfying the three conditions below:
(a) Exactly one cell is chosen in each row.
(b) Exactly one cell is chosen in each column.
(c) The numbers in the cells chosen are pairwise distinct.
Proof. Let $\left\{b_{1}, b_{2}, \ldots, b_{100}\right\}$ be a random permutation of $\{1,2, \ldots, 100\}$. Let's consider the 100 cells
$$
B=\left\{a_{1, b_{1}}, \quad a_{2, b_{2}}, \quad \ldots, \quad a_{100, b_{100}}\right\} .
$$
Clearly $B$ satisfies both (a) and (b). We compute the probability that $B$ does not satisfy (c). Let's consider any $n \in\{1,2, \ldots, 5000\}$. Two of the cells, say $a_{i j}$ and $a_{p q}$, in matrix $A$ have the number $n$ written in. If $i=p$ or $j=q$, then the probability that there exist two cells from $B$ with $n$ written in is 0 because none of the cells in $B$ are from the same row or column. Otherwise, we consider $a_{i, b_{i}}$ and $a_{p, b_{p}}$. The probability that $a_{i, b_{i}}=a_{p, b_{p}}=n$ is $\frac{1}{100} \cdot \frac{1}{99}$.
Since there are 5000 numbers, Union Bound tells us that the probability that any two of the numbers in $B$ are the same is no more than
$$
5000 \cdot \frac{1}{100} \cdot \frac{1}{99}<1 .
$$
Thus, for any random sampling of 100 cells satisfying (a) and (b), the probability that those cells are pairwise distinct is positive. Therefore, there exist 100 cells satisfying the three conditions (a), (b), and (c).$\square$

Proposition 2. If a random variable $X$ has expectation $E(X)=c$, then there must be a realization of $X$ with value at least $c$, and a realization of $X$ with value at most c.

For example, if the scores of a test are integers from 0 to 10 and the class average is $7.3$, then we know for sure that at least one student's score is 8 or higher, and at least one student's score is 7 or below.

Example 4. (Moscow 1993) In a botanical classifier, a plant is identified by 100 features. Each feature can either be present or absent. A classifier is considered to be good if any two plants have less than half of their features in common. Prove that a good classifier cannot describe more than 50 plants.
Proof. Let's pick a pair of plants uniformly at random from $n$ plants. Let $X_{i}=1$ if the two plants in the chosen pair have opposite $i$ th features and $X_{i}=0$ otherwise. Then let $X$ be the total number of features for which the plants differ. So $X=X_{1}+X_{2}+\cdots+X_{100}$. Thus, $E(X)=\sum_{i=1}^{100} E\left(X_{i}\right)=\sum_{i=1}^{100} P$ (the chosen pair has opposite $i$th features).
For $i \in\{1,2, \ldots, 100\}$, let $n_{i}$ be the number of plants with $i$ th feature present. Then the number of pairs of plants that have opposite $i$ th features is $n_{i}(n-$ $\left.n_{i}\right)$. Therefore,
$$
E(X)=\sum_{i=1}^{100} \frac{n_{i}\left(n-n_{i}\right)}{\left(\begin{array}{l}
n \\
2
\end{array}\right)}
$$
By AM-GM, $n_{i}\left(n-n_{i}\right) \leq \frac{n^{2}}{4}$. So
$$
E(X)=\sum_{i=1}^{100} \frac{n_{i}\left(n-n_{i}\right)}{\frac{n(n-1)}{2}} \leq \sum_{i=1}^{100} \frac{n^{2}}{2 n(n-1)}=100 \cdot \frac{n}{2(n-1)}=\frac{50 n}{n-1}
$$
When $n=51$, we get $E(X) \leq 51$. Note that $n_{i}\left(n-n_{i}\right)=\frac{n^{2}}{4}$ if and only if $n_{i}=\frac{n}{2}$. Since $n_{i}$ is an integer, the equality cannot hold when $n=51$. That is, when $n=51, E(X)<51$. Since $X$ is an integer, when there are 51 plants, there must exist a pair of plants such that the number of opposite features this pair has is $\leq 50$. In other words, there exists a pair of plants that have 50 or more common features. Therefore, a good classifier cannot describe 51 plants. Consequently, it cannot describe more than 50 plants.$\square$

hbghlyj

3 Graph Theory
A complete oriented graph is a graph in which every pair of vertices is connected by a single directed edge. We call such an orientation a tournament. A Hamiltonian path in a tournament is a directed path that passes through each vertex exactly once.

Example 5. (Szele) There is a tournament on $n$ vertices that has at least $\frac{n !}{2^{n-1}}$ Hamiltonian paths.

Proof. We construct a random tournament $T$ on $n$ vertices. For each pair of vertices, we flip a fair coin to decide the direction of the edge between them. Let $X$ be the number of Hamiltonian paths in $T$. Note that each Hamiltonian path corresponds to a permutation $\sigma$ of the $n$ vertices. Let's consider the sequence $\{\sigma(1), \sigma(2), \ldots, \sigma(n)\}$. Let $X_{\sigma}=1$ if all the edges $(\sigma(i), \sigma(i+1))$ are in $T$ and $X_{\sigma}=0$ otherwise. We have
$E\left(X_{\sigma}\right)=P((\sigma(i), \sigma(i+1)) \in T$ for all $i \in\{1,2, \ldots, n-1\})=\frac{1}{2^{n-1}} .$
Since $X=\sum_{\sigma} X_{\sigma}$ and there are $n!$ permutations, we have
$$
E(X)=E\left(\sum_{\sigma} X_{\sigma}\right)=\sum_{\sigma} E\left(X_{\sigma}\right)=\frac{n !}{2^{n-1}}
$$
Therefore there is a tournament with at least $\frac{n !}{2^{n-1}}$ Hamiltonian paths.$\square$
Example 6. Show that one can construct a round-robin tournament outcome with more than 1000 people such that for any set of 1000 people, some contestant outside that set beats all of them.

Proof. We flip a fair coin to decide the results of the tournament. Let $A$ be the set of all the people in the tournament with $|A|=n$ and $B$ be any subset of $A$ of unbeaten people with $|B|=1000$. We call a set "unbeaten" if for any contestant outside this set, there is at least one person within the set who beats this contestant. Let $C$ be the set of all the $B$'s. We will calculate the expected value of $|C|$.

Since $B$ is a subset of $A$ of unbeaten people, for any $x \in A \backslash B$, there is a $y \in B$ such that $y$ beats $x$. The probability that someone in $B$ beats $x$ is $1-\left(\frac{1}{2}\right)^{1000}$ and there are $n-1000$ people who are in $A$ but not in $B$. Therefore,
$$
\begin{aligned}
E(|C|) &=\sum_{|B|=1000} P(B \text { is unbeaten })=\sum_{|B|=1000}\left(1-\left(\frac{1}{2}\right)^{1000}\right)^{n-1000} \\
&=\left(\begin{array}{c}
n \\
1000
\end{array}\right) \cdot\left(1-\frac{1}{2^{1000}}\right)^{n-1000} .
\end{aligned}
$$
Since exponential functions grow faster than polynomials, when $n$ is big enough, $E(|C|)$ is less than 1. Since $|C|$ is an integer, there is an $n$ such that $|C|=0$. That is, we can construct a tournament outcome with $n$ people for some sufficiently large $n$, such that for any set of 1000 people, some contestant outside that set beats all of them.$\square$

4 Alteration
So far, all our examples work when we randomly sample objects in a probability space and hope for the best. But this approach does not work all the time. In some cases, we need to modify the objects to make it work.

In graph theory, a set of vertices is called independent if no two of them are connected by an edge.

Example 7. (weak Turán) A graph $G$ has $n$ vertices and average degree $d$. Prove that it is possible to select an independent vertex set of size at least $\frac{n}{2 d}$.

Proof. Without loss of generality, we assume $d>1$. Let's go through a two-step process:

Step 1: Remove each vertex and its associated edges independently with probability $1-\frac{1}{d}$.

Step 2: For each remaining edge, remove it by randomly removing one of its vertices together with its associated edges.

We get an independent vertex set $A$ after those two steps. To find $E(|A|)$, let's define $B$ and $C$ to be the number of remaining vertices and edges after Step 1, respectively. We have $E(B)=n\left(1-\left(1-\frac{1}{d}\right)\right)=\frac{n}{d}$. We start with $\frac{n d}{2}$ edges. Note that every edge is associated with two vertices, and each vertex has probability $\frac{1}{d}$ of surviving Step 1. Thus we have
$$
E(C)=\frac{n d}{2} \cdot \frac{1}{d} \cdot \frac{1}{d}=\frac{n}{2 d}
$$
Note that $|A| \geq B-C$ because each time we remove an edge, we also remove at least one vertex. Thus,
$$
E(|A|) \geq E(B-C)=\frac{n}{d}-\frac{n}{2 d}=\frac{n}{2 d} .
$$
Therefore, it is possible to select an independent vertex set of size at least $\frac{n}{2 d}$.$\square$

hbghlyj

5 Lovász Local Lemma
From Union Bound, we see that if $A_{1}, A_{2}, \ldots, A_{n}$ are "bad" events, and if $\sum_{i=1}^{n} P\left(A_{i}\right)<1$, then there is a positive probability that none of them occur. However, $\sum_{i=1}^{n} P\left(A_{i}\right)$ is not always a good estimate of $P\left(\cup A_{i}\right)$.
Recall that if $A_{1}, A_{2}, \ldots, A_{n}$ are independent events and each occurs with a probability $P\left(A_{i}\right) \leq p<1$, then the probability that none of them occur is
$$
P\left(\bigcap_{i=1}^{n} \bar{A}_{i}\right)=\prod_{i=1}^{n} P\left(\bar{A}_{i}\right) \geq(1-p)^{n}>0
$$
Lovász Local Lemma extends the idea of independency by allowing limited dependencies.

Theorem 2 (Symmetric Lovász Local Lemma). Let $A_{1}, A_{2}, \ldots, A_{n}$ be a set of events with $P\left(A_{i}\right) \leq p$ for all $1 \leq i \leq n$. If each $A_{i}$ is independent of all but at most $d$ of the other $A_{j}$ and
$$
e p(d+1) \leq 1, \quad \text { where } e=2.71818 \ldots
$$
then the probability that none of them occur is positive.
Example 8. Suppose $11n$ points are placed around a circle and colored with $n$ different colors in such a way that each color is applied to exactly 11 points. Prove that in any such coloring, there must be a set of $n$ points each with a different color and no two adjacent.
Proof. Let's label the points around the circle $a_{1}, a_{2}, \ldots, a_{11 n}$, and $a_{0}=a_{11 n}$. Let's pick a point of each color randomly to form a set $B$ of $n$ points. For each $1 \leq i \leq 11 n$, let $X_{i}$ be the event that both $a_{i}$ and $a_{i+1}$ are in $B$. So $X=X_{1} \cup X_{2} \cup \cdots \cup X_{11 n}$ is the union of all the bad events that we would like to avoid. Note that
By Union Bound, $$ P(X) \leq \sum_{i=1}^{11 n} P\left(X_{i}\right)<\frac{11 n}{11^{2}}=\frac{n}{11} . $$
So Union Bond does not give us $P(X)<1$ when $n>11$. However, we see that each $X_{i}$ is independent from $X_{j}$ for all $j$ unless $a_{j}$ or $a_{j+1}$ has the same color as $a_{i}$ or $a_{i+1}$. Note that 10 other points are colored the same color as $a_{i}$, and each point appears in two consecutive pairs of points. So there are at most $2 \cdot 10+1=21$ pairs $\left(a_{j}, a_{j+1}\right)$ other than $\left(a_{i}, a_{i+1}\right)$ sharing a color with $a_{i}$. Similarly, there are at most another 21 pairs sharing a color with $a_{i+1}$. Thus $X_{i}$ and $X_{j}$ are independent for all but at most 42 values of $j$. Now we can apply Lovász Local Lemma with $p=\frac{1}{11^{2}}$ and $d=42$. Since
$$
e p(d+1)=e \cdot \frac{1}{11^{2}} \cdot 43<\frac{28}{10} \cdot \frac{43}{121}<1
$$
Lovász Local Lemma tells us that the probability that none of the bad events occur is positive. Therefore, there must be a set of $n$ points each with a different color and no two adjacent.
6 Exercises
1. (Engel) Let $S$ be a collection of line segments in the unit interval $I=[0,1)$ whose total length is more than $\frac{1}{2}$. Prove that there exist two points in $S$ that are exactly distance $0.1$ apart.
2. (Iran) Prove that in a tournament with 799 teams, there exist 14 teams that can be partitioned into groups in a way that all of the teams in the first group have won all of the teams in the second group.
3. (Russia) In the Duma there are 1600 delegates, who have formed 16000 committees of 80 persons each. Use probabilistic method to prove that one can find two committees having at least four common members.
4. (Turán's Theorem) A graph $G$ has $n$ vertices and average degree $d$. Prove that it is possible to select an independent vertex set of size at least $\frac{n}{d+1}$.
5. Let $n \in \mathbb{N}$ and $m \in \mathbb{N}$ such that $m>0$. Let $A_{1}, A_{2}, \ldots, A_{m}$ be $m$ nonempty subsets of the set $\{1,2, \ldots, n\}$. Prove that there exists a subset $X$ of $\{1,2, \ldots, n\}$ such that $\left|A_{j} \cap X\right|$ is odd for more than $\frac{m}{2}$ different values of $j \in\{1,2, \ldots, m\}$.
6. Prove that a good classifier in Example 4 cannot describe more than 34 plants.

7 References
1. Evan Chen, Expected Uses of Probability
mit.edu/˜evanchen
2. Po-Shen Loh, Probabilistic Methods in Combinatorics,
math.cmu.edu/˜ploh/docs/math/mop2009/prob-comb.pdf
3. Matoušek and Vondrák, The Probabilistic Method,
webbuild.knu.ac.kr/˜trj/Combin/matousek-vondrak-prob-ln.pdf

hbghlyj

尝试做一下习题
1.假设$S$中不存在距离为0.1的两点.设$S$为线段$(a_1,b_1),⋯,(a_n,b_n)$的并集,$0≤a_1<b_1<⋯<a_n<b_n≤1$,则$a_2-b_1<0.1,⋯,a_n-b_{n-1}<0.1$.
$S$中线段的总长满足
$0.5<b_1-a_1+⋯+b_n-a_n<1-0.1(n-1)=1.1-0.1n$
$⇒n<6$
$⇒n≤5$
因为每个线段内部不存在距离为0.1的两点,所以$b_n-a_n≤0.1,⋯,b_1-a_1≤0.1$,相加得$b_1-a_1+⋯+b_n-a_n<0.1n≤0.5$
矛盾.得证.
2.
3.
4.
5.
6.

Czhang271828

更多例子:

________________________

定理 1 $\forall k\in \mathbb Z_{\geq 1}$, $\exists N\in \mathbb Z_{\geq 1}$ 使得一切 $K_{N}$ 的子图 $G$ 满足 $K_k\subset G$ 或 $K_k\subset \overline G$; 换言之, 将 $K_N$ 的边进行任意形式的 $2$ -染色, 总有边染色相同的子图 $K_k$.

根据抽屉原理, $\min N\leq 2^{2k}$ 是显然的, 下将证明 $\min N\geq 2^{k/2}$.

证明 对 $K_N$ 的 $\binom{N}{2}$ 条边独立同分布地进行等概率的红-蓝 $2$ 染色. 对任意取定的 $k$ 个点, 其间连边色均相同的概率为 $2^{1-\binom{k}{2}}$. 若存在某种染色方式使得 $K_N$ 中不含同色的 $K_k$ 子图, 则期望
\[
2^{1-\binom{k}{2}}\cdot\binom{N}{k}<1.
\] 取 $N=2^{k/2}$, 则

\begin{align*}
\binom{N}{k}&\leq \dfrac{N^k}{k!}\\
&\leq 2^{\binom{k}{2}}\cdot \dfrac{(\sqrt 2)^{k}}{k!}\\
&\leq 2^{\binom{k}{2}}\cdot 2^{-1}.
\end{align*}
从而 $2^{1-\binom{k}{2}}\cdot\binom{N}{k}<1$.



$\square$

________________________

定理 2 任意简单图 $G$ 包含一个含有至少 $\left\lceil\dfrac{|E(G)|}{2}\right\rceil$ 条边的二部子图. 其中, 称 $G$ 为二部图若且仅若存在顶点集划分 $V(G)=V_1\dot\cup V_2$ 使得 $V_i$ 中各点两两不连边 ($i=1,2$); 换言之, $\forall e\in E(G)$ 一定是从 $V_1$ 到 $V_2$ 的连边.

证明 记 $\mathcal S$ 为顶底集为 $V(G)$ 的极大二部子图 (即添上任意边后均不为二部图之图) 之集合. 该集合构造如是: 将 $V(G)$ 划分为 $V_1\dot\cup V_2$, 作新图 $G'$ 使得其

• 以 $V(G)$ 为顶点集;
• 以 $E(G)$ 中一切从 $V_2$ 连至 $V_1$ 的边为边集.
  

如此看来, 若随机划分, $\forall e\in E(G)$ 出现于 $E(G')$ 之概率恒为$\dfrac{1}{2}$. 故期望 $\mathbb E|E(G')|=\dfrac{|E(G)|}{2}$. 以上计入 $V_1=V(G)$ 之情形, 此时 $|E(G')|=0$ 低于平均值, 从而 $G$ 中的某一极大二部子图至少含有$\left\lceil\dfrac{|E(G)|}{2}\right\rceil$条边.

$\square$

________________________

定理 3 (Turán 问题, 极值图论学科之滥觞) 在保证不生成 $K_p$ 的情况下, $n$ 个点至多能添上几条边?

答案是 $\left\lfloor\left(1-\dfrac{1}{p-1}\right)\dfrac{n^2}{2}\right\rfloor$.

证明 下利用"期望值法"证明 Turán 定理. 记顶点集 $V(G)=\{v_1,\ldots,v_n\}$, 度 $d_i:=\deg v_i$, $\omega(G)$ 为 $G$ 中包含最大完全子图之顶点数. 例如 $\omega (G)=3$ 若且仅若 $G$ 包含 $K_3$ 而不含 $K_4$. 下证明 $\displaystyle{\omega(G)\geq\sum_{i=1}^n\dfrac{1}{n-d_i}}$.

为提取 $G$ 中完全子图, 定义 $\pi$ 为 $v_1,\ldots, v_n$ 的随机排序, 即$\pi\in\mathrm{Aut}(V(G))$). 定义 $C_\pi$ 为满足以下性质的集合: $\pi(v_j)\in C_\pi$若且仅若对任意 $l>j$ 均有 $\pi(v_l)\in C_\pi$. 定义随机变量 $X_i=1$ 若且仅若 $v_i\in C_\pi$; 反之 $X_i=0$. 注意到 $X_i=0$ 若且仅若 $\pi(v_i)$ 后包含任意非相邻点 $v_j$ 的置换 $\pi(v_j)$, 从而 $\mathbb EX_i=\dfrac{1}{n-d_i}$. 根据随机变量期望运算法则,
\[
\mathbb E|C_\pi|=\sum_{i=1}^n \mathbb EX_i=\sum_{i=1}^n\dfrac{1}{n-d_i}.
\] 注意到

\begin{align*}
n^2\leq&\left(\sum_{i=1}^n(n-d_i)\right)\left(\sum_{i=1}^n(n-d_i)^{-1}\right)\\
\leq&\left(n^2-2|E(G)|\right)\omega(G)\\
\leq&(n^2-2|E(G)|)(p-1)
\end{align*}
得证. 取等若且仅若 $G$ 为某一完全 $p-1$ 部图 $K_{r_1,\ldots,r_{p-1}}$, 其中 $r_i$ 取 $\left\lfloor\dfrac{r}{p-1}\right\rfloor$ 或$\left\lceil\dfrac{r}{p-1}\right\rceil$, 同时 $\sum_{i} r_i=r$.

$\square$

________________________

定理 4 (B. Green & T. Tao) 质数集合包含任意长度的等差数列 Ref

________________________

定理 5 称盒子 $\prod_{i=1}^n B_i$ 真包含于盒子 $\prod_{i=1}^n A_i$, 若且仅若 $B_i\subsetneq A_i$ 对一切 $i=1,\ldots, n$ 均成立. 则 $n$ 维立方体无法被划分为少于 $2^n$ 个盒子, 使得每个盒子均真包含于原立方体.

问题背景: 1999 年 8 月 17 日 (🐸), 美国东北部的一座小城里, 仲夏如期而至. 此日, 组合图论先辈 Danny Kleitman 正迎来他 65 岁的生日. 马赛诸纳大道 77 号的 conference room 里, Keith 与 Kiss 早年提出的那个 open question 再次被拿上了会桌...

证明 记 $A=\prod_{i=1}^n A_i$ 为超立方体, 给定盒子的一个有限划分 $A=\dot\cup_{i=1}^m B_i$ (显然$\min m\leq 2^n$). 任选 $A$ 的真子盒 $C=C_1\times\cdots \times C_n$, 其中 $|C_i|$ 均为奇数. 注意到必然事件
\[
\lor_{i=1}^m\{|C\cap B_i|\equiv1\mod 2\}.\]
从而
\begin{align*}
1&=P(\cup_{i=1}^m\{|C\cap B_i|\equiv1\mod 2\})\\
&\leq\sum_{i=1}^mP(\{|C\cap B_i|\equiv1\mod 2\})\\
&=m\cdot\dfrac{1}{2^n}
\end{align*}.
故 $m\geq 2^n$. 证毕.

若读者对 "无限集中谈奇偶性" 一点有顾虑, 则可以针对划分 $A=\dot\cup_{i=1}^m B_i$ 离散化 $A$: 即取 $A$ 中体积有限的真子盒 $A'$ 使得 (a) $|A_k'|$ 均为偶数, (b) $A'$ 与一切 $B_i$ 有非空交集. 此后即可放心采用上述方法.

$\square$

思考 若 $A$ 体积为奇数, 则至少需要几个体积为奇数的真子盒覆盖? 例如 $\{1,2,3\}^3$ 的最小奇数真子盒覆盖数显然为 $27$, $\{1,2,3,4,5\}^3$ 呢? 可能小于 $27$ 吗.

________________________

Czhang271828

hbghlyj 发表于 2022-3-17 21:43
5 Lovász Local Lemma
From Union Bound, we see that if $A_{1}, A_{2}, \ldots, A_{n}$ are "bad" event ...

To be updated.

Solution to Ex 1.

$\forall x\in [0,1)$, define $y=y(x)=\left\{\begin{align*}&x+0.1&&2\mid \lfloor 10 x\rfloor,\\&x-0.1&&2\not\mid \lfloor 10 x\rfloor.\end{align*}\right.$

Albeit dependent, both $y$ and $x$ have uniform distribution on $[0,1)$. The probability $x\in S$ is $|S|>1/2$, so is $y\in S$. As a result, $P(x\in S\land y\in S)>0$.

Solution to Ex 2.

Consider the tournament graph $G$, where $v_i\to v_j$ means $i$ is defeated by $j$. Of course, the adjacency matrix $A(G)$ satisfies $A(G)^T+A(G)+I=$ all-one matrix.

Now we consider a random $k$ -element subset $P$ of $V(G)=\{v_i\}_{i=1}^{799}$. Let $N$ denotes the number of teams TOTALLY defeated by $P$. Then $\mathbb EN=\sum_{v\in V(G)}\binom{\deg_{\to} v}{k}/\binom{799}{k}$. Here $\deg_\to v:=|\{v'\mid v'\to v\}|$. Since the average of $\mathbb E(\deg _\to v)$ is exactly $399$, we deduce that
\[
\mathbb E N\geq 799\cdot \dfrac{\binom{399}{k}}{\binom{799}{k}}\approx 800\cdot2^{-k}.
\]
Such partition exists whenever $\lceil \mathbb EN\rceil+k\geq 14$. Hmmm... I think the existence of the case "$13$ defeats $1$" is too trivial. However, $7$ - $7$ seems tight enough for the inequality since $800\cdot 2^{-7}=6.25\leq 7$.

$\square$

It is better to restate Question II as

Prove that in a tournament with $799$ teams, for every partition $(14-k,k)$, there exist two disjoint groups consisting $14-k$ and $k$ teams in each group, such that one group defeated the other TOTALLY.

Solution to Ex 3.

I think this question has something to do with a meme called Soviet Jokes.

We denote all commitees by $\{i\}_{i=1}^{16000}$. Let $S$ be any two-elemented subset of $\{i\}_{i=1}^{16000}$. Let $n_k$ be the number of committees that the $k$ -th person belongs to. The probability for the $k$ -th person taking part in both two commitees in $S$ is $1/\binom{800}{2}$, this is due to each person participates in $800$ commitees in average. The expectation of the number of people belonging to each committees in $S$ simultaneously is
\[
\sum_{k=1}^{1600}\dfrac{\binom{n_k}{2}}{\binom{16000}{2}}\geq 1600\cdot \dfrac{\binom{800}{2}}{\binom{16000}{2}}\geq 3.9.
\] Therefore, one can find two committees having at least four common members.

$\square$

The probability method is SURPRISING if the decimal part of the expectation is close enough to $0$. For instance,

In the Duma there are 1600 delegates, who have formed 16000 committees of 81 persons each. Use probabilistic method to prove that one can find two committees having at least FIVE common members. Hint: We see that $1600\cdot \dfrac{\binom{810}{2}}{\binom{16000}{2}}\geq 4.09$.

Solution to Ex 4.

See 定理 3 . One can prove the following statement by the same token: a graph with degree $d_1,\ldots, d_n$ has an independent set of size at least $\sum_{i=1}^n\dfrac{1}{d_i+1}$.

Solution to Ex 5.

$\forall X\in \mathcal P(\{i\}_{i=1}^n)$, the probability $|A_k\cap X|$ is odd is $1/2$, for each given $A_k$. Therefore,
\[
\mathbb E|\{i\mid |A_i\cap X|\text{ is odd}\}|=\dfrac{m}{2}.\] As a result, there exists some $X$ such that $|\{i\mid |A_i\cap X|\text{ is odd}\}|=\lceil m/2\rceil$.

$\square$

Czhang271828

hbghlyj 发表于 2022-3-17 21:43
5 Lovász Local Lemma
From Union Bound, we see that if $A_{1}, A_{2}, \ldots, A_{n}$ are "bad" event ...

Solution to Ex. 6 is quite difficult. The least number of species that a good classifier cannot describe is called the Plotkin bound, which can be rephrased in the language of coding theory:

Plotkin bound is the largest binary code with length $n$ and distance at least $\lfloor n/2\rfloor+1$?

Solution. We shall apply the following notations first.

• Let $H_m$ be an $m\times m$ Hadamard matrix, with entries in $\{\pm 1\}$, normalized so the first row and column are all $+1$.
• Let $H_m'$ be the $m\times (m-1)$ matrix given by removing the first column of $H_m$.
• Let $H_m''$ be the $(m/2)\times (m-2)$ matrix given by deleting all rows from $H'_m$ whose first entry is $-1$, then deleting the first column of what is left.
  

Let $S$ denotes the set of $\pm 1$ -valued vectors in $\mathbb R^n$ which $x\cdot y<0$ for every distinct pair $(x,y)$. Here one can regard $x$ as a plant with $i$ -th feature present whenever the $i$ -th entry of $x$ is $+1$, vice versea. One can distinguish $x$ and $y$ whenever $x\cdot y<0$.

Here are some constructions when Plotkin bound attains.

• When $n=4k+3$, the Plotkin bound is $4k+4$. One knows that $H_{n+1}$ is always constructable. Then let $S$ be the set of rows of $H_{n+1}'$.
• When $n=4k+2$, the Plotkin bound is $2k+2$. It can be constructed by the set of rows of $H_{n+2}''$.
• When $n=4k+1$, the Plotkin bound is $2k+2$. It can be constructed by the set of rows of $H_{n+3}''$ with any column deleted.
• When $n=12k+8$, the Plotkin bound is $4k+4$. It can be constructed by the set of rows of $[H_{4k+4}'\,\,H_{4k+4}'\,\,H_{4k+4}']\in\mathbb R^{(4k+4)\times (12k+9)}$ with any column deleted.
• When $n=12k+4$, the Plotkin bound is $4k+2$. It can be constructed by (i) Take the first $4k+2$ rows of $H_{8k+4}'$ to obtain $Q\in \mathbb R^{(4k+2)\times (8k+3)}$, (ii) Let $S$ be the set of rows of $[Q\,\, H_{8k+4}'']\in\mathbb R^{(4k+2)\times (12k+5)}$ with any column deleted.
• When $n=12k$, the Plotkin bound is $4k$. It can be constructed by (i) Take the first $4k$ rows of $H_{8k+4}''$ to obtain $R\in \mathbb R^{4k\times (8k+2)}$, (ii) Let $S$ be the set of rows in $[R\,\,H_{4k}']\in \mathbb R^{4k\times (12k+1)}$ with any column deleted.
  

In Ex. 6, $n=12\cdot 8+4$, thus the maximum number of species that a good classifier can describe is $4\cdot 8+2=34$.

Czhang271828

Czhang271828 发表于 2022-8-9 15:31
Solution to Ex. 6 is quite difficult. The least number of species that a good classifier cannot de ...

或者可以如此转化问题: $\{\pm 1\}^n$ 中最多能找到几个两两内积为负数的向量?