原文鏈接：https://yanghan.life/2019/01/15/兩道有趣的離散數(shù)學(xué)題目/
有兩道比較有趣的題目痪蝇，為了防止忘掉荆忍，記錄一下禁灼。
1 實(shí)數(shù)集uncountable
這里countable的定義就是與集合里的元素能與自然數(shù)集一一對應(yīng)昵仅，比如說偶數(shù)集和自然數(shù)集有2n和n的對應(yīng)關(guān)系退渗，所以說這兩個集合大小相等导绷，都是.
這道題目是當(dāng)年大二時候的離散數(shù)學(xué)課后習(xí)題犀勒，最近剛好跟人聊天聊到相關(guān)的話題，回憶了一下怎么證明。
這里記錄幾個簡單的結(jié)論/題目贾费。
1.1 有理數(shù)集countable
法一（直觀）：
對于有理數(shù)m/n, 按
1/1
1/2 2/1
1/3 2/2 3/1
1/4 2/3 3/2 4/1
...
排列去數(shù)枚碗，可以與自然數(shù)一一對應(yīng)。
法二：
對于任意一個既約有理數(shù)m/n铸本，構(gòu)造映射肮雨，y是自然數(shù)，那么對于不同的m/n箱玷，一定有不同的自然數(shù)y怨规。所以自然數(shù)集小于等于有理數(shù)集。
反過來锡足，自然數(shù)是有理數(shù)的子集波丰，所以自然數(shù)集又不大于有理數(shù)集。
綜上舶得，兩集合基數(shù)相等掰烟，所以有理數(shù)集是可數(shù)集。
1.2 若集合A, B都countable沐批，則
countable
一纫骑、若 或者
, 顯然。
二九孩、若 且
countable, 對應(yīng)
countable, 對應(yīng)
.
定義 :
即可證明 countable.
1.3 (0, 1)的無理數(shù)uncountable
假設(shè)(0,1)的實(shí)數(shù)countable,
則對于(0,1)的實(shí)數(shù)集：X {x1,x2,x3,...,xn}
總能找到一個實(shí)數(shù)H=0.abcdefg….. , 使得
a != x1小數(shù)點(diǎn)后第一位
b != x2小數(shù)點(diǎn)后第二位
c != x3小數(shù)點(diǎn)后第三位
...
由此得出
產(chǎn)生矛盾, 所以(0,1)的實(shí)數(shù)集uncountable.
實(shí)數(shù)=有理數(shù)+無理數(shù)
有理數(shù)countable先馆，所以無理數(shù)uncountable.
由(0,1)的實(shí)數(shù)集uncountable可知實(shí)數(shù)集uncountable.
2 Stolen Necklace Problem
這道題目來自3Blue1Brown的Sneaky Topology。這里簡單總結(jié)一下要點(diǎn)躺彬。
題目：把一串有n種寶石的項鏈平分給兩個人（每種寶石有偶數(shù)個）煤墙，那么在項鏈上至多切n刀即可完成。
2.1 Borsuk-Ulam Theorem
簡單地拿三維空間里的球體來說宪拥，通過一個連續(xù)函數(shù)將其映射到一個二維平面 仿野，必然可以找到一對在兩極的點(diǎn)(antipodes 對跖點(diǎn))在映射后是二維平面上的同一個點(diǎn)。
簡單證明一下：
構(gòu)造她君，
所以對于赤道上的點(diǎn)脚作，的圖像是圍繞原點(diǎn)的一個圈。將赤道這條緯線連續(xù)向北極移動犁河，到北極的時候
的值是一個點(diǎn)鳖枕。在這個連續(xù)的過程中
的圖像必然經(jīng)過原點(diǎn)魄梯，這就證明了
有零點(diǎn)桨螺，原命題得證。
2.2 回到原題目
假設(shè)項鏈總長度為1酿秸，切兩刀后的三段長度為灭翔。那么
意味著每種切法都對應(yīng)球上一點(diǎn)。
antipodes對應(yīng)的切法相同，但是分法互換肝箱。(e.g. xz給A哄褒，y給B 和 y給A，xz給B 這兩種分法)
意味著AB兩人分得的內(nèi)容相同煌张，互換后不變呐赡。
這樣，Borsuk-Ulam Theorem 就證明了 2種寶石的 Stolen Necklace Problem 可以用2刀解決骏融。
Borsuk-Ulam Theorem 和 Stolen Necklace Problem 都可以推廣到n.
