2019-01-15 两道有趣的离散数学题目

2019-01-15 本文已影响2人 y4nghan

原文链接：https://yanghan.life/2019/01/15/两道有趣的离散数学题目/

有两道比较有趣的题目，为了防止忘掉，记录一下。

1 实数集uncountable

这里countable的定义就是与集合里的元素能与自然数集一一对应，比如说偶数集和自然数集有2n和n的对应关系，所以说这两个集合大小相等，都是 $\aleph 0$ .

这道题目是当年大二时候的离散数学课后习题，最近刚好跟人聊天聊到相关的话题，回忆了一下怎么证明。

这里记录几个简单的结论/题目。

1.1 有理数集countable

法一（直观）：

对于有理数m/n, 按

1/1
1/2 2/1
1/3 2/2 3/1
1/4 2/3 3/2 4/1
...

排列去数，可以与自然数一一对应。

法二：

对于任意一个既约有理数m/n，构造映射 $y=2^n3^m$ ，y是自然数，那么对于不同的m/n，一定有不同的自然数y。所以自然数集小于等于有理数集。

反过来，自然数是有理数的子集，所以自然数集又不大于有理数集。

综上，两集合基数相等，所以有理数集是可数集。

1.2 若集合A, B都countable，则 $A \cup B$ countable

一、若 $A \subseteq B$ 或者 $A \supseteq B$ , 显然。

二、若 $A \backslash B \neq \phi$ 且 $B \backslash A \neq \phi$

$A \cup B = A \cup (B \backslash A)$

$A$ countable, 对应 $f:A \rightarrow N$

$B \backslash A$ countable, 对应 $g:(B \backslash A) \rightarrow N$ .

定义 $h:A \cup B \rightarrow N$ :

$h(x)= \begin{cases} 2f(x)& x \in A\\ 2g(x)+1& x \in B \backslash A \end{cases}$

即可证明 $A \cup B$ countable.

1.3 (0, 1)的无理数uncountable

假设(0,1)的实数countable,

则对于(0,1)的实数集：X {x1,x2,x3,...,xn}

总能找到一个实数H=0.abcdefg….. , 使得

a != x1小数点后第一位

b != x2小数点后第二位

c != x3小数点后第三位

...

由此得出 $H \notin X$

产生矛盾, 所以(0,1)的实数集uncountable.

实数=有理数+无理数

有理数countable，所以无理数uncountable.

由(0,1)的实数集uncountable可知实数集uncountable.

2 Stolen Necklace Problem

这道题目来自3Blue1Brown的Sneaky Topology。这里简单总结一下要点。

题目：把一串有n种宝石的项链平分给两个人（每种宝石有偶数个），那么在项链上至多切n刀即可完成。

2.1 Borsuk-Ulam Theorem

Borsuk-Ulam Theorem

简单地拿三维空间里的球体来说，通过一个连续函数将其映射到一个二维平面 $f: R^3 \rightarrow R^2$ ，必然可以找到一对在两极的点(antipodes 对跖点)在映射后是二维平面上的同一个点。 $f(x) = f(-x)$

简单证明一下：

构造 $g(x)$ ，

$g(x) = f(x) - f(-x)$

$g(x) = -g(-x)$

所以对于赤道上的点， $g(x)$ 的图像是围绕原点的一个圈。将赤道这条纬线连续向北极移动，到北极的时候 $g(x)$ 的值是一个点。在这个连续的过程中 $g(x)$ 的图像必然经过原点，这就证明了 $g(x)$ 有零点，原命题得证。

2.2 回到原题目

假设项链总长度为1，切两刀后的三段长度为 $x,y,z$ 。那么
$x^2+y^2+z^2=1$
意味着每种切法都对应球上一点。
antipodes对应的切法相同，但是分法互换。(e.g. xz给A，y给B 和 y给A，xz给B 这两种分法)
$f(x)=f(-x)$ 意味着AB两人分得的内容相同，互换后不变。

这样，Borsuk-Ulam Theorem 就证明了 2种宝石的 Stolen Necklace Problem 可以用2刀解决。

Borsuk-Ulam Theorem 和 Stolen Necklace Problem 都可以推广到n.

上一篇下一篇

猜你喜欢

热点阅读