两道有趣的离散数学题目
有两道比较有趣的题目,为了防止忘掉,记录一下。
1 实数集uncountable
这里countable的定义就是与集合里的元素能与自然数集一一对应,比如说偶数集和自然数集有2n和n的对应关系,所以说这两个集合大小相等,都是\(\aleph 0\).
这道题目是当年大二时候的离散数学课后习题,最近刚好跟人聊天聊到相关的话题,回忆了一下怎么证明。
这里记录几个简单的结论/题目。
1.1 有理数集countable
法一(直观):
对于有理数m/n, 按 1
2
3
4
51/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
简单地拿三维空间里的球体来说,通过一个连续函数将其映射到一个二维平面 \(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.
- 本文链接:https://yanghan.life/2019/01/15/%E4%B8%A4%E9%81%93%E6%9C%89%E8%B6%A3%E7%9A%84%E7%A6%BB%E6%95%A3%E6%95%B0%E5%AD%A6%E9%A2%98%E7%9B%AE/
- 版权声明:本博客所有文章除特别声明外,均采用 CC BY-NC-SA 3.0 CN 许可协议。转载请注明出处!
分享