奧數齊齊玩 (已更新 (30/11/2008)

Naozumi

International Mathematics Olyympiad (IMO)係一個國際性的中學生(好似有小學版)的比賽.
第1届IMO於1959年在羅馬利亞舉行.而它的logo及會旗則於1995年首次在加拿大出現



簡單介紹一下IMO的背景資料:

奧數的syllabus包括:
    * Number Theory (數論), including
          o Fundamental Theorems on Arithmetic
          o Linear and quadratic Diophantine equations, including Pell's equation
          o Arithmetic of residues modulo n (同餘), Fermat's (費馬) and Euler's (尤拉) theorems
    * Algebra (代數), including
          o Fundamental Theorems on Algebra
          o Symmetric polynomials of several variables, Vieta's theorem
    * Combinatorics (組合數學), including
          o Graph theory (圖論)
    * Geometry(幾何學), including
          o Properties of the orthocentre(垂心), Euler's line, nine-point-circle (9點圓), Simson line, Ptolemy's inequality, Ceva and Menelaus etc.

每個參賽國家最多可派6名代表出賽 (另加兩名唔參賽的leader),但是他們要獨立地解開難題.
比賽分兩日舉行,每日做3題題目,每題7分,時限為每人每日4.5小時.
除左筆紙同埋個腦外,乜野計數機,computer都唔可以帶入場.

獎牌的計分去如下:
    * GOLD MEDAL: the top 1/12 of scores receive gold medals
    * SILVER MEDAL: the next 2/12 of scores receive silver medals
    * BRONZE MEDAL: the next 3/12 of scores receive bronze medals
    * HONORABLE MENTION: any competitor who receives a perfect score of 7 on any one question, but who does not receive a medal, is awarded an honorable mention


當然世界各地都有自己的MO,可以當係為IMO做選拔賽. 香港區奧數簡稱為HKMO

Related websites
香港教育學院
http://imo.math.ca/
http://www.imo-official.org/general.aspx

大家見到個syllabus係咪好驚呢 ,因為中學課程係唔會特別講,當然IMO亦只會用到這些topic的入門知識,而呢d知識係可以簡單地推出黎啫.

[ 本帖最後由 Naozumi 於 2008-11-30 06:24 PM 編輯 ]

Naozumi

乜野係數論呢? 好粗略咁講,佢係研究整數的整除性,質數的關係等等. 數論廣泛地用於關乎internet安全的密碼學(cryptography)
呢d野係中學課程近乎冇提過,不過講真唔係難得咁緊要 (當然指係MO/IMO用到的部分內容). 舉個例啦

設 a、b和 c 是三個質數。若 a < b < c 及 c = a^2 + b^2 ，求 a 的值。
Let a, b and c are three prime numbers. If a < b < c and c = a^2 + b^2 , find the value of a.
HKMO(2005 – 2006) Heat Event  (Group)

明顯 a同b唔可以同時係單數, 否則c會係一個大過2的雙數
咁a或b有一個係雙數, 根據題設,a,b及 c要係質數,所以a = 2

Let P and P+2 be both prime numbers satisfying P(P+2)<= 2007. If S represents the sum of all such possible values of P, find the value of S.
設P 及 P + 2均為質數並滿足 P(P+2)<= 2007  。 若 S 是符合上述要求的質數 P的總和，求 S 的值。
HKMO(2006 – 2007) Final Event 1 (Group)

應該點攪呢?我地要逐一分析:
1. 明顯 P係單數
2. P唔可以係13,23,...,因為P+2會係5字尾,明顯唔係質數
3. 要搵P的範圍

關於第3點,有網友可能會用二次公式(Quadratic formula)解 P^2 + 2P - 2007 = 0,好可惜,冇計數機係手,好難解到出黎. 所以要另尋方法
留意 P, P+2的"中間"係 P+1,所以P(P+2)<= 2007 可以改寫成:
(P+1 -1)(P+1+1) <= 2007
(P+1)^2 -1 <= 2007
(P+1)^2<= 2008
再留意 45^2 = 2025, 44^2 = 1936
所以 P<= 43
數番哂 1 - 43的質數唔太難 (13, 23, 43又自動out),再加埋 P+2都要係質數,所以剩番d數都唔太多
P = 3, 5, 11, 17,19, 21, 29, 41


另一題就深D

Find all solutions in positive integers x, y, z to the simultaneous
equations
求以下聯立方程組的所有正整數解.
x + y − z = 12
x^2 + y^2 − z^2 = 12.
British MO 2007 - 2008

首先將條方程組改寫成:
y - z = 12 - x  ...(1)
y^2 − z^2 = 12 - x^2 ...(2)

(y^2 - z^2)/(y - z) = y+z 都係整數 (留意 y - z 不可能為 0)
y + z = (12 - x^2)/(12 - x) ... (3)

由(1)(3)可得
y =1/2 [12 - x + (12 - x^2)/(12 - x)]
   = (78 - 12x)/(12 - x)
   = 12 - 66/(12 - x)
z = -1/2 [12 - x - (12 - x^2)/(12 - x)]
   = -(66 - 12x + x^2)/(12 - x)
   =  [(x - 6)^2 + 30]/(x - 12)   
66的因子為1,2,3,6,11, -1, -2, -3,-6,-11,-22,-33,-66
但由於 y > 0,所以x只可以係1,6, 13, 14, 15,18, 23,34, 45, 78
再由於 z > 0,  所以x只可以係 13, 14, 18, 34, 45, 78
剩番果d就係dry checking的功夫
簡單計算一下,得
x = 13, y = 78, z = 79
x = 14, y = 45, z = 47
x = 15, y = 34, z = 37
x = 18, y = 23, z = 29
x = 23, y = 18, z = 29
x = 34, y = 15, z = 37
x = 45, y = 14, z = 47
x = 78, y = 13, z = 79

[ 本帖最後由 Naozumi 於 2008-11-9 07:51 PM 編輯 ]

Naozumi

數論的題目有很多種,除左上面果d, 仲有計一計整數的整除性或餘數,都係HKMO都算幾hot的題目

A six-digit number 1234xy is divisible by 8 ans 9. Given that x + y = c, find the value of c.
一個六位數1234xy能同時被8和9整除. 已知 x + y = c, 求c的值
HKMO 2000 - 2001 Final Event (Group)

Note: 係呢度 xy係指1234xy中的十位數同個位數,唔係x乘y

呢條數其實最主要把1234xy寫成 123400 + xy
123400可以被8整除,所以
xy都要被8整除 ... (1)
123400被9除之後,餘數= 1,咁要1234xy被9整除, xy被9除時的餘數要係8先得,所以
xy - 8可以被9 整除 ... (2)

由於8可被8整除,再加埋(1),所以
xy - 8可以被8 整除 ... (3)

從(2)(3), xy - 8係72的倍數
所以 xy = (72) + 8 = 80
x + y = 8

Given that 111111222222 = c(c+1), find the value of c
已知111111222222 = c(c+1), 求c 的值
HKMO(2000 - 2001) Final Event 1 (Group)

明顯 c應該係一個6位數
111111222222 = 111111 x 1000000 + 222222
                      = 111111 (1000002)
所以要將1000002 做分解,但係又要保持111111係6位數,咁即係分解一個得一位數的因子
咁唔洗試好多個, 得2, 3, 6,
做一個簡單checking,得  
111111222222 = 333333 x 333334

跟住呢題,解題所用到的技巧大約係初中程度,但係要個思路好清楚先掂

Let n be an integer greater than 6. Prove that if n − 1 and n + 1 are both prime,
then n^2(n^2 +16) is divisible by 720. Is the converse true?
設 n 是一個大於6的整數. 若 n - 1及 n + 1都質數,證明n^2(n^2 +16)能被720整除.
它的逆命題 (即若 n^2(n^2 +16)能被720整除, n - 1及 n+1是否都是質數)是否成立?
British MO 2005

觀察1: n一定是雙數 (否則 n -1, n +1都是雙數且 n > 6, 當然不是質數 )
觀察2: n 的個位數值只可以是 0, 2 或 8 (同樣是由 n-1, 及 n+1都質數推出)

實驗1:
試試計算n的可能值, 由觀察2, 我們只需要計算 n =10, 12, 18, 20, 22, 28,30,...
再由n - 1及 n + 1都是質數,  n = 12, 18, 30,...

由實驗1,可估計 n = 6m. 現在先要證明這點
Proof:
任何整數n,只可以寫成 6m, 6m+1, 6m+2, 6m+3, 6m+4, 6m+5
從觀察1, n只可以寫成 6m, 6m+2, 6m+4
當 n = 6m+2, n+1 = 6m+2+1 =3(2m +1) ,即不是質數
當 n = 6m+4, n-1 = 6m+4-1 =3(2m +1) ,即不是質數
所以n  = 6m only

繼續代 n = 6m入 n^2(n^2 +16)中,可得
n^2(n^2 +16) = 36m^2 (36m^2 + 16)
                        =144m^2 (9m^2 + 4)
由觀察2, m的個位數值只可以是 0, 5, 2,7,8
所以 m^2的個位數值只可以是 0, 5,4, 9
所以 m^2 或(9m^2 + 4)能被5整除

所以n^2(n^2 +16)能被144 x 5 = 720所整除

至於"若 n^2(n^2 +16)能被720整除, n - 1及 n+1是否都是質數)是否成立?",這個是很容易找到反例的.

[ 本帖最後由 Naozumi 於 2008-11-12 12:24 PM 編輯 ]

Naozumi

另外一種題目就係搵某d數的乘積的個位數,前面d題目都有用過下

求  2004^2006。
Find the unit digit of  2004^2006 .
(HKMO 1999-2000 Heat Event Group)

呢題仲簡單, 4^1 = 4, 4^2 = 16, 4^3 = 64, 4^4 = 256...
好明顯4的單數次方的個位數是4,雙數次方的個位數是6
所以2004^2006的個位數是6

(HKMO 2002-2003 Final Event 1 Individual)

呢題相應黎講容易1d
5的次方都係5字尾,所以慳番唔洗諗

而且 (3^2003) x (7^2001) = (21)^2001 x 9
所以(3^2003) x (7^2001)的個位數係9
所以P = 5

若以5除 7^2007  所得的餘數是 R，求 R 的值。
If the remainder of 7^2007  when dividing by 5 is R, find the value of R.
(HKMO 2006-2007 Heat Event Group)

呢題留番大家度度,應該唔係大問題

[ 本帖最後由 Naozumi 於 2008-11-16 11:32 AM 編輯 ]

AYuMe

了解完以上兩題
雖然理解計算方法 , 但亦相信不能一時之間計出答案-口-

charlesmkh

原帖由 Naozumi 於 2008-11-8 10:53 PM 發表
乜野係數論呢? 好粗略咁講,佢係研究整數的整除性,質數的關係等等. 數論廣泛地用於關乎internet安全的密碼學(cryptography)
呢d野係中學課程近乎冇提過,不過講真唔係難得咁緊要 (當然指係MO/IMO用到的部分內容). 舉個 ...

好變態>"< 但係又好似好好玩咁... (可惜我唔係讀Maths既材料~~)

c443122

7^1 = 7
7^2 = 49
7^3 = 343
7^4 = 2401
7^5 = 16807
.....
7^2007 = 7^(2004+3) = %%@%@%#@$3
so remainder = 3???

Naozumi

yes, u're right

charlesmkh

原帖由 c443122 於 2008-11-18 10:20 PM 發表
7^1 = 7
7^2 = 49
7^3 = 343
7^4 = 2401
7^5 = 16807
.....
7^2007 = 7^(2004+3) = %%@%@%#@$3
so remainder = 3???

超好眼力= =" 諗左幾耐??
我又試~~
7=2(mod5)
7^2=4(mod5)
7^3=3(mod5)
7^4=1(mod5)
7^1024=1(mod5)
7^1536=7^1024*7^512=1(mod5)
7^1792=7^1536*7^256=1(mod5)
7^1920=7^1792*7^128=1(mod5)
7^2007=7^1920*7^64*7^16*7^4*7^3=3(mod5)
Thus, R=3

新學返黎既方法~~ 好似好麻煩咁= ="

[ 本帖最後由 charlesmkh 於 2008-11-20 11:03 PM 編輯 ]

Naozumi

因為你唔用 7^2黎做 9的次方的字尾只有1同9,簡單好多
你再狠d用 7^4黎做,咁只有(7^4)^n = 1 (mod 5)

[ 本帖最後由 Naozumi 於 2008-11-20 11:15 PM 編輯 ]

19960506

我唔係好明白=.= e d野唔岩好~

charlesmkh

原帖由 Naozumi 於 2008-11-20 11:14 PM 發表
因為你唔用 7^2黎做 9的次方的字尾只有1同9,簡單好多
你再狠d用 7^4黎做,咁只有(7^4)^n = 1 (mod 5)

XD 我做到4次都知可以直接做上去~ 畢竟係新學既... 都唔係好知搞乜XD

Naozumi

組合數學 (Combinatorics)係現時中學課程很少討論 (中6 maths and stats有教),呢門數學的其中一個較簡單的分支就係探討一下一組物品的排列的數目,(nCr, nPr etc)
不過334的高中數學將會慢慢討論呢個課程的入門部份

另一個分支則為圖論(Graph theory), 最出名的便是"一筆畫"某圖形的問題, 有機會都可以同大家一齊研究下.

Combinatorics亦係奧數的常客

已知 a、 b、 c 是正整數，且滿足a < b < c = 100，求以 a cm、b cm、c cm 為邊長的三角形的個數。
Given that a, b, c are positive integers and a < b < c = 100, find the number of triangles formed with sides equal a cm, b cm and c cm.
HKMO 1998-1999 Heat Event (Individual)

呢題首先要知道三角不等式 (triangle inequality),即三角形的兩邊之和必定大於第3條邊

由於100係最大,咁 b + 100> a同 a + 100 >b一定o岩
剩番要諗有幾多個a,b符合 a + b > 100

由 a+ b> 100,明顯a同b最少有一個一定大過或等於50

假設 a>= 50,咁 b要由51開始數起
如果a = 50, b = 51,52,53,...,99
如果a = 51, b = 52,52,...,99
....
如果 a = 98, b = 99
咁呢度total有 (49 + 48 +47 + ... + 1) = 1225個

假設 b>= 50及 a <50 (a>=50係上面已經數左)
如果 a = 2, b = 99
如果 a = 3, b = 99, 98
如果 a = 4, b = 99, 98, 97
...
如果 a = 49, b = 99, 98, 97, ...,52
咁呢度total有 (1 + 2 + 3 + ... + 48) = 1176個

所以共有 1225 + 1176 = 2401個

[ 本帖最後由 Naozumi 於 2008-11-30 06:12 PM 編輯 ]

c443122

總覺得..做的時候會很難..看ans 時很易=.=..

Naozumi

同洗錢一樣,洗時好開心好爽手,搵錢時很艱苦

aesopi

我想問一問HKMO2008一D既題目
1.化簡開方(10+開方(24)+開方(40)+開方(60))
2.化簡 3開方(20+14開方(2))+3開方(20-14開方(2))
3.X^(LOG(7底)X^2)=343X     X<1 求X

Naozumi

X^(LOG(7底)X^2)=343X    0< X<1 求X
log(7底) [X^(log(7底)X^2)] = 3 + log(7底) X
(log(7底)X^2) log(7底) X = 3  + log(7底) X
2(log(7底)X)^2 = 3 + log(7底) X
2Y^2 = 3 + Y
(2Y -3)(Y + 1) = 0
Y = -1
X = 1/7