Luận văn Phân số Ai Cập và biểu diễn đơn vị

Nội dung tài liệu: Luận văn Phân số Ai Cập và biểu diễn đơn vị

1. ĐẠI HÅC QUÈC GIA HÀ NËI TRƯỜNG ĐẠI HÅC KHOA HÅC TỰ NHIÊN NGUYỄN THỊ HÇNG NHẬT PHÂN SÈ AI CẬP VÀ BIỂU DIỄN ĐƠN VỊ LUẬN VĂN THẠC SĨ KHOA HÅC HÀ NËI - 2016
2. ĐẠI HÅC QUÈC GIA HÀ NËI TRƯỜNG ĐẠI HÅC KHOA HÅC TỰ NHIÊN NGUYỄN THỊ HÇNG NHẬT PHÂN SÈ AI CẬP VÀ BIỂU DIỄN ĐƠN VỊ 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 Gi¡o vi¶n hướng d¨n: TS NGUYỄN VĂN NGÅC HÀ NËI, 2016
3. Mục lục Mở đầu 1 1 Ph¥n sè Ai Cªp 3 1.1 Giới thi»u v· x¥y dựng thuªt to¡n . . . . . . . . . . . . . . . . . . 3 1.1.1 Phương ph¡p t¡ch . . . . . . . . . . . . . . . . . . . . . . . 4 1.1.2 Thuªt to¡n Fibonaci-Sylvester . . . . . . . . . . . . . . . . 5 1.1.3 Thuªt to¡n Golomb . . . . . . . . . . . . . . . . . . . . . . . 7 1.2 Sè thực hành . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.2.1 Thuªt to¡n nhị ph¥n . . . . . . . . . . . . . . . . . . . . . . 10 1.2.2 Thuªt to¡n Bleicher/Erdo¨s .................. 12 1.2.3 Gi£ thuy¸t cõa Goldbach . . . . . . . . . . . . . . . . . . . 16 1.2.4 Thuªt to¡n Yokota . . . . . . . . . . . . . . . . . . . . . . . 17 1.2.5 Thuªt to¡n Tenenbaum/Yokota . . . . . . . . . . . . . . . . 19 1.2.6 Thuªt to¡n sè thực hành "tèi ưu" . . . . . . . . . . . . . . 20 1.3 C¡c thuªt to¡n kh¡c . . . . . . . . . . . . . . . . . . . . . . . . . . 22 1.3.1 Thuªt to¡n giai thøa . . . . . . . . . . . . . . . . . . . . . . 22 1.3.2 Thuªt to¡n Chuéi Farey . . . . . . . . . . . . . . . . . . . 23 1.3.3 Thuªt to¡n ph¥n sè ti¸p di¹n . . . . . . . . . . . . . . . . . 24 1.3.4 So s¡nh Thuªt to¡n . . . . . . . . . . . . . . . . . . . . . . 24 1.4 Độ dài và chặn m¨u sè . . . . . . . . . . . . . . . . . . . . . . . . . 25 1.4.1 Chặn m¨u sè . . . . . . . . . . . . . . . . . . . . . . . . . . 25 1.4.2 Chặn độ dài . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 1.4.3 Độ dài và chặn m¨u sè . . . . . . . . . . . . . . . . . . . . . 29 1.5 Bài to¡n li¶n quan đến sè cè định . . . . . . . . . . . . . . . . . . 31 1.6 Paul Erd¨osvà c¡c ph¥n sè Ai Cªp . . . . . . . . . . . . . . . . . . 37 1.6.1 Giới thi»u . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 1.6.2 Gi£ thuy¸t cõa Erd¨os-Straus . . . . . . . . . . . . . . . . . 39 2
4. 1.6.3 C¡c ph¥n sè Ai Cªp trù mªt . . . . . . . . . . . . . . . . . 40 1.6.4 Th¶m c¡c bài to¡n tø bài to¡n cũ, mới và k¸t qu£ . . . . . 41 1.6.5 C¥u chuy¶n v· mët gi£ thuy¸t không đúng . . . . . . . . . 46 2 Biºu di¹n đơn vị thành têng cõa c¡c ph¥n sè Ai Cªp 49 2.1 Biºu di¹n đơn vị thành têng cõa c¡c ph¥n sè Ai Cªp với m¨u sè nguy¶n dương đặc bi»t . . . . . . . . . . . . . . . . . . . . . . . . . 49 2.1.1 Giới thi»u . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 2.1.2 Ki¸n thùc chu©n bị . . . . . . . . . . . . . . . . . . . . . . . 51 2.1.3 Chùng minh Định lý 2.1 . . . . . . . . . . . . . . . . . . . . 53 2.2 Biºu di¹n đơn vị thành têng cõa c¡c ph¥n sè đơn vị với c¡c m¨u sèl´.................................... 55 2.2.1 Đặt v§n đ· . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 2.2.2 Chùng minh Định lý 2.2 . . . . . . . . . . . . . . . . . . . . 57 2.2.3 Chùng minh Định lý 2.3 . . . . . . . . . . . . . . . . . . . . 59 K¸t luªn 61 Tài li»u tham kh£o 62 3
5. Mở đầu To¡n học Ai Cªp r§t đặc s­c v· nhi·u mặt. Mët trong nhúng kh½a c¤nh r§t kỳ l¤ cõa To¡n học cê Ai Cªp li¶n quan đến "Ph¥n sè". C¡c nhà To¡n học cê Ai Cªp ch¿ x²t nhúng ph¥n sè mà ta gọi là "Ph¥n sè đơn vị", ph¥n sè có tû sè b¬ng 1 và m¨u sè là c¡c sè nguy¶n dương. T¤i sao l¤i như vªy? Ð thời Ai Cªp cê đại, ký hi»u to¡n học trong h» thªp ph¥n dựa tr¶n cơ sở c¡c ký hi»u b¬ng chú tưñng h¼nh cho méi lũy thøa cõa mười cho đến mët tri»u. Méi k½ hi»u trong sè này có thº được vi¸t đi vi¸t l¤i nhi·u l¦n n¸u c¦n thi¸t để có thº đạt được con sè mong muèn. Do đó, để vi¸t được c¡c sè t¡m mươi hay t¡m tr«m, ký hi»u mười hay mët tr«m s³ được vi¸t t¡m l¦n tương ùng. Bởi vªy phương ph¡p t½nh to¡n cõa họ không thº xû l½ h¦u h¸t c¡c ph¥n sè có tû sè lớn hơn 1, họ đ¢ ph£i vi¸t c¡c ph¥n sè như là têng cõa nhi·u ph¥n sè có tû sè b¬ng 1. C¡c ph¥n sè đơn vị này được vi¸t như là sè nguy¶n với d§u ch§m hay k½ hi»u nào đó ở b¶n tr¶n. Nhưng trong luªn v«n này chúng ta v¨n dùng qui ước thông dụng để vi¸t ph¥n sè. 2 1 1 Để vi¸t ph¥n sè , c¡c nhà To¡n học cê Ai Cªp không thº vi¸t + v¼ theo 5 5 5 quy ước vi¸t c¡c sè lúc đó, ph¥n sè đơn vị ch¿ được thº hi»n mët l¦n. Thay v¼ 1 1 2 1 1 vi¸t + ph¥n sè được vi¸t là + . Trong to¡n học cê Ai Cªp ngoài c¡ch 5 5 5 3 15 dùng ph¥n sè đơn vị, mët sè ph¥n sè thông dụng họ quy ước vi¸t b¬ng mët sè k½ tự đặc bi»t. Trong luªn v«n này li»t k¶ c¡c thuªt to¡n để vi¸t ph¥n sè b¬ng têng c¡c ph¥n sè đơn vị.Tuy nhi¶n méi mët ph¥n sè không có duy nh§t mët biºu di¹n ph¥n sè đơn vị, do đó có sự ph¥n t½ch tèi ưu giúa c¡c thuªt to¡n. Luªn v«n cũng nghi¶n cùu vi»c biºu di¹n c¡c ph¥n sè thành têng c¡c ph¥n sè đơn vị th¶m c¡c điều ki»n cè định, như sè c¡c sè h¤ng, hay m¨u sè lớn nh§t. Ngoài ra luªn v«n cán nghi¶n cùu lời gi£i cõa bài to¡n v· phương tr¼nh Diophantine trong c¡c mët sè trường hñp. Đặc bi»t là biºu di¹n đơn vị thành têng c¡c ph¥n sè đơn vị. Để thực hi»n luªn v«n t¡c gi£ chõ y¸u thu thªp và nghi¶n cùu tø c¡c nguồn 1
6. tài li»u kh¡c nhau, rồi ph¥n t½ch c¡c thuªt to¡n đưa ra v½ dụ minh họa cụ thº. Nhúng tài li»u v· ph¥n sè Ai Cªp b¬ng Ti¸ng Vi»t r§t ½t. Do đó n¸u luªn v«n được thực hi»n thành công th¼ nó cũng là mët tài li»u tham kh£o bê ½ch cho gi¡o vi¶n và học sinh. C§u trúc cõa luªn v«n được chia thành ba ph¦n: ph¦n mở đầu, ph¦n nëi dung và ph¦n k¸t luªn. Nëi dung luªn v«n được chia làm hai chương: Chương 1. Ph¥n sè Ai Cªp. Chương 2. Biºu di¹n đơn vị thành têng c¡c ph¥n sè đơn vị. Trong thời gian thực hi»n luªn v«n, t¡c gi£ đã nhªn được sự hướng d¨n ch¿ b£o tªn t¼nh cõa TS. Nguy¹n V«n Ngọc. Qua đây, t¡c gi£ xin được bày tỏ láng bi¸t ơn s¥u s­c và tr¥n trọng nhúng công lao, sự quan t¥m, động vi¶n và sự tªn t¼nh ch¿ b£o cõa Th¦y. T¡c gi£ ch¥n thành c£m ơn c¡c th¦y, cô khoa To¡n - Cơ - Tin học Trường Đại học Khoa học Tự nhi¶n, ĐHQG hà Nëi đã d¤y b£o tªn t¼nh, c¡c th¦y cô gi¡o trong Ban gi¡m hi»u, Pháng Đào t¤o, V«n pháng 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 đã t¤o mọi điều ki»n tèt nh§t trong suèt thời gian t¡c gi£ học tªp và hoàn thi»n luªn v«n. Hà Nëi ngày 01/12/2016 Học vi¶n Nguy¹n Thị Hồng Nhªt 2
7. Chương 1 Ph¥n sè Ai Cªp 1.1 Giới thi»u v· x¥y dựng thuªt to¡n Mët trong nhúng v§n đề cơ b£n li¶n quan đến ph¥n sè Ai Cªp là sự t¼m ki¸m và x¥y dựng thuªt to¡n-c¡ch để vi¸t b§t kỳ ph¥n sè thành têng cõa c¡c ph¥n sè đơn vị, tùc là nhúng ph¥n sè có tû sè b¬ng 1 và m¨u sè là nhúng sè nguy¶n dương. Qua nhi·u n«m, có nhi·u thuªt to¡n kh¡c nhau đã x¥y dựng cho c¡c mục đích kh¡c nhau, chúng bao gồm tø thu¦n túy lý thuy¸t tới thực hành. Rã ràng là với méi mët ph¥n sè b§t kỳ có nhi·u hơn môt c¡ch mở rëng thành c¡c ph¥n sè Ai Cªp ph¥n bi»t. N¸u a 1 1 = + ··· + b x1 xn th¼ sû dụng h» thùc 1 1 1 = + ; x x + 1 x(x + 1) ta thu đưñc a 1 1 1 1 = + ··· + + + : b x1 xn−1 xn + 1 xn(xn + 1) Người Ai Cªp có thº có hoặc không có mët thuªt to¡n để x¥y dựng mở rëng 2 ph¥n sè. Họ t¤o ra mët b£n mở rëng cõa c¡c sè cho t§t c£ c¡c sè l´ n<100. n Gill đã th£o luªn v· mët sè ti¶u ch½ kh¡c nhau mà người Ai Cªp có thº sû dụng p để t¤o b£ng. Trong b£n luªn v«n này, ta ch¿ quan t¥m đến c¡c ph¥n sè < 1. q V¼ vªy ở b§t cù ché nào chưa được quy định rã ràng th¼ ta coi như trong trường hñp này. Trước khi b­t đầu, ta s³ tóm t­t mët sè c¡c k½ hi»u mà s³ được sû dụng trong b£n Luªn v«n 3
8. K½ hi»u Gi£ sû p 1 1 = + ··· + ; n1 < n2 < ··· < nk: q n1 nk Chúng ta ký hi»u: • D(p; q) = gi¡ trị nhỏ nh§t có thº có cõa nk • D(q) = maxpfD(p; q)j0 < p < qg • L(p; q) = gi¡ trị nhỏ nh§t cõa k • L(q) = maxpfL(p; q)j0 < p < qg • O(f(n)) = vô cùng lớn cõa cõa f(n) khi n ! 1 • o(f(n)) = vô cùng b² cõa f(n) khi n ! 1: • f(x)  g(x): f(x) r§t nhỏ so với g(x). • f(s; x) s g(s; x): f(s,x) r§t nhỏ so với g(s,x) theo bi¸n s. Để thuªn ti»n ta cũng s³ x¡c định: • Pi = Sè nguy¶n tè thù i, trong đó P1 = 2(P2 = 3;P3 = 5; ··· ) Q • k = P1:P2 :::Pk • S = fP 2kjk ≥ 0 và P là sè nguy¶n tèg • si = ph¦n tû nhỏ nh§t thù i cõa S 1.1.1 Phương ph¡p t¡ch Có l³ thuªt to¡n thông dụng nh§t cho vi»c t¤o ra mët mở rëng cõa ph¥n sè đơn vị là phương ph¡p t¡ch. Nó dựa vào vi»c sû dụng lặp đi lặp l¤i cõa h» thùc 1 1 1 = + x x + 1 x(x + 1) mà nó được gọi là " h» thùc t¡ch". p Cho ph¥n sè húu tỷ < 1: q p 1 Bước1. Vi¸t b¬ng têng cõa ph¥n sè đơn vị q q 4
9. 1 Bước 2. N¸u có hai ph¥n sè gièng nhau trong khai triºn (với méi sè nguy¶n a 1 a), giú l¤i mët trong sè chúng và thay c¡c ph¥n sè kh¡c b¬ng c¡ch sû a dụng " h» thùc t¡ch". Bước 3. Lặp l¤i bước 2 cho đến khi đạt được khai triºn mà không có hai ph¥n sè có m¨u gièng nhau. 3 V½ dụ 1.1. 7 3 1 1 1 = + + 7 7 7 7 1 1 1  1 1  = + + + + 7 8 56 8 56 1 1 1 1 1 = + + + + 7 8 8 56 56 1 1 1 1  1  1 1  = + + + + + + 7 8 9 72 56 57 3192 1 1 1 1 1 1 = + + + + + : 7 8 9 56 72 3192 1.1.2 Thuªt to¡n Fibonaci-Sylvester Mët thuªt to¡n húu ½ch và trực quan hơn nhi·u là thuªt to¡n Fibonaci - Sylvester. Nó l¦n đầu ti¶n được t¼m th§y bởi Fibonaci vào n«m 1202 và sau đó là bởi Sylvester. Thuªt to¡n như sau p Cho ph¥n sè tèi gi£n < 1: q Bước 1. K½ hi»u p0 = p và q0 = q: p0 Bước 2. N¸u p0 = 1; đặt là mët ph¦n cõa mở rëng, và ta đã làm xong. N¸u q0 không th¼ sû dụng thuªt to¡n chia ta thu được q0 = sp0 + r, trong đó r < p0: p0 1 p0 − r 1 Bước 3. Chú ý r¬ng = + : V¼ vªy là mët ph¦n cõa khai q0 s + 1 q0 (s + 1) s + 1 triºn. Bước 4. Đặt p0 = p0 − r và q0 = q0 (s + 1) : p0 Bước 5. Rút gọn ph¥n sè v· ph¥n sè tèi gi£n và quay l¤i bước 2. q0 5
10. V½ dụ 1.2. 3 1 2 = + 7 3 21 1 1 1 = + + : 3 11 231 Gi£i th½ch. Ð đây p0 = p = 3; q0 = q = 7: Ta có 3 1 p0 − r 1 2 7 = 2:3 + 1; s = 2; r = 1; = + = + : 7 s + 1 q0 (s + 1) 3 21 Ti¸p theo, ta có p0 = 2; q0 = 21: Ta có 2 1 p0 − r 1 1 21 = 10:2 + 1; s = 10; r = 1; = + = + : 21 s + 1 q0 (s + 1) 11 231 Với ph¥n sè cuèi cùng p0 = 1; ta døng qu¡ tr¼nh. Vªy, ta có 3 1 1 1 = + + : 7 3 11 231 Định lý 1.1. Ứng với méi thuªt to¡n Fibonaci - Sylvester có mët khai triºn có không qu¡ p sè h¤ng. Chùng minh . Thuªt to¡n đưa ra p0 1 p0 − r = + : q0 s + 1 q0 (s + 1) Thực t¸, ta bi¸t r¬ng thuªt to¡n t¤o ra h¦u h¸t p sè h¤ng bởi v¼ tû sè luôn nhỏ hơn. Cụ thº: p0 Khi là tèi gi£n, ta bi¸t r¬ng r > 0: q0 Ð bước 4, ta có p0 = p0 − r, v¼ vªy p0 mới ≥ p0 cũ − 1: Ð bước 2, ta døng l¤i n¸u p0 = 1, v¼ vªy ở đây có thº có h¦u h¸t p sè h¤ng. Mặc dù, trường hñp x§u nh§t mà méi l¦n r = 1; và k¸t qu£ ph¥n sè là luôn luôn tèi gi£n. Khi đó khai triºn ch­c ch­n t¤o ra p sè h¤ng. Tr¶n thực t¸, trường hñp x§u nh§t thường hi¸m khi x£y ra. Mặt kh¡c, v§n đề đặt ra đối với phương ph¡p này là m¨u sè t¤o ra có thº r§t lớn. V½ dụ, thuªt 5 to¡n Fibonaci-Sylvester mở rëng là: 121 5 1 1 1 1 1 = + + + + : 121 25 757 763309 873960180912 1527612795642093418846225 6