Luận văn Một số bài toán số học - Tổ hợp

Nội dung tài liệu: Luận văn Một số bài toán số học - Tổ hợp

1. ĐẠI HÅC QUÈC GIA HÀ NËI TRƯỜNG ĐẠI HÅC KHOA HÅC TỰ NHIÊN ------------------ Tr¦n Thanh Nh¢ MËT SÈ BÀI TOÁN SÈ HÅC - TÊ HỢP LUẬN VĂN THẠC SĨ KHOA HÅC Chuy¶n ngành: PHƯƠNG PHÁP TOÁN SƠ CẤP M¢ sè: 60.46.01.13 Người hướng d¨n khoa học GS. TSKH. HÀ HUY KHOÁI HÀ NËI, NĂM 2013
2. 1 Mục lục Lời mở đầu 3 Lời c£m ơn 5 1 Mët sè ki¸n thùc chu©n bị 6 1.1 Ki¸n thùc tê hñp . . . . . . . . . . . . . . . . . . . . . . . . . . . . .6 1.1.1 Quy t­c cëng . . . . . . . . . . . . . . . . . . . . . . . . . . .6 1.1.2 Quy t­c nh¥n . . . . . . . . . . . . . . . . . . . . . . . . . . .6 1.1.3 Ho¡n vị . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .7 1.1.4 Ch¿nh hñp . . . . . . . . . . . . . . . . . . . . . . . . . . . . .7 1.1.5 Tê hñp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .8 1.1.6 Nguy¶n lý bù trø . . . . . . . . . . . . . . . . . . . . . . . . .8 1.1.7 Nguy¶n lý Dirichlet . . . . . . . . . . . . . . . . . . . . . . . .8 1.1.8 Khai triºn nhị thùc Newton . . . . . . . . . . . . . . . . . . .8 1.2 Ki¸n thùc sè học . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .9 1.2.1 T½nh chia h¸t . . . . . . . . . . . . . . . . . . . . . . . . . . .9 1.2.2 Biºu di¹n cơ sè . . . . . . . . . . . . . . . . . . . . . . . . . .9 1.2.3 Sè nguy¶n tè . . . . . . . . . . . . . . . . . . . . . . . . . . . .9 1.2.4 Ước chung lớn nh§t, bëi chung nhỏ nh§t . . . . . . . . . . .9 1.2.5 Thuªt to¡n Euclid . . . . . . . . . . . . . . . . . . . . . . . . 11 1.2.6 Đồng dư . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.2.7 Đồng dư tuy¸n t½nh . . . . . . . . . . . . . . . . . . . . . . . . 12 1.2.8 Thặng dư . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 1.2.9 Mët sè định lý quan trọng . . . . . . . . . . . . . . . . . . . . 13 2 Mët sè bài to¡n Sè học - Tê hñp 14 2.1 T½nh ch§t sè học . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.1.1 T½nh chia h¸t . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.1.2 Biºu di¹n sè . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 2.1.3 Thuªt to¡n Euclid và mët sè bài to¡n li¶n quan đến ước chung lớn nh§t . . . . . . . . . . . . . . . . . . . . . . . . . . 37 2.2 Bài to¡n chia kẹo Euler. . . . . . . . . . . . . . . . . . . . . . . . . . 47 2.3 B§t bi¸n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 2.4 Cực trị tr¶n tªp hñp rời r¤c . . . . . . . . . . . . . . . . . . . . . . . 61 2.5 Sè phùc - Tê hñp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
3. 2 3 Mët sè bài to¡n trá chơi 86 K¸t luªn ..................................... 96 Tài li»u tham kh£o .............................. 97
4. 3 Lời mở đầu To¡n rời r¤c đóng mët vai trá quan trọng trong to¡n học bởi v¼ nó có nëi dung r§t phong phú và có nhi·u ùng dụng trong đời sèng và thực ti¹n. Trong c¡c k¼ thi đ¤i học, thi học sinh giỏi quèc gia, quèc t¸, c¡c bài to¡n tê hñp xu§t hi»n nhi·u và thường có nëi dung r§t khó. Nh¼n chung, n¸u như vi»c ph¥n lo¤i bài to¡n nào là sè học, đại sè, gi£i t½ch, h¼nh học là tương đối rã ràng th¼ vi»c ph¥n lo¤i c¡c bài to¡n tê hñp kh¡ mơ hồ. Ch½nh v¼ sự đa d¤ng này n¶n vi»c gi£ng d¤y và học tªp chúng là mët v§n đề khó kh«n. Hơn núa, trong chương tr¼nh to¡n phê thông, tài li»u tham kh£o v· lĩnh vực tê hñp r§t ½t, n¶n luªn v«n này nh¬m góp mët ph¦n ki¸n thùc nhỏ b² để hê trñ cho vi»c học tªp và gi£ng d¤y, và bê sung th¶m tài li»u tham kh£o v· tê hñp. Luªn v«n nh¬m mục ti¶u giới thi»u mët sè bài to¡n có thº gọi thuëc lo¤i "sè học - tê hñp". Thực ra không có mët "định nghĩa" nào cho lo¤i bài to¡n này. N¶n luªn v«n này ch¿ giới h¤n ở vi»c đưa ra mët sè bài to¡n thường gặp trong c¡c k¼ thi học sinh giỏi, mà vi»c gi£i chúng đòi hỏi nhúng phương ph¡p cõa sè học và tê hñp. Bè cục luªn v«n được chia thành ba chương: Chương 1 : Mët sè ki¸n thùc chu©n bị Trong chương này, chúng tôi tr¼nh bày mët sè ki¸n thùc cơ b£n v· sè học (t½nh chia h¸t, biºu di¹n sè, sè nguy¶n tè, bëi chung nhỏ nh§t, ước chung lớn nh§t, đồng dư, thặng dư, mët sè định lý quan trọng bao gồm: định lý Wilson, định lý Fermat, định lý ph¦n dư Trung Hoa) và mët sè ki¸n thùc cơ b£n v· tê hñp (quy t­c cëng, quy t­c nh¥n, ho¡n vị, ch¿nh hñp, tê hñp, nguy¶n lý bù trø, nguy¶n lý Dirichlet, khai triºn nhị thùc Newton). Chương 2 : Mët sè bài to¡n Sè học - Tê hñp Mục đích cõa chương này tr¼nh bày mët sè bài to¡n thuëc lo¤i "sè học - tê hñp" theo chõ đề (t½nh ch§t sè học , bài to¡n chia kẹo Euler, b§t bi¸n, cực trị tr¶n tªp hñp rời r¤c và sè phùc), đồng thời trong méi bài to¡n chúng tôi cè g­ng ph¥n t½ch để ti¸p cªn lời gi£i và có b¼nh luªn. Chương 3: Mët sè bài to¡n trá chơi
5. 4 Trong chương cuèi cùng, chúng tôi giới thi»u mët sè bài to¡n trá chơi và đặc bi»t là ùng dụng cõa "t¿ sè vàng" trong lời gi£i cõa bài to¡n trá chơi. Mặc dù b£n th¥n đã cè g­ng nhi·u trong qu¡ tr¼nh thực hi»n, nhưng do thời gian có h¤n và ki¸n thùc b£n th¥n cán h¤n ch¸ n¶n luªn v«n không tr¡nh khỏi nhúng thi¸u sót. R§t mong nhªn được sự ch¿ b£o cõa quý th¦y cô và c¡c b¤n.
6. 5 Lời c£m ơn Luªn v«n này được hoàn thành dưới sự hướng d¨n nghi¶m kh­c và ch¿ b£o tªn t¼nh cõa GS. TSKH Hà Huy Kho¡i. Th¦y đã dành nhi·u thời gian hướng d¨n cũng như gi£i đáp c¡c th­c m­c cõa tôi trong suèt qu¡ tr¼nh làm luªn v«n. Tôi muèn bày tỏ láng bi¸t ơn s¥u s­c đến người th¦y cõa m¼nh. Qua đây, tôi xin gûi tới c¡c th¦y cô Khoa To¡n - Cơ - Tin học, Trường Đại học Khoa học Tự nhi¶n, Đại học Quèc gia Hà Nëi, cũng như c¡c th¦y cô đã tham gia gi£ng d¤y khóa cao học 2011 − 2013 lời c£m ơn s¥u s­c nh§t đối với công lao d¤y dé trong suèt qu¡ tr¼nh gi¡o dục đào t¤o t¤i Nhà trường. Tôi xin được gûi lời c£m ơn ch¥n thành tới gia đình, ban gi¡m hi»u và tªp thº gi¡o vi¶n trường THPT chuy¶n L¶ Quý Đôn t¿nh B¼nh định đã quan t¥m, t¤o điều ki»n và động vi¶n cê vũ tôi để tôi có thº hoàn thành nhi»m vụ cõa m¼nh. Hà nëi, th¡ng 11 n«m 2013
7. 6 Chương 1 Mët sè ki¸n thùc chu©n bị 1.1 Ki¸n thùc tê hñp 1.1.1 Quy t­c cëng Nëi dung quy t­c: N¸u có m1 c¡ch chọn đối tượng a1, m2 c¡ch chọn đối tượng a2,. . . , mn c¡ch chọn đối tượng an, trong đó c¡ch chọn đối tượng ai (1 ≤ i ≤ n) không phụ thuëc vào b§t k¼ c¡ch chọn đèi tượng aj nào n P (1 ≤ j ≤ n; i 6= j) th¼ s³ có mi c¡ch chọn đối tượng a1, hoặc a2,. . . , hoặc i=1 an. Để sû dụng tèt quy t­c này ta chuyºn sang ngôn ngú tªp hñp như sau: X²t fA1;A2; :::; Ang là mët họ c¡c tªp hñp con húu h¤n cu£ tªp A sao cho hai tªp b§t k¼ không có ph¦n tû chung, hñp cõa t§t c£ c¡c tªp con là A, n S A = Ai. Khi đó, ta có i=1 n X jAj = jA1j + jA2j + ::: + jAnj = jAij: i=1 1.1.2 Quy t­c nh¥n Nëi dung quy t­c: Cho n đối tượng a1; a2; :::; an, n¸u có m1 c¡ch chọn đối tượng a1 và với méi c¡ch chọn a1 có m2 c¡ch chọn đối tượng a2, sau đó với méi c¡ch chọn a1; a2 có m3 c¡ch chọn đối tượng a3, ... cuèi cùng với méi c¡ch chọn a1; a2; :::; an−1 có mn c¡ch chọn đối tượng an. Như vªy s³ có m1:m2:::mn c¡ch chọn đối tượng a1, rồi a2,..., rồi an: Tương tự như quy t­c cëng, ta s³ chuyºn sang ngôn ngú tªp hñp như sau: Gi£ sû có n tªp hñp Ak (1 ≤ k ≤ n) với jAkj = mk. Khi đó, sè c¡ch chọn bë
8. 7 gồm n ph¦n tû (a1; a2; :::; an) với ai 2 Ai (1 ≤ i ≤ n) s³ là n Y jA1 × A2 × ::: × Anj = m1 × m2 × ::: × mn = mk: k=1 1.1.3 Ho¡n vị Định nghĩa 1.1. (Ho¡n vị không lặp) Gi£ sû A là tªp hñp húu h¤n gồm n ph¦n tû. Mët c¡ch s­p x¸p n ph¦n tû kh¡c nhau cõa tªp A theo mët thù tự nào đó được gọi là mët ho¡n vị không lặp cõa c¡c ph¦n tû trong tªp A, hay đơn gi£n là sự s­p x¸p n ph¦n tû cõa tªp A. Khi đó, sè ho¡n vị không lặp cõa n ph¦n tû k½ hi»u Pn và t½nh theo công thùc Pn = n (n − 1) :::1 = n!: Định nghĩa 1.2. (Ho¡n vị có lặp) Ho¡n vị trong đó méi ph¦n tû xu§t hi»n ½t nh§t mët l¦n được gọi là ho¡n vị có lặp. K½ hi»u P (n1; n2; :::; nk) là sè ho¡n vị có lặp cõa n ph¦n tû gồm k lo¤i, mà c¡c ph¦n tû lo¤i i (1 ≤ i ≤ k) xu§t hi»n ni l¦n và được t½nh theo công thùc n! P (n1; n2; :::; nk) = : n1!n2!:::nk! 1.1.4 Ch¿nh hñp Định nghĩa 1.3. (Ch¿nh hñp không lặp) Cho tªp hñp A gồm n ph¦n tû. Méi bë gồm k (0 ≤ k ≤ n) ph¦n tû được s­p thù tự cõa tªp A được gọi là mët ch¿nh hñp không lặp chªp k cõa n ph¦n tû thuëc A. k K½ hi»u sè ch¿nh hñp không lặp chªp k cõa n là An, t½nh bởi công thùc n! Ak = : n (n − k)! Định nghĩa 1.4. (Ch¿nh hñp có lặp) Cho tªp hñp X gồm n ph¦n tû. Méi d¢y có độ dài k ph¦n tû cõa tªp X, mà méi ph¦n tû có thº lặp l¤i nhi·u l¦n và được s­p theo mët thù tự nh§t định được gọi là mët ch¿nh hñp có lặp chªp k cõa n ph¦n tû thuëc tªp X. k K½ hi»u sè ch¿nh hñp có lặp chªp k cõa n là An, t½nh bởi công thùc k k An = n :
9. 8 1.1.5 Tê hñp Định nghĩa 1.5. (Tê hñp không lặp) Cho tªp hñp A gồm n ph¦n tû. Méi tªp con gồm k (0 ≤ k ≤ n ) ph¦n tû cõa tªp A được gọi là mët tê hñp không lặp chªp k cõa n ph¦n tû thuëc A. k K½ hi»u sè tê hñp không lặp chªp k cõa n là Cn, t½nh bởi công thùc n! Ck = : n k!(n − k)! Định nghĩa 1.6. (Tê hñp có lặp) Cho tªp A = fa1; a2; :::; ang. Mët tê hñp có lặp chªp m (m không nh§t thi¸t ph£i nhỏ hơn n) cõa n ph¦n tû thuëc A là mët bë gồm m ph¦n tû, mà méi ph¦n tû này là mët trong nhúng ph¦n tû cõa A. m K½ hi»u sè tê hñp có lặp chªp m cõa n là Cn , t½nh bởi công thùc m m Cn = Cn+m−1: 1.1.6 Nguy¶n lý bù trø Gi£ sû M1;M2; :::; Mn là c¡c tªp hñp húu h¤n. Khi đó ta có công thùc têng qu¡t sau đây: n X X jM1 [ M2 [ ::: [ Mnj = jMij − jMi \ Mjj i=1 1≤i<j≤n X n+1 + jMi \ Mj \ Mkj − :::: + (−1) jM1 \ M2 \ ::: \ Mnj : 1≤i<j<k≤n 1.1.7 Nguy¶n lý Dirichlet Có n đồ vªt được x¸p vào m ng«n k²o. Khi đó tồn t¤i ½t nh§t mët ng«n n − 1 k²o chùa ½t nh§t + 1 đồ vªt. m 1.1.8 Khai triºn nhị thùc Newton Định lý 1.1. Với sè tự nhi¶n n ≥ 1 ta có n n X k n−k k (x + y) = Cnx y : k=0
10. 9 Định lý 1.2. Với m; n là hai sè nguy¶n dương, ta có n X n1 n2 nm (x1 + x2 + ::: + xm) = P (n1; n2; :::; nm) x1 x2 :::xm : n1;n2;:::;nm≥0 n1+n2+:::+nm=n 1.2 Ki¸n thùc sè học 1.2.1 T½nh chia h¸t N¸u a; b là hai sè nguy¶n và b 6= 0 th¼ tồn t¤i duy nh§t hai sè nguy¶n q; r; 0 ≤ r ≤ jbj − 1 sao cho a = bq + r: 1.2.2 Biºu di¹n cơ sè Với b 2 Z; b > 1 th¼ với mọi n 2 Z+ luôn tồn t¤i biºu di¹n duy nh§t k k−1 n = akb + ak−1b + ::: + a1b + a0; trong đó a0; a1; :::; ak 2 Z; 0 ≤ ai ≤ b − 1; ak 6= 0: K½ hi»u n = (akak−1:::a1a0)b: 1.2.3 Sè nguy¶n tè Định nghĩa 1.7. Sè nguy¶n p > 1 gọi là sè nguy¶n tè n¸u nó ch¿ có hai ước nguy¶n dương 1; p. Định lý 1.3. (Định lý cơ b£n cõa sè học) Mọi sè nguy¶n n > 1 đều có biºu di¹n duy nh§t dưới d¤ng t½ch c¡c sè nguy¶n tè (không kº thù tự), tùc là α1 α2 αk n = p1 p2 :::pk ; trong đó αi 2 Z+; p1 < p2 < ::: < pk là c¡c sè nguy¶n tè. Định lý 1.4. Tªp hñp c¡c sè nguy¶n tè là vô h¤n. 1.2.4 Ước chung lớn nh§t, bëi chung nhỏ nh§t Định nghĩa 1.8. Cho n > 1 sè nguy¶n không đồng thời b¬ng không a1; a2; :::; an. Sè nguy¶n dương d lớn nh§t có t½nh ch§t d chia h¸t ai; i = 1; 2; :::; n được gọi là ước chung lớn nh§t cõa n sè a1; a2; :::; an. K½ hi»u ƯCLN(a1; a2; :::; an) hay (a1; a2; :::; an).