logo 首頁 > 文匯報 > 百科啟智 > 正文

【奧數揭秘】派生果用中國剩餘定理

2017-02-15

社會上的長者越多越多,安老院也不少,久不久就有些義工去探訪,派一點水果。派水果的時候,為了每人都有一些,會預多一點。

每次幾個幾個的派,由餘下的數量中,可以估算出長者的人數。

問 題

義工到安老院派水果給長者,每人有一個蘋果,一個橙和一個梨。義工家明每次拿7個蘋果去派,派完又拿7個再派,如此類推,一直派到最後,手上餘4個。義工家華每次拿5個橙去派,派到最後手上餘2個。

義工家輝每次拿3個梨去派,最後手上餘2個。粗略看來,估計長者少於100人,求長者人數。

答 案

設長者有x人。由家明7個7個地派,最後手上餘4個,即最後一次只派了3個,得知x除以7餘3。類似地,由家華的情況,得知x除以5餘3;由家輝的情況,得知x除以3餘1。

由x除以7餘3及除以5餘3,得知若x除以7和5的最小公倍數35,亦餘3。之後考慮除以35餘3的正整數,由小至大依次為38、73、108、108大於100,因此不用再考慮比108大的數。

再檢查除以3餘1的條件,得知長者人數為73人。

「韓信點兵」簡單化

這道題數學的一面來說,就是有一個未知數x,分別除以3個數之後,得出3個餘數,那炯o樣的最小正整數x是什活H這是一個在數學上知名的問題,叫「韓信點兵」。

求出這樣的x的普遍方法,稱為「中國剩餘定理」,當中另外要求x除以的這3個數之中,任意兩個互質,即最大公因數是1,而且相關的數字亦可不止3個。網上相關的文章有很多,不過符號是挺多的,看來比較複雜,以下嘗試就定理的基本思路,指出重點。

先考慮x這個數的形式,設x=(3)(5)(a)+(5)(7)(b)+(7)(3)(c),其中a、b和c都是未決定的數。為什洎n這樣設定呢?因為這樣只需要找到適當的a、b和c,就能使x符合條件除以3餘1,除以5餘3和除以7餘3的條件。不過算出來可能會過大,需要略為調整。

這樣的x除以3的話,(3)(5)(a)和(7)(3)(c)兩項都是3的倍數,對x除3的餘數沒影響。真正影響x除以3的餘數的,就只有中間的(5)(7)(b)=35b。而35b除以3的餘數,亦即除以3的餘數,因為其中35b=3×11b+2b。要使x除以3餘1,即要求2b除以3餘1,可取b=2。

同理,若x除以5,(3)(5)(a)和(5)(7)(b)都是5的倍數,影響餘數的就只有(7)(3)(c)=21c,21c=5×4c+c。若要使x除以5得3,可取c=3。

類似地可以考慮x除7,(5)(7)(b)和(7)(3)(c)都是7的倍數,影響餘數的就只有(3)(5)(a)=15a,15a=7×2a+a。若要使x除以7得3,可取a=3。

這樣x=(3)(5)(3)+(5)(7)(2)+(7)(3)(3)=178,比題目中的限制100還要大,不過只需要減去3、5和7的最小公倍數105,即可得178-105=73。

可推廣至其他數字

以上絕不單是把題目重新解一次,其意義在於,它能推廣至其他數字。當中把x的形式設定為x=(3)(5)(a)+(5)(7)(b)+(7)(3)(c)是關鍵的一步。

先取能與餘數相對應的a、b及c,然後再取3、5及7的最小公倍數105,再減法105的倍數就可以了。

再舉一例:正整數y除以3餘1,2餘1,7餘3。那樣要求最小的y,就考慮y=(2)(7)(a)+(3)(7)(b)+(3)(2)(c)。

經嘗試後得y=(2)(7)(2)+(3)(7)(1)+(3)(2)(4)=73,再減去3、2和7的最小公倍數42,得31為滿足條件的最小正整數。

結 語

以上是就茪@個安老院分水果的問題,帶出了數論之中的中國剩餘定理,提供了基本的思路。

定理的正式的形式,需要用到許多同餘理論,同餘理論是奧數中常用的工具,威力強大,由於篇幅所限,日後再詳細介紹。 ■張志基

簡介:香港首間提供奧數培訓之教育機構,每年舉辦奧數比賽,並積極開辦不同類型的奧數培訓課程。學員有機會獲選拔成為香港代表隊,參加海內外重要大賽。詳情可瀏覽:www.hkmos.org。

逢星期三見報

讀文匯報PDF版面

新聞排行
圖集
視頻