什么是皮克定理?
1899年,猶太數(shù)學(xué)家皮克(Georg Alexander Pick)發(fā)現(xiàn)了一個被譽為“有史以來最重要的100個數(shù)學(xué)定理之一”的“皮克定理”(Pick's Theorem)。這個定理是這樣說的:給定頂點座標(biāo)均是整點(或正方形格子點)的簡單多邊形,其面積?和內(nèi)部格點數(shù)目?、邊界格點數(shù)目?的關(guān)系為?=?+?/???。
例如:
根據(jù)皮克定理,我們可以得到:
我們可以通過間接計算的方法驗證這個結(jié)果:
S=S長方形-(S1+S2+S3+S4+S5)=12×8-(1×4÷2+6×4÷2+6×2÷2+6×4÷2+7×3÷2)=96-(2+12+6+12+10.5)=96-42.5=53.5。
最終的結(jié)果正如皮克定理所說的那樣,面積的計算居然可以通過數(shù)點數(shù)來得到,很神奇對不對?
問題的起源
皮克定理的發(fā)現(xiàn)要從古埃及說起。
古埃及人鋪地板時發(fā)現(xiàn),用同樣大小且同一種的正多邊形鋪地板時,只能用正三角形、正方形與正六邊形,得到三種圖案。
古埃及人又從鋪地板中,發(fā)現(xiàn)三角形三個內(nèi)角和為一平角(即180°)。
我們也可以利用折紙的實驗,發(fā)現(xiàn)這個定理。即沿著DE、DG、EF把三角形折成長方形DEFG,那么∠?、∠?、∠?疊合于A’點,成為一個平角。
定理的證明
一般而言,數(shù)學(xué)是先有觀察與猜測(這個階段允許犯錯),然后才有試驗、修正與證明。數(shù)學(xué)絕不是突然從天上掉下一個公式或定理,然后就要我們?nèi)プC明。
為了證明公式,首先讓我們分析單純多邊形:
(1)最簡單的單純多邊形就是原子三角形(atomic or primitive triangles),亦即除了三個頂點之外,三邊及內(nèi)部皆不含格子點之三角形,見下圖,其面積皆為?/?,并且可用公式來計算:?/?+???=?/?。因此,對于原子三角形,上述公式成立。
(2)其次,我們觀察到對于任意的單純多邊形都可以先分割成三角形(即三角形化),再進一步分割成原子三角形的組合(這叫做原子化),見下圖。
(3)最后考慮任何單純多邊形Γ,將它分割成兩個單純多邊形Γ?與Γ?,見下圖。設(shè)Γ有?個邊界點、?個內(nèi)點,并且Γ?和Γ?分別有??個與??個邊界點、有??個與?2個內(nèi)點。再設(shè)Γ?與Γ?有?3個共同的邊界點。
則:
?=??+??????+?;?=??+??+????
所以:
?/?+???=(??/?+????)+(??/?+????)
即:Γ=Γ?+Γ?。
因此,我們發(fā)現(xiàn),這個公式在分割下具有加性(additivity)。
現(xiàn)在換個角度再來證明一下這個定理的正確性。
重新整理皮克定理的證明思路,具體如下:
(1)首先,證明對長方形是成立的;
(2)接著,再證明對直角三角形是成立的;
(3)然后,繼續(xù)證明對任意三角形也是成立的;
(4)最后,證明對于兩個圖形的組合還是成立的。
假設(shè)這個公式是對的,我們先看第四步:證明對于兩個圖形的組合是成立的。
將兩個圖形組合在一起。注意:重合的兩個邊界點,分別多了1/2個點,所以最后是減去2,而不是減去1。
回頭證明第一部分:公式對長方形是成立的。以一個長為?、寬為?的長方形為例。
接著證明第二部分:對直角三角是成立的。以一個底為?、高為?的三角形為例。先假設(shè)斜邊上沒有邊界點(除了頂點)。
繼續(xù)?,F(xiàn)在考慮斜邊上有邊界點的情況。通過對第四種情況的證明,我們可以將三角形分割為長方形和三角形的組合。
最后證明第三種情況:皮克定理對任意三角形也是成立的。
這里,我們可以通過從長方形減去外圍三角形的方法得到證明。
C語言網(wǎng)提供由在職研發(fā)工程師或ACM藍橋杯競賽優(yōu)秀選手錄制的視頻教程,并配有習(xí)題和答疑,點擊了解:
一點編程也不會寫的:零基礎(chǔ)C語言學(xué)練課程
解決困擾你多年的C語言疑難雜癥特性的C語言進階課程
從零到寫出一個爬蟲的Python編程課程
只會語法寫不出代碼?手把手帶你寫100個編程真題的編程百練課程
信息學(xué)奧賽或C++選手的 必學(xué)C++課程
藍橋杯ACM、信息學(xué)奧賽的必學(xué)課程:算法競賽課入門課程
手把手講解近五年真題的藍橋杯輔導(dǎo)課程