成人网站在线看。,欧美亚洲无码视频,亚洲黄色免费视频,国产夫妻自拍在线观看,一区二区不卡无码免费,大香蕉伊人免费网站,国产69精品久久久久久久久久久久,亚洲1234区

數(shù)學(xué)算法俱樂(lè)部

日期：2020年07月29日

正文共：1438字4圖

預(yù)計(jì)閱讀時(shí)間：4分鐘

來(lái)源：算法與數(shù)學(xué)之美-姜子麟

我的研究方向是組合數(shù)學(xué) Combinatorics，又稱(chēng)具體數(shù)學(xué)。這個(gè)學(xué)科里絕大多數(shù)的問(wèn)題都能用簡(jiǎn)單的語(yǔ)言描述，但解答又不顯然。

在卡內(nèi)基梅隆大學(xué)讀研究生的第二年暑假，導(dǎo)師推薦給了我一本書(shū) Thirty?three Miniatures，作者是 Ji?í Matou?ek。乍一看書(shū)名，可能會(huì)猜測(cè)是一本包含 33 個(gè)小故事的故事集（突然想起了桂綸鎂主演的第 36 個(gè)故事），但實(shí)際上這個(gè)猜測(cè)也八九不離十了。書(shū)的副標(biāo)題是 Mathematical and Algorithmic Applications of Linear Algebra —— 這本書(shū)包含了 33 個(gè)線性代數(shù)的數(shù)學(xué)和算法應(yīng)用。

比如書(shū)中回答了以下組合數(shù)學(xué)問(wèn)題：

在 Oddtown 里面住著 n 個(gè)居民，他們的主要工作是組建各種各樣的俱樂(lè)部。為了限制俱樂(lè)部的個(gè)數(shù)，市政府決定頒布如下條例：每個(gè)俱樂(lè)部只能有奇數(shù)個(gè)會(huì)員并且任何兩個(gè)俱樂(lè)部只能有偶數(shù)個(gè)公共會(huì)員。證明：不可能組建超過(guò) n 個(gè)俱樂(lè)部。（取自 Miniature 3）
平面上不存在四個(gè)點(diǎn)，兩兩之間距離均為奇數(shù)。（取自 Miniature 6）
一個(gè)長(zhǎng)寬比為無(wú)理數(shù)的長(zhǎng)方形無(wú)法用有限個(gè)正方形鋪砌（正方形內(nèi)部不相交且覆蓋長(zhǎng)方形）。（取自 Miniature 12）
一個(gè)網(wǎng)店正在處理訂單，突然所有小于 1 元的硬幣都被作廢了！所有商品的價(jià)格都要取整（可以選擇向上或向下取整）。如果每種商品賣(mài)了至多 t 個(gè)，并且每個(gè)訂單中每種商品至多包含 1 個(gè)，那么有一種取整的辦法使得每個(gè)訂單的總價(jià)變化不超過(guò) t 元（有趣是總價(jià)的變化和訂單數(shù)、商品數(shù)均無(wú)關(guān)）。（取自 Miniature 19）

令人驚訝的是，理解這些問(wèn)題的解答只需要明白大學(xué)本科的線性代數(shù)知識(shí)！好吧，其實(shí)還需要知道有限域上的線性代數(shù)。在此，我補(bǔ)充一個(gè)在這本書(shū)里面沒(méi)有的組合數(shù)學(xué)問(wèn)題。

問(wèn)題：平面上 n 條一般位置的直線（沒(méi)有三線共點(diǎn)或兩線平行）至少會(huì)產(chǎn)生 n - 2 個(gè)小三角形。

解釋一下小三角形的意思：

如圖所示，5 條直線把平面劃分后，形成的區(qū)域中為三角形的部分就是所謂的小三角形。

現(xiàn)在，就是見(jiàn)證線性代數(shù)的奇跡的時(shí)刻了！

證明：反證法，假設(shè)產(chǎn)生了 m < n - 2 個(gè)小三角形。固定 L1, L2 兩條直線，再讓其他直線平移起來(lái)！也就是說(shuō)，對(duì) L1, L2 外的每條直線的法向量制定一個(gè)速率（可正可負(fù)）。附加條件是：每個(gè)小三角形大小保持不變。如下圖，如果斜的兩條直線決定以那樣的速度移動(dòng)，為了保持小三角形大小不變，水平的直線必須以某個(gè)規(guī)定的速度移動(dòng)。

換句話說(shuō)，決定小三角形的三條直線的平移速率必須滿足某個(gè)約束條件。可以證明每個(gè)約束條件關(guān)于平移速率是線性的（請(qǐng)讀者自己思考）。那么現(xiàn)在我們有 m 個(gè)小三角形，即 m 個(gè)線性方程，以及 n - 2 個(gè)直線平移速率作為未知元，由于 m < n - 2，線性代數(shù)告訴我們存在非零解！也就是說(shuō)，確實(shí)可以在保持每個(gè)小三角形大小不變的情況下，讓 L1, L2 外的一部分直線平移起來(lái)！在整個(gè)平移的過(guò)程中，考慮第一次某三條直線交匯于一點(diǎn)的前一個(gè)剎那，如下圖。

ちょっと待って，說(shuō)好小三角形大小保持不變呢！下一刻，這個(gè)小三角形都要消失了！矛盾 ╮(╯_╰)╭

這里有一個(gè)需要補(bǔ)充的細(xì)節(jié)，為什么一定會(huì)有三條線在運(yùn)動(dòng)后交于一點(diǎn)呢？一方面，L1, L2 兩條直線固定，考慮第三條直線 L 正在移動(dòng)，那必定有一個(gè)時(shí)刻 t 直線 L 會(huì)穿過(guò) L1 和 L2 的交點(diǎn)。如果這個(gè)時(shí)刻 t 為負(fù)數(shù)，那我們轉(zhuǎn)而考慮反轉(zhuǎn)所有速度后的運(yùn)動(dòng)。

證畢。

文初提到的作者無(wú)私地將初稿放在他的主頁(yè)上。如果想閱讀，可以直接以書(shū)名作為關(guān)鍵詞搜索。我個(gè)人非常得益于 Ji?í Matou?ek 的寫(xiě)作，但很不幸，他于 2015 年 3 月 9 日去世了。謹(jǐn)以此紀(jì)念他。

后記：在 2017 年于 Akko 舉行的以色列數(shù)學(xué)大會(huì)上，有幸遇到了文中描述證明的發(fā)現(xiàn)者 Alexei Kanel。這篇文章 Taking on triangles: in search of answers between the lines? (https://www.researchgate.net/publication/301276231_Taking_on_triangles_in_search_of_answers_between_the_lines) 中詳細(xì)描述了發(fā)現(xiàn)這個(gè)證明的過(guò)程。

—?THE END —

?圍棋中的數(shù)學(xué)原理

?如何畫(huà)出優(yōu)秀的架構(gòu)圖？

?八卦二進(jìn)制

?機(jī)器學(xué)習(xí)中需要了解的 5 種采樣方法

?北大讀博手記：怎樣完成自己的博士生涯？非常具有指導(dǎo)性！

?他把400個(gè)流氓送進(jìn)哈佛耶魯！寒門(mén)與貴族之間，只差一個(gè)數(shù)學(xué)老師！

線性代數(shù)在組合數(shù)學(xué)中的應(yīng)用