Tài liệu Bồi dưỡng học sinh giỏi toán tổ hợp rời rạc -nguyễn văn thông

  • Số trang: 137 |
  • Loại file: PDF |
  • Lượt xem: 540 |
  • Lượt tải: 2
dangvantuan

Tham gia: 02/08/2015

Mô tả:

Bồi dưỡng học sinh giỏi toán tổ hợp rời rạc -nguyễn văn thông
'^d gido iCu til - Thqc si Todn hoc - Gido vien chuyen Le Quy Don N G U Y I N VAN THONG TOAN Ti llfP; 111 MC I Danh cho hpc sinh chuyen D M NAII I Toan-„^in^ NHA XUAT BAN DAI HOC QUOC GIA HA NQI Cty TNHH MTV DWH Khang Viet mii Maddu XURT BAN Dfll HOC QUOC Glfl Hl^ NOI 16 Hang Chuoi - Hai Ba TrUng - Ha Npi Dien t h o a i : Bien tap - Che ban: (04) 39714896; Hanh chinh: (04) 39714899: Tona bien tap: (04) 39714897 Fax: (04) 39714899 Tu duy ve toan roi rac ra doi rat som. O Trung Quo'c, vao thoi nha Chu nguai ta da biet den nhimg hinh vuong than bi. Nha toan hpc Pithagore va cac hoc tro cua ong da phat hien ra nhieu tinh chat ky la ciia cac so. M o t ket qua noi tieng cua cac truong phai nay la ke't qua ma ngay nay chiing ta goi la dinh l i Pithagore. Tuy nhien c6 the noi rang ly Chiu trdch nhi^m xuat ban Gidmdoc- Tong bien tap : thuyet toan roi rac duoc hinh thanh nhu mpt nganh toan hoc chi vao khoang the ky XVII bang mgt loat cong trinh nghien cmi nghiem tiic cua cac nha toan TS. P H A M T H j T R A M hoc xuat sac n h u Pascal, Fermat, Leibnitz, Euler... Chiing ta nho lai hai bai toan noi tieng trong toan roi rac sau: Bi^n tap N G Q C LAM CM ban C O N G TY KHANG V I E T Trinh bay bia <6di toan 1: pi n B C O N G TY KHANG VIET Tong phdt hanh vd doi tdc lien ket xuat ban: CONG TY TNHH MTV D|CH Vg VAN H 6 A KHANG VIET - EULER va bai toan bay cau 6 KONIGSBERG 6 thanh pho KONIGSBERG (LITHUANIA) c6 7 cay cau bac ngang con /^Dia chl 71 Dinh Tien Hoang - P Da Kao - Q 1 - TP HCM Dien thoai- 08. 39115694 - 39105797 - 39111969 - 39111968 Fax; 08. 3911 0880 Email: khangvletbookstore®yahoo.com.vn Website: www.nhasachkhangviet.vn song pregel n h u hinh ve tren: Nguai ta dat ra cau do. ^ Tim each di qua tat ca bky cay cau nay, moi cai diing mpt Ian roi quay ve diem xuat phat. Nam 1736 Leonahard Euler (1707 SACH L I E N K E T - 1783) da chung minh khong the c6 BOI DlfONG HQC SINN GIOI TOAN TO HQP - R6I RAC mpt duong d i nao nhu the bang lap M a so: 1 L - 2 9 7 D H 2 0 1 2 In 2 . 0 0 0 c u o n , k h d 1 6 x 2 4 c m T a i : Cty T N H H M T V IN A N MAI T H j N H DLfC Dja c h l : 7 1 , Kha V g n C a n , P. H i e p Binh C h a n h , Q . Thu Diifc, TP. H o Chi M i n h So xuat b 5 n : 1 2 0 4 - 2 0 1 2 / C X B / 0 7 - 1 9 4 / D H Q G H N ngay 0 9 / 1 0 / 2 0 1 2 . Quyet d j n h xuat bkn so: 2 9 2 L K - T N / Q D - N X B D H Q G H N , cap ng^y 09/10/2012 In xong n o p \\Ju c h i e u quy IV nSm 2 0 1 2 'uan sau: i^.u, • Bieu dien bon mien dat A, B, C, D bang bon diem trong mat phang, moi cau noi hai mien duoc bieu dien bang nipt doan noi hai diem tuong ung ta se CO do thi sau: Cty TNHH MTV Boi dudng hqc sink gioi Toan tohgrp - red rac, Nguyen Van Thong Bay gio, m p t d i r a n g d i qua bay cay cau, m o i cai d u n g m p t Ian r o i quay ve d i e m xua't p h a t se c6 so' Ian d i den A bang so' Ian r o i k h o i A , nghia la p h a i sit d u n g den m p t so chan cay cau n o i v o i A . V i so cau n o i v o i A la 5 (le) nen DWH Khang Vi^l p6, to h o p va l y t h u y e t d o t h i lien q u a n chat che v o i n h a u , k h i d o bp m o n Toanj r d i rac bat d a u p h a t t r i e n m a n h me. - ' " • T r o n g t r u o n g p h o t h o n g cua Vi?t N a m , hi?n nay bp m o n nay chua thuc k h o n g CO d u o n g d i nao thoa m a n d i e u k i e n bai toan. Y t u o n g tren cua Euler da svf d u p e ehii t r p n g va q u a n tarn, chua c6 h u o n g n g h i e n c u u de d u a toan r o i rac k h a i sinh n g a n h toan hpc c6 n h i e u ap d u n g d o la l i t h u y e t d o t h i . vao giang day t r o n g t r u o n g p h o t h o n g cho eo ke't qua. N h a t la d o i v o i cac lop ^di toan2: Bai toan b o h m a u . - >5,., ... •f>:v,i ;:;firr, y j l ^ i i ^ Tren m p t ban d o bat k i , ta n o i no d u p e to m a u , neu m o i m i e n ciia n o d u p e to m p t m a u xac d i n h sao cho hai m i e n ke n h a u c6 m a u sac khac n h a u . Van de can d u n g t o i t h i e u bao n h i e u m a u de to m p t ban d o bat k i . Bai toan da d u p e dat ra k h o a n g g i u a the k i XIX. M o h i n h toan hpc cua bai toan nay n h u sau: V o i m o i ban d o M cho trude, ta hay xay d u n g m p t d o t h i G t u o n g u n g , m o i m i e n cua M u n g v o i m p t d i n h cua G, 2 m i e n ciia M c6 c h u n g m o t p h a n bien neu va chi neu 2 d i n h t u o n g u n g t r o n g G c6 canh n o i . De thay do t h i G n h a n d u p e theo each tren la m p t d o t h i phang n h u the bai toan to m a u M t r o t h a n h bai toan to m a u G . N g a y tir k h i m o i xua't hien bai toan n g u o i ta dat gia thie't bai chuyen Toan ehuyen T i n , n h i m g l o p p h o t h o n g chuyen can b o i d u o n g Toan r o i rac de cac e m vao d a i hpc, hpc bp m o n nay tot h o n . - N g a y t r o n g cac k y t h i HSG quoe te^ hpc sinh Vi?t N a m ehiing ta t h u o n g khong thanh cong v o i cac bai toan To h p p , to m a u , do t h j . T r o n g t i n h h i n h toan hpc ngay cang phat trien, t h i su ke't h p p g i i i a cac ITnh v u c toan hpc v o i nhau ngay cang cao va sau sac, d o i h o i n g u o i l a m toan t u o n g lai p h a i biet n o i ke't v o i cac bp m o n lai v o i nhau m o i dat ke't qua m o n g m u o n , m a bp m o n toan r o i rac pho t h o n g la buoe d a u can thie't. V o i t u d u y sau sac, m a n h me, n o se la vien gach dau tien cho hpc sinh p h o thong ren l u y e n buoe d a u d i vao nghanh toan hpc va mpt t r o n g so hp se t r o thanh nha toan hpc ehuyen n g h i f p t u o n g lai. - D a y la ke't qua t h i O l y m p i c toan quoe t e c u a doan hpc s i n h V i ? t N a m Ian t h i i 46 tai M e x i c o n a m hpc 2005 (trich t u toan hpc va t u o i tre so 8/2005). toan la 4. T u y n h i e n , k h o n g eo m p t c h u n g m i n h nao d i i n g cho gia thie't nay d u p e dat ra. C h o den n a m 1976 m p t n h o m cac nha khoa hpc ( K . A p p e l , SBD^\ BAIl BAI 2 BAI 3 BAI 4 BAI 5 BAI 6 W . H a k e n , J.Kock) da xay d t m g m p t l o i giai d u a tren cac ke't qua d o m a y t i n h VNl 5 7 0 7 7 4 I B M 360 c u n g cap (mat h a n g n g a n g i o tren m a y t i n h ) da k h a n g d i n h gia t h u y e t VN2 0 1 7 2 7 2 VN3 0 7 0 1 7 0 VN4 1 1 6 1 7 0 VN5 7 7 6 2 7 2 VN6 7 7 7 2 7 2 E 20 30 26 15 42 10 4 m a u la d u n g . - C l i n g v o i s u phat trien, v o i toe d p n h a n h ciia cong nghe t h o n g t i n , l y t h u y e t to h p p v a d o t h i da t r a t h a n h m p t l i n h v y c toan hpc q u a n t r p n g va can thie't cho n h i e u l i n h v u c khoa hpc va u n g d u n g . - Cac hpc sinh, ke ca thay giao v a n eon chua q u a n tarn n h i e u den p h a n nay: l y t h u y e t g i , bai tap nao la can thie't cho viee b o i d u o n g H S G Toan, HSG Tin, HSG t r o n g t r u o n g T H P T . - C h u a CO cong t r i n h nao n g h i e n c u u that sau sac va day d i i cho hpc sinh p h o t h o n g ve cac u n g d u n g cua toan hpc r o i rac. - Mac d a u ve m a t lich su, toan r o i rac ra d o i tu hai t r a m n a m t r u d c day t r o n g qua t r i n h giai cac bai toan do, n h u n g bai toan d a n gian. T u lau, n o v a n con d u n g n g o a i le cac p h u o n g h u o n g n g h i e n euu cua cac nha Toan hpc, den nay v i t r i cua no d u p e k h a n g d i n h t r o n g Toan hpc, dac biet la t i n hpc h i e n d a i . m^nh Buoe p h a t t r i e n cua toan r o i rac, da t h u d u p e n h i i n g ke't qua va phat t r i e n vao k h o a n g euoi t h e k i 19 va d a u t h e ' k i 20, k h i m a cac cong t r i n h ve to (Bangl) ^ Bai 6 la bai toan r o i rac t r o n g k y t h i I M O k y 46 tai M e x i c o c6 n p i d u n g sau: T r o n g m p t k y t h i hpc sinh gioi, cae t h i sinh p h a i giai 6 b a i toan. Biet rang hai 2 %. bai toan bat k y l u o n c6 n h i e u h o n - so t h i sinh d u t h i giai d u p e ca hai bai nay. o N g o a i ra k h o n g c6 t h i sinh nao giai d u p e ca 6 bai toan. C h u n g m i n h rang c6 i t nhat 2 t h i sinh sao cho m o i n g u o i t r o n g hp giai d u p e d u n g 5 bai toan. - Bai nay ciia R u m a n i de n g h i . (Doan hpc sinh V i ? t N a m dat ke't qua thap). Boi duanghQc sinh gioi Toan tohgp-rari r^c, Nguyeu //••,; Cty TNHH MTV DWH Day la ket qua ky thi Olympic toan quo'c te cua doan hpc sinh Vi^t Nam Ian thii 47 tai Slovenia nam hpc 2006 (trich t u toan hpc va tuoi tre so'8/2006). Khang Vi?t . Qua qua trinh giang day cac lop chuyen Toan + Tin va ket hpp voi chuong trinh boi duong HSG cua Bp giao due va dao tao toi viet tai lieu nay vdi nhung kinh nghif m ban than ma toi da day cong nghien euu trong suot qua trinh giang day. Trong tai lieu nay, toi eiSng manh dan dua ra mot so khao sat mdi cua minh de tong quat hoa mpt so ket qua da biet. Bail Bai 2 Bai 3 Bai 4 Bai 5 Bai 6 VNl 7 0 1 7 3 0 VN2 7 1 7 6 7 0 T6NGQUAN VN3 7 1 7 7 7 0 Quyeh sach nay se dupe chia lam sau chuong. VN4 7 0 1 6 1 0 Chuong 1: A n h xa va luc lupng ciia cac tap hpp. VN5 7 0 7 7 1 0 Chuong 2: Phep dem, to hpp, chinh hpp va cac mo rpng. VN6 7 4 1 7 0 0 Chuong 3: Trinh bay ve do thi, cac dinh nghia dinh ly can ban thuong dung Z 42 6 24 40 19 0 S B D \ (Bang 2) Bai 2 va Bai 6 la hai bai toan roi rac do nude (Serbia) de nghi. Ket qua ciia doan Viet Nam rat thap trong ky I M O Ian thu 47 to chuc tai Slovenia 2006. Den nay ket qua I M O ciia chiing ta van chua c6 dau hieu tien bo, ma hpc sinh van con lam tot cac bai toan Pi va Ps chuyen ve hinh hoc phang, con bai toan 3, bai toan 6 van con rat yeu, bai toan 3 ve to hop roi rac, bai toan 6 thupc ve so hpc. Chiing ta c6 the quan sat ket qua doan Viet Nam dual day. STT Hp va ten PI P2 P3 P4 P5 P6 :f^K'rWl':,:~::^ly/,r^,.. r i , , X i ;j ; i cho hpc sinh chuyen Toan theo gioi han chuong trinh cua Bp giao due. Chuong 4: Trinh bay ve to mau gom nhung khai niem eo ban, cac dinh ly thuong su dung trong giai Toan pho thong theo gioi han chuong trinh ciia Bp giao due. Chuong 5: Toan to hpp va thi HSG y g / \ Chuong 6; Nguyen ly Dirichlet - Djnh ly Ramsey ^ ,, , - Trinh bay theo quan diem ly thuyet voi nhung chung minh dinh ly, vi du minh hpa, bai tap ap dung, bai tap t u luyen. - Bai tap chpn Ipe t u miic dp trung binh eho den kha, gioi, cac de thi toan Tong Huy diem chuong 1 Nguyen Ta Duy 7 7 0 6 7 0 17 Bac 2 Dau Hai Dang 7 7 3 7 7 0 31 Vang 3 Nguyen Phuong Minh 7 7 0 6 7 0 27 Bac 4 Le Quang Lam 7 7 0 5 0 0 19 Dong 5 Tran Hoang Bao Linh 7 1 0 5 7 0 20 Dong 6 Nguyen Hung Tarn 7 7 1 2 7 0 24 Bac (Bang 3 (Trich Toan hpc va tuoi tre so 8 - 2012)) - Qua nhiing ky thi dinh cao, nhu vay, thi sinh d u thi toan la nhung hpc quoe gia, quo'c te. - Chiing minh nhieu bai toan chia khoa, de nhin nhan van de don gian hon. - Cac dinh ly ve to hpp thuong su dung phuong phap anh xa, phuong phap song anh de chiing minh. - Cac bai toan ve do thi dua vao logic de suy luan va chiing minh eo gang dua ra nhieu bai toan chia khoa de hpc sinh de ap dung va van dung. Day la van de kho nhung tac gia mong muon gop phan minh vao ky nang lam toan roi r^c cho hpc sinh chuyen toan nen khong khoi tranh sai sot. Rat mong gop y ciia cac ban dong nghiep va cac em hpc sinh. .. ,j .,, ^ sinh gioi dupe chpn Ipc ky luong nhung nhin vao ket qua thi ta nhan tha'y. - Hpc sinh Vi?t Nam rat manh ve hinh hpc p h i n g , bat dang thuc, giai tich, phuong trinh ham, nhung toan roi rac van la diem yeu. Do do van de dat ra la Nguyen Van Thong phai CO ly thuyet va bai tap ve toan roi rac de boi duong cho hpc sinh gioi toan pho thong, hpc sinh cac lop chuyen toan, chuyen tin, can boi duong can than va day dii de hpc sinh nam dupe ban chat van de va kha nang ling dung, theo duoi dupe con duong toan hpc sau nay. 6 7 BSi duang hgc sink gidi Toan td'ht^ - rbi rac, Nguyen Van Thdng ^inh nghla 1.3.3. Ta bao m p t anh xa f: X A N H XA, L U CLUCWG C U A C A C T A PH O T X len Y, ne'u no vira la d o n anh vira la toan anh, n o i m p t each khac ne'u v o i m p i y eY §1. A N H X A 1.1.1. • ' >' ^inh ' s » cr-" f: X Anhx? Y v a g: Y -> Z. X->Z '« > • ' '^'f • x-^g(f(x)) 1.2. A N H V A T A O A N H : ^inh nghla 1.4.1. Gia s u cho M p t anh xa f t u X vao Y la m p t q u y tac cho t i r o n g u n g v a i m o i p h a n t u x e X m p t p h a n tvr xac d i n h y e Y, k y hi?u f(x). m p t v a chi m p t x e X sao cho y = f (x) 1.4. TfcH A N H X A . ' •' CO Chang han anh xa d o n g nhat I x la m p t song anh v o i m p i X. I.I.OINHNGHTAANHXA: ^inhnghia Y la m p t song anh hay m p t anh xa m p t do'i m p t t u .^ I'M _ » G p i la tich anh xa f v a anh xa g. K i hieu: g.f nghla 1.2.1. ^inhly Gia s u f: X -> Y la m o t anh xa da cho, x la m o t phan t u t i i y y cua X, A la mQt bp phan t i i y y ciia X, B la m p t b p p h a n t i i y y ciia Y. The t h i n g u o i ta gpi: ' 1 " 1.4.2. Gia s u cho The t h i f: X ^ Y, g: Y, g: Y ^ Z, h: Z ^ T 3'- W ' h(gf) = (hg)f. ^ y'.Ji^iich • • f(x) la anh cua x b o i f hay gia t n ciia anh xa f tai d i e m x. Ta bao phep n h a n cac anh xa c6 t i n h chat ke't h o p . • f ( A ) = { y e Y I t o n tai x e A sao cho f(x) = y ) la anh ciia A b o i f. C h u n g m i n h : Ta CO v o i m p i x e X. • f"^ (B) = { X e X I f(x) 6 B 1 la tao anh toan p h a n cua B b o i f. (h(gf)) (x) = h(gf(x)) = h (gf(x)) = (hg)((f(x)) = ((hg)f){x). Dac biet v o i b e Y, f"^ ({ b }) = { x e X I f(x) = b }. De d o n gian k y h i e u ta viet (b) thay cho f"^ ({ b}) v a g p i la tao anh toan p h a n ciia b b o i f. M o i p h a n t u K y . h i f u £(A) la m o t d i e u l a m d u n g v i f(A) chi c6 nghla k h i A e X. R6 rang ta CO f ( 0 ) = 0 v o i m o i f. Ta c h u n g m i n h de dang cac quan he: • v» • - s:.v, ^.T ,inur- gf = l x v a f g = l y ^inh nghla 1.4.4. A n h xa f: X nghla 1.3.1. A n h xa f: X -> Y la m o t d o n anh ne'u v o i m p i x, x ' e X, quan h ^ f(x) = f(x') f(x'), hay v o i m p i y e Y c6 nhieu nhat m p t x e X sao cho y = f(x). N g u o i ta con g p i m p t d o n anh f: X Y la m p t anh xa m p t d o i mot. nghla 1.3.2. Ta bao m p t anh xa f: X ^ Y la m p t toan anh ne'u f(X) = Y, n o i m p t each khac, ne'u v o i m p i y e Y c6 i t nhat m p t x e X sao cho y = f(x). N g u a i ta con g p i m p t toan anh f: X ^ Y la m p t anh xa t u X len Y. ' D i n h l y sau day cho ta biet k h i nao m p t anh xa c6 anh xa ngirpc. 1.3. D O N A N H - TOAN A N H - S O N G ANH: ^inh 1.4.8. Gia s i i f: X - » Y v a g: Y - » X la hai anh xa sao cho Tir d i n h nghia ta suy ra f cung la m p t anh xa ngupc ciia g. B c f ( r ^ (B)) v o i m p i b p phan B ciia Y. keo theo q u a n h$ x = x', hay x ^ x ' keo theo f(x) C h i i y rang neu f: X -> Y la m p t anh xa bat k y t h i ta c6: fix = l y f = f The t h i g g p i la m p t anh xa ngupc ciia f . A c f"-^ (f(A)) v o i m p i b p phan A ciia X. ^inh • D o d o ta k y h i e u h(gf) = (hg)f bang h g f va g p i la tich ciia ba anh xa f, g, h . 'i>inhnghla x e f"^ (b) g p i la m o t tao anh ciia b b o i f. Y CO m p t anh xa ngupc k h i v a chi k h i f la m p t song anh. Chung mink G i a sii- f c6 m p t anh xa ngupc g: Y -> X Theo d i n h nghia ta c6: gf = I x v a fg = ly Tucla: g(f(x)) = x v o i m p i x. - Xetquanhe: f(x) = f(x') Tasuyra x = g(f(x)) = g(f(x')) = x'. , v , , Vay f la m p t d o n anh. Bay g i o gia s u y la m p t p h a n t u t i i y y ciia Y. D a t x = g(y) e X t r o n g d a n g t h i i c f(g(y)) = y, ta dupe y = f(x). Vay f la m p t toan anh. Dao lai, gia s u f la m p t song anh. Q u y tac cho h r o n g u n g v o i m o i y e Y phan t i i d u y nhat ciia f"^ (y) xac d i n h m p t anh xa g: Y 8 .f X va ta thay ngay 9 Boi duong hQc sink gidi Todn tohipp - rai rac, Nguyen gf = I x Van Thdnjj Cty TNHH va fg = ly g(y) = X, sao cho f(x) = y g 1. H a i tap Y. T h e t h i g = g'. ^ T u do: gf = I x va fg'= ly ' ' i s it; = , ' (y) bang i ; ; ^ (f''^)"^. Vay / I I \ / v a i tap h i i u han). V 1 trong m g t khoang (a, b) bat ky: s u t u a n g l i n g c6 the thuc hien bang Jib Hinh 1 hay cung m g t ban so'. N o i each khac luc l u g n g (hay ban so) ciia m g t tap bieu t h i m o t t i n h chat chung cho no va tat ca cac tap t u o n g d u a n g v a i no. D o i v a i = Ix. tap hijoi han, t h i luc l u g n g (ban so) chinh la so' phan t i i cua no. Thanh t h i i , luc l u g n g (ban so) la k h a i n i e m true tiep m o rgng khai n i e m so' t u nhien. Luc l u g n g ciia m g t tap A t h u a n g d u g c k i hieu I A I (hay cardA). C h u n g m i n h . Ta c6: (g-' / K h i hai tap h g p t u o n g d u o n g nhau, ta bao rang c h i i n g c i i n g m g t luc l u g n g nen f = Ji^ qua Cho hai song anh f: X ^ Y v a g: Y - » Z. The t h i gf: X -> Z la m g t song anh. (gO( I I \ I \ • phep v i t u ( H i n h 1) y ^ f - l (y) CO tu (0,1) t u a n g d u o n g v a i tap cac d i e m (y) va d o d o n g u a i ta k y h i e u anh xa Ta S 3. T a p cac d i e m trong khoang D o l a m d u n g n g u a i ta cung k y hieu phan t u d u y nha't x ciia V i f la anh xa n g u g c ciia t u o n g d u o n g v i c6 't ciia n o (dieu k h o n g the xay ra d o i «. f"^. 2n, (n = l , 2 , 3,...) d u a n g v a i m g t b g phan thuc s u y ^ X , v o l X la p h a n ttr d u y nhalt ciia f"^ (y) la anh xa n g u g c ciia f, bang n, ...} va B = { 2, 4, 6, vay m g t tap v 6 han c6 the t u a n g ' N h u vay neu f: X ^ Y c6 anh xa ngugc t h i anh xa n g u g c la d u y nha't, xac dinhboi. h a n c i i n g so'lugng t h i t u o n g d u o n g . D i e u dang chii y 6 day la B c A: ' g = gly = g(fg') = (gOg' = l^g' = g'- ^ Vi^t the thiet lap phep t u o n g d u o n g l i n g : n<^2n <^inh ly 1.4.5. Gia su g: Y ^ X va g': Y -> X la hai anh xa ngugc ciia f: X c6: hiJTi 2. H a i tap A = { 1, 2, 3, N g o a i anh xa ngugc nay, f con c6 anh xa ngugc nao khac khong? Ta c6: ChicngminhTa Khang Vidu: N h u vay f: X ^ Y c6 m p t anh xa ngugc k h i v a chi k h i f la song anh, va t r o n g t r u a n g h g p do ta c6 m p t anh xa ngugc g: Y X ciia f xac d i n h b o i >i , Y MTV DWH i g-^) = g ( f f - ^ ) g - i = g i y g - i = g g - i = i . )(gf) =rU g"' g)f = r' hi =r'i=ix > ; f-ig-^=(gf)-i N e u m g t tap A t u o n g d u o n g v o i m g t bg phan ciia m g t tap B, n h u n g k h o n g t u o n g d u a n g v a i B, t h i ta noi luc l u g n g ciia A nho h a n luc l u g n g ciia B, hay lye l u g n g ciia B Ion h a n luc l u g n g ciia A va vie't I A I < IBI hay IBI > I A I . M g t v a n de t u nhien nay ra: neu m g t tap A t u o n g d u o n g v a i m g t bo phan ciia tap B va n g u g c lai tap B c i i n g t u o n g d u a n g v a i m o t b g phan ciia A , t h i eo §2. L l J C Ll/ONG CUA CAC TAP HOP the n o i gi ve h a i tap ay? D i n h ly sau day giai dap v a n de nay. 2.1.1. ^inh ly (Cantor- Berntein). N e u tap A t u a n g d u o n g v a i m g t bg phan 2.1. TAP HOP TUONG O JONG: K h i ta d e m Ian l u g t cac phan t u ciia mgt tap A, c6 the xay ra hai t r u a n g hgp: 1. T a i m g t liic nao do, ta d e m d u g c het cac p h a n t i i ciia A . T r o n g t r u o n g h g p nay, tap A la h i i u han v a so cuoi c i i n g d a d e m t a i cho ta biet so l u g n g phantuciiaA. ly, •' .>vi 2. M a i m a i v a n con n h i i n g phan t i i ciia A chua d e m t o i . T r o n g t r u a n g h g p nay, tap A la v 6 han. Ta n o i hai tap h g p A v a B la t u a n g d u o n g (ve so' l u g n g ) neu g i i i a hai tap h g p ay c6 the thiet lap m g t phep t u a n g l i n g 1 - 1 (tiic la c6 the anh xa 1 - 1 tap nay len tap kia). ' ciia tap B v a n g u g c lai tap B c i i n g t u o n g d u o n g v a i m g t bg p h a n ciia tap A t h i hai tap t u a n g d u a n g nhau. N h u vay, neu tap A t u o n g d u o n g v o i m g t bg phan ciia tap B t h i chi c6 the I A I < IBI hoac l A I = IBI (ta vie't l A I < I B I ) . N o i each khac. l A I < I B I , IBI < l A I Chung mink l A I = IBI theo gia thiet c6 m g t phep t u o n g li'ng 1 - 1 f giiia cac p h a n t u ciia A v a i cac phan t u ciia m g t bg p h a n ciia B, va ngugc lai cung c6 Hinh 2 11 BSi duang htfc sink gioi Todn tohgrp - rcri r^c, Nguyen Vin C t y TNHH Thdng M T V DWH Khang Vift mpt p h e p tirong ung 1- 1 g giiia cac p h a n t u cua B vai cac phan t u ciia mpt bp phan ctia A . s'< < ^ii ; ' ; ; Ta qui uoc gpi mpt phan t u x la "ho" cua phan t u y hay y la "con" cua x, neu x e A , y G B v a y = f(x) (y l i n g voi x trong phep tuong ung f) hoac neu xe B, y e A va y = g(x) (y ung vdi x trong phep tuong ung g). Vi du;Theo v i d\ 1 (a myc truoc), t a p |2, 4, 6, 2n, ...} la dem dupe. Ta cung thay ngay rang cac t a p { 3, 6, 9 , 3 n , ...), { 1 , 4, 9 , n ^ , . . . } , v.v ... deu dem dupe; t a p hpp cac so nguyen (bao gom ca so nguyen duong, am, va so khong) C l i n g la dem dupe v i c6 the viet dual dang: 4;,; , 0,1, -1, 2, -2, 3, - 3 , n , - n , . . . Mpt phan t u x (thupc A hay B) gpi la "to tien" ciia mpt phan t u y, neu c6 mpt day XI, X2, XK sao cho x la bo cua xi, xi la bo cua X2, X2 la bo ciia X3, XK la bo ciia y. Chang han trong hinh 2, x la to tien cua y dong thai x ciing la to tien ciia XI, X2, X3; XI la to tien ciia X2, xs; y, v.v... Bay gio ta hay chia A ra lam ba tap con: Ac gom tat ca cac phan t u ciia A c6 mpt sochSn to tien, A i gom tat ca cac phan tu ciia A CO mpt so le to tien va A~. gom tat ca cac phan t u ciia A c6 v6 so' to tien. Dong thoi ta cung theo each do chia B ra lam ba tap: Be, Bi, B~. Sau do ta xac dinh mpt phep tuong ung cp nhu sau giua cac phan t u ciia A voi eae phan t u ciia B: voi moi phan t u thupc Ac hay A - thi cho ung con eiia no, vai moi phan t u thupc A i t h i cho ung bo ciia no. (i r? spi;:; Viec luc lupng dem dupe la lue lupng be nha't eiia cac t a p v6 han dupe xac De thay rang (p la mpt phep tuong ung 1 - 1 giua A va B. That vay, trong phep tuong ung do, voi moi x e A d l nhien ung mpt phan t u duy nhat y e B. Ngupc lai lay mpt phan t u x nao do thupc A i ; neu y e Bi thi bo ciia no thupc Ac, nghia la y la eon ciia mpt phan A i ; neu y e Bi thi bo ciia no thupc Ac, nghia la y la con ciia mpt phan t u x nao do thupc Ac; con neu y e B - thi bo' ciia no thupc Aoo, nghia la y la con ciia mpt phan t u x nao do thupc A - . Thanh t h u moi phan t u y e B ung voi mpt phan t u duy nhat x e A trong phep tuong ling (p. Vay (p la mpt phep tuong l i n g 1-1 giua A va B. Tir dinh ly nay ta suy ra rang cho truoc hai tap A , B, chi c6 the xay ra mpt trong 4 truong hop: •j; 1. lAI = IBI 2. l A I < IBI 3. IBI < l A I • K''^' ->niVx F] Chung minh; That vay, cho M la mpt tap v6 h^n. Ta hay lay mpt phan t u bat ky, ai 6 M , roi mpt phan t u a2 e M \, roi mpt phan t u as e M \, 32), v.v... Vi M v6 h?n, nen dieu do c6 the tie'p tyc mai va ta thu dupe tap dem dupe (ai, a2, as,...} c M. ^inh ly 2.2.2. Mpt bp phan eiia mpt t a p dem dupe thi phai la h i m han hay dem dupe. Chung mink That vay, cho B la mpt bp phan ciia tap dem dupe A = { ai, a2, as,...}. Gpi la phan t u dau tien ciia B ma ta g a p trong day { 8 1 , 8 2 , 8 3 , . . . } , a^^ la phan t u t h u hai ciia B trong day so'do, v.v... Neu trong eae so' 11,12, ••• c6 mpt so Ion nhat, v i du ip, thi B = { , a^^a,^ ] la hihi han. Con neu trai lai day , a i 2 k e o dai v6 tan thi B = ( ,a^^.....} la dem dupe. .XA& • 4. A khong tuong duong voi B, hoac bo phan nao ciia B, va B cung khong la t a p dem dupe. ^* " Chung mink Cho mpt day tap dehi dupe: A i , A2, A3... Ta hay viet eae phan tu eiia moi tap ay thanh mpt day va xep dat cac day thanh mpt bang nhu duoi day. R6 rang tren moi duong cheo (c6 miii ten) chi eo mpt so hiiu han phan tu: tren chung tren duong cheo thii n chi c6 n phan tu (eae apq ma p + q = n +1). Ai A3 2.2. TAP OfM OLTOC Trong tat ea cac tap v6 han thi tap "be nhat" (c6 lue lupng kem nhat) la tap cac so t u nhien: N * = { 1, 2, 3, n,...}. Lue lupng eiia tap nay gpi la lue lupng dem dupe, va mpi tap tuong duong voi no gpi la tap dem dupe. Duong nhien, cung CO the noi: Mpt tap dem dupe la mpt tap ma ta eo the danh so dupe cac phan t u ciia no thanh mpt day v6 han: a i , a 2 , a 3 , a n , . . . ^ ^11 ^ ^12 >^^13 ^332 ^ ^^ ^14 ^23 324 ^33 334 Veiy ta CO the Ian lupt danh so cac phan tu" tren duong eheo thii nhat, roi den duong cheo t h u hai, v.v... ^inh ly 2.2.4. Khi them mpt tap hpp hixu han hay dem dupe vao mot tap v6 hcin ' ' ^inh ly 2.2.3. H p p ciia mpt hp huu han hay dem dupe t a p dem dupe cung tuong duong voi bp phan nao ciia A . 12 ' duong cheo thu nhat chi c6 a n , tren duong eheo thu hai chi c6: 821,812, v.v... noi ^ J"r?>v ^iyjy^ .(;• dinh boi hai dinh l i sau day: ^inh ly 22.1. ^ai cu t a p v6 han nao cung c6 mpt bp phan la t a p dem dupe. M , ta khong lam thay doi luc lupng ciia t^p M . 13 Cty TNHH MTV D W H Khang Viet Boi duang hoc sink gidi Todn tohgrp - rcri r^c, Nguyen Van Thong Chung minh:Cho N la tap thu dugc khi them vao M mQt tap A hiru han hay dem dxxoc. Theo Dinh ly 2.2.1 c6 the lay mot tap dem dugc B cz M . Dat M ' = M\B, ta CO M = M ' u B, N = M ' u B u A. Theo dinh ly truac B u A ciang la dem dugc, cho nen c6 the lap mot phep tuong ung 1-1 giiia B va B u A. Sau do chi can lap mot phep tuong ung 1- 1 giiia M ' va chinh M ' , ta se c6 mot phep tuong ling 1-1 giiia M va N . N h u vay M va N cung luc lugng. Theo dinh ly nay, ta thay rang tap cac diem thugc mot khoang (a, b) tuong duong voi tap cac diem thugc doan [a, b]. Vay tap cac diem thugc doan [a, b] tuong duong voi tap cac diem tren toan duong thang. ^inh ly 2.2.5. Tap tat ca cac day hiiu han c6 the thanh lap dugc voi cac phan t u ciia mot tap dem dugc la dem dugc. Noi ro hon, cho A = day CO dang (a^^, {31,82,33,...} HJ^ , . . . , 3 ; ^ la mot tap dem dugc, S la tap tat ca cac ) trong do m la mgt so' t u nhien bat ky, a^^ (k = 1, 2, m) la nhiing phan t u (khong nhat thiet phan biet) ciia A. Ta khang dinh rang S la dem dugc. Chung mink Ggi Sm la tap cac day gom dung m phan t u ciia A. 2.3. Ll/C LUQNG CONTINUM: Qua cac v i du tren kia, ta da di t u tap cac so' t u nhien den tap cac so' h i m ti, roi den tap cac so dai s6^ moi tap bao gom v6 so phan t u moi so voi cac tap da xet truoc, the ma luc nao ta ciing chi c6 nhiing tap de'm dugc. Vay thi c6 tap nao khong de'm dugc khong? ^inh ly 2.3.1. Tap cac so thuc la khong de'm dugc. Chung mink V i tap cac diem thugc doan [0, 1] tuong duong voi tap cac diem tren toan duong thSng, ta chi can chung minh rang tap cac diem thugc do^n [0,1] la khong dem dugc. Gia sir trai l^i rang tap do de'm dugc, nghla la c6 the danh so' thanh day: Xi,x2,X3,... ta hay chia doan [0, 1] thanh ba doan bang nhau. Trong ba doan do phai CO mgt doan khong chua x^: cho doan ay la . Ta lai chia ra ba doan bang nhau. Trong ba doan do phai c6 mgt doan khong chua X 2 : cho doan ay la A2 . Ta lai chia A 2 ra ba doan bang nhau, v.v. Tie'p tuc mai, ta se c6 mgt day doan Aj A2 3> A3 3 Nen theo Dinh ly 2.2.3 chi can chung minh rang moi Sm la de'm dugc. Voi va voi x^ g A ^ . V i I A „ I - > 0 (n -> °°) nen do la mgt 3 day doan that lai va theo nguyen ly Cantor, phai c6 mgt diem ^ chung cho tat dieu do hien nhien v i rang ca cac dogn ay. Co' nhien ^ e [0, 1]. Vay ^ phai triing voi mgt x^^ nao do. ' ViS=U-.iS„ (hie = A. Ta hay gia thiet dieu do diing voi de'm dugc), va chung minh cho S^^^. (Hj^ ,3(2 , . . . , 3 ; ^ , 3 k ) . Giiia s[^+i va ro rang c6 su tuong ung 1-1. (aii'ai2'aim'3k)<^(aii.ai2'-.ai^) y: I A„ 1= Nhung ^ 6 A „ voi mgi n, cho nen x^^ e A^^ . Dieu nay trai voi each xay dung Cho ak la mgt phan t u xac dinh ciia A, va s|^+i la tap tat ca cac day so c6 dang Voi do dai 3 Ma Sn, da de'm dugc thi SJ^+i cung de'm dugc. Do do S^+i ciing de'm dugc, cac doan A „ . Do do gia thiet rSng tap cac diem thugc [0,1] de'm dugc la v6 ly. Dinh ly tren cho thay rang luc lugng ciia tap so thuc Ion hon luc lugng de'm dugc. Nguoi ta ggi no la luc lugng continum hay luc lugng c. ©mh ly 2.3.2. (Cantor). Cho bat cu tap A nao thi tap tat ca cac bg phan cua A ciing CO luc lugng Ion hon luc lugng cua A. Chung mink Ggi m la tap tat ca cac bg phan cua A. Chang han ne'u A= {a, b, Ji$ qua l : T a p tat ca cac da thuc P(x) = ag + 3 j X + ... + 3 ^ x " (n bat ky) vol cac h^ so ao,3i,...,a„ huu ti, la de'm dugc. That v^y, cac da thuc do hrong ung 1-1 voi cac day so hihi t i (ao,ai,...,an). Vi tap cac so'him t i la de'm dugc nen theo dinh ly tren, tap cac da thuc do ciing de'm dugc. J f | qua 2:Tap cac so dai so la de'm dugc. Mgt so dai so la nghi^m so'ciia mgt da thuc voi r\hung he so'hiiu ti. V i tap cac da thuc nay la de'm dugc, ma moi da thuc chi c6 mgt so' h i i u han nghi^m s6^ nen tap cac so d^i so' chi c6 the la hiru han hay de'm dugc. Nhung no khong the h i m h^n v i no bao ham tap cac so'tu nhien, vay no phai de'm dugc. 14 c} thi M gom c6: 0 , {a}, {b}, {c}, (a, b}, {b, c}, {a, c}, A. Truoc he't ta hay chung minh rang A khong tuong duang voi M . Muo'n the, gia sir trai lai rang A tuong duong voi M , va cho f la phep tuong ung 1-1 giiia hai tap ay. Voi moi phan tir x e A ung mgt phan tir xac dinh cua M ma ta se ky hieu la f ( x ) ; ngugc lai, moi phan tir aia M la f(x) cho mgt phan tir xac dinh x e A. V i f(x) la mgt phan tir cua M , tuc la mgt bg phan cua A nen c6 the xay ra tinh trang x e f(x) . Ta se ggi mgt phan tir x sao cho x e f(x) la "xa'u so". Con ne'u x i f(x) thi x ggi la "tot so". Ggi S la tap tat ca cac phan tir tot so cua A. Vi rang S e M nen S = £(xo) voi mgt XQ e A. Ta thir xem XQ la xa'u so hay tot so?. Ne'u XQ la xa'u so thi XQ e f( XQ ) = S, v6 ly v i S chi chira nhimg phan tir tot so. 15 Boi dumtg hpc sink gidi Todn td'hgp - red n^c, Nguyen Van Thong C o n neu X Q la to't so' t h i XQ e f( X Q ) = S : c u n g v 6 l y v i X g da to't so' t h l p h a i thupc quen v a i B, d o d o A; va B c6 d i i n g 2 n g u d i quen chung, m p t t r o n g h a i n g u o i do la A ' S. M a u t h u a n d o c h u n g to r a n g A k h o n g the t u a n g d u o n g v d i M . n g u d i k i a la m p t Bj nao d o la m p t t r o n g n h u n g n g u d i quen B. phan ctia M . That vay, Mhvr v a y m o i Aj d a t d u p e t u o n g u n g v d i m o t B, nao d o . N e u i # j n g h i a la A j , gpi M ' la tap cac bp phan ciia A chi g o m m p t p h a n t u d u y nha't t h i M ' c M va ro A khae n h a u t h i Bj, Bj la n g u d i quen ciia h p cung khae n h a u . ( K h o n g n h u vay rang M ' va A t u o n g d u o n g nhau, v i m o i x e A c6 the cho i m g v d i tap {x} e M ' . thi A va Bj, ed ba n g u d i quen c h u n g la B, A j , A j ) . D o t i n h d d i x i i n g , ro rang Bay g i o ta c h i m g m i n h rang A t u o n g d u o n g v o i m g t if T o m l a i , I M I > I A I , va d i n h l y da d u a c c h u n g m i n h . N h u v a y , cho t r u o c m o t tap bat k y , bao g i o c i i n g c6 the t h a n h lap m p t tap CO l y c l u p n g I o n h o n . D o do, k h o n g c6 l u c l u p n g (ban so) nao la I o n nha't ca. 2.4. ' Lyc LLTONG 2 " : '^v'' ' - ••AM.A H ..n mt,: De ket t h i i c v a n de l u c l u p n g cac tap, ta hay t i m hieu t h e m ve t h i i bac tren tap cac ban so. . ; . . « neu Bi va Bj la n h i i n g n g u d i khae n h a u , v | y cd m p t song a n h g i i i a n h i i n g n g u d i quen A va B d o d d so n g u d i quen eiia A v a B n h u n h a u . N e u D la m p t t r o n g n h i i n g n g u d i ed m a t t r o n g eupe h p p t h i hoac anh ta quen v d i A hoac D k h o n g q u e n A t h i se cd 2 n g u d i q u e n c h u n g va k h i d o (theo c h i i n g m i n h tren) A v a D cd n g u d i quen bang so n g u d i q u e n ciia A va cQng bang so n g u d i q u e n ciia D . Vay A va D ed so n g u d i quen n h u n h a u . N h u vay, Cho A la m p t tap bat k y , S la tap tat ca cac tap con (bp phan) cua A . mpt n g u d i bat k y t r o n g n h i i n g n g u d i cd m a t d eupc h p p cd so n g u d i quen bang N e u A la h u u h a n v a g o m n p h a n t u : so n g u d i quen ciia A . v o i m o i b p p h a n M ciia ,a2'-.^n A ta CO the cho u n g day ( ^ i , ^ 2 ' - ' ^ n ) t^ong d o = 0 neu 3 ; ^ M va = 1 neu Bj e M . Phep t u o n g u n g d o ro r a n g la 1 - 1 cho nen tap S t u o n g d u o n g v o i tap tat ca cac d a y {^i.^Z'-'^n) '^o the thanh lap d u p e bang n h i i n g soO v a 1 . N h u n g de thay r a n g so day nay b a n g 2 " , v i m o i day g o m n so' c6 the lay hai gia t r i . mtodn3.2.(TrungQuoc-1997). Trong cac xau nhi phan c6 do dai n, goi a^, /« so cac xau khong chiea 3 so lien tiep 0,1, 0 va \ so"cac xau khong chtta 4 so lien tiep 0, 0,1,1 0,0. Chihtgminh rang: Loi giai M a r p n g k y h i e u do, ta q u i u o c m o t each t o n g quat rang: neu l u c l u p n g ciia i-t •(••••Vsv™:,*.! Ta gpi m p t x a u thupe loai A neu no k h o n g chua 3 so' l i e n tiep 0, 1 , 0 va gpi y i = 0 , y ^ = X i + X 2 + . . . + X i ^ _ i ( m o d 2). Rd rang X ehiia 3 so l i e n tie'p 0, 1 , 0 k h i va chi k h i f(X) chua 4 so h a n g l i e n tiep 0, 0 , 1 , 1 hoac 1 , 1 , 0, 0 t i i c la X thupe loai A ^ ^ ' k h i va chi k h i f(X) thupe B. K h o k h a n I a n nha't k h i giai m p t bai toan to h a p la xac d i n h h u a n g d i " N e u CO m p t song a n h d i t u tap h u u h a n X d e n m p t tap h u u h a n Y t h i I X I = I Y I . T u y t u o n g d o ta t i m d u p e l a i giai cac bai toan sau: ' * Vay f la m p t song anh d i tir tap cac xau loai A d p d a i n d e n tap eac xau loai B dp d a i n + 1 m a bat d a u bang 0. N h u n g t u m o i xau X thupe B ta n h a n dupe mpt xau X Cling thupe B bang each d d i cac p h a n t i i ciia X theo q u y tac 1 - > 0, 0 ~> 1 nen so cac xau loai B d p d a i n + 1 gap d o i so'cae xau loai B d p d a i n + 1 ma / Mgt cuoc hgp c6 n nguai: Mgt so nguai trong ho khong quen hiet nhau, dong thai cH moi cap 2 nguai khong quen nhau lai c6 dung 2 nguai quen chung, con hai nguai quen nhau lai khong c6 nguai quen chung. Chttng minh rang moi mgt con ngupi trong cugc hgp c6 mgt so nhu nhau nhung nguai quen. Lin giai Ta n h a n thay r a n g n h u n g n g u d i q u e n A t h i k h o n g q u e n n h a u (neu k h o n g n h u v a y t h i h p c6 A la n g u a i q u e n chung). Gia s u B, >,.-n. 4 0, 0. v d i m o i xau X = ( x i , X 2 , . . . , x „ ] , ta xay d u n g f(X) = ( y i . y a . - . y n + i ) n h u sau: §3. C N G D U N G A N H X A D E G I A I ^di todn 3.1. 1,1, mpt xau thupe loai B neu no k h o n g ehiia 4 so h a n g l i e n tiep 0, 0, 1 , 1 hoac 1 , 1 , A la a t h i l y c l u p n g ciia S (tap cac bp p h a n ciia A ) se d u p e k y h i ? u 2°'. M O T SO BAI TO AN ROI R A G hoac = 2a^. V g y S g o m 2" p h a n t u : I S I = 2" . - * , A j , A ^ (n > k) la tap h p p tat ca n h i r n g n g u a i q u e n v o i A . K h i d o m o i m p t t r o n g cac A, k h o n g bat d a u b a n g so'O. T i r d o ta ed d p e m . N h g n xet: t u vi|e so sanh l u c l u p n g cae tap h p p , p h u a n g p h a p song anh cd the g i i i p c h i i n g ta d e m so' p h a n t i i eiia m p t tap t h o n g qua s y so sanh l u c l u p n g tap d d v d i m p t t^p khae ma ta da bie't so' p h a n t u eiia n o . ,» ^ d i todn 3.3. (Vd dich Ucraina Ggi M la so cac songuyen ^ong do CO n chit sol 1996) duong viet trong h? thap phan c6 2n chit so, vd n chit so 2. ggi N la so tat cd cac soviet phan CO n chit so, trong do chi c6 cac chU sol, so 2. Chiing minh rhngM = N. 2,3, 4 vd sochUsol \'^{i'^^p]\m B i N H trong h? thap hang so chU THUAN 17 Cty TNHHMIV f H VHKhangVift Lai giai Vai moi so' c6 n chiJ' so' gom cac chu so 1, 2, 3, 4 va so' chu so 1 bang so' chu so'2, ta "nhan d o i " thanh so'co 2n chu so'theo quy tac sau: dau tien, hai phien ban cua so' nay duQc vie't ke nhau thanh so' c6 hai chu so', sau do cac chu so 3 6 n chu so'dau va cac chir s6'4 6 n chii so'sau dugc doi thanh chu sol, cac chu so 3 6 n chir so'sau va cac chir so 4 6 n chu so'dau dugc doi thanh chu so 2. v i du: 1234142 12341421234142 ^ 12121221221112. ^ai todn 3.5. Chiing minh rang vai m, n, k e N h u the^ ta thu dugic mot so' c6 diing n chii so' 1 va n chu so 2. R6 rang day la mpt don anh. De chxmg minh day la mpt song anh, ta xay dung anh xa ngugc nhu sau: voi moi so' c6 n chii so' I v a n chu so' 2, ta cat n chiJ so' dau va n chii so'cuoi roi cpng chung theo cot voi quy tac: 1+1 = 1, 2 + 2 = 2 , 1 + 2 = 3, 2 + 1 = 4, va ta thu dugc mot so' c6 n chii so' gom cac chii so' 1, 2, 3, 4 vai so' chii so' 1 bang so cac so 2. each chgn m + n + l - k s 6 ' t u m + n + l so nen se c6 C|^^n^.i each chgn. Cach thii 1212122 Vidu 12121221221112 1221112 '-m+n+l-^m*-n+^m-l'-n+l+-+'-m-k%+k Loi giai Ta de'm so cac l < a i 0 2 <- ' ' , ! ' Loi giai >k. Xetphep todn f dot vai bo sap thtctuX= (a^.^z.-.a^+n+i-k) ^di todn 3.6. (Vd dick Trung Quoc -1994) N h u the song anh giiia hai tap hop da dugc thiet lap va ta c6 M = N . Cho cacso'nguyen duangn, k vain , c i ^ C ^ c i ^ T - i C i + "+CkCl^+k • Ket qua do cho ta dpcm. 1234142 n h u hinh ben. 1234142 (xi,...,x„) nhu sau: moi Idn chon k so lien tiep tuy y trong X vd doi dau cua chung. (1,1,1). Lai giai Xet bg thii t u X = ( x i , . . . , X n ) tuy y. Ta c6 2 nhan xet sau: 1. Co diing n - k + 1 nhom k so'lien tiep. 2. Sau mot so' chan Ian thuc hien phep toan f cho mot nhom k so' lien tiep trong X thi gia tri k so' do khong doi. N h u vay, moi phuong an thuc hien hiiu han Ian phep toan f cho X tuang ung voi mot bg nhi phan A = (ai,a2,...,an), trong do ta tinh theo modun 2 cua so Ian thuc hi?n f cho nhom k so'lien tiep (Xj.Xj+j,...,Xi+i^_i), va X tro thanh (-lfi"""^' k thi: buac 2 CO c||"j^'^^^^^ each chgn va ta chgn dugc tong cgng n s6^ trong do k chay tu 0 toi n. Lap luan do cho ta dpcm. ^di todn 3.7. Cho truoc cac so nguyen duang m, n. Tinh T = ^ - ^ + ^ k=o 2"" k=o 2" Lai giAi Ta Chung minh tong can tinh bSng 1, tuc la: Yj^),"^^+Yj^'^ k=0 • k=0 Cac liiy thua cua 2 ggi ta lien tuang den so tap eon mgt tap hgp. );> Trong cac tap eon cua tap S = {1, 2, d^ng {ai,a2,...,a„+i}, m + n +1}, de tha'y c6 tap ( l < i < m + l ) trong do aj ^ T n h u s a u : f(X) = {2003 - x |x6X}, V X E T . R6 r a n g (X) + m ( f ( X ) ) = 2 0 0 3 . D o d 6 : ^ n = l a ' 2;Xni[X)=2(m(X) + ( f C X ) ) ) H T | . 2 0 0 3 ^ m = 2 ^ = f(l)_f(2)_ ^ vd cdc cha so"cua N thugc {1, 2,3,4, 2002 chit sothoa man N: 5, 6, 7,8}. G Q I M la tap cac so N thoa d i e u kien de bai. I ^ f(n). n2 V f M "^(2) ' " ' f(n) .•-.-^tls :>«ysi ivJ*::.::,, b M n Vfrn g'"' N e u N = aia2..a2002 t ' , 102002 _ i - , ^ xanh. > , ^ |i - k| c6 cdng nhau. ., Chicng minh td"t cd cdc phdn tic cua M CO cung mdu. 2002sfl^9 . , L a i giai V o i m S i so n g u y e n a, dat Q so d u k h i chia a cho n v a k y h i ^ u Zn = {0, 1 , 2, 2002 so 9 •••/ n -1) t h i CO the coi p h e p to m a u da cho xac d i n h anh xa. vd f: {1,2,..., n} ^ {1, 2 , n } Id mot song ^ > - • k=i k^ i ^ k n,l Moi phdn tic ciia M dugc to bang mot trong hai mdu trang hodc D o N + f ( N ) = 9 9 7 9 ;99 nen f la song anh M - » M . <6di todn 4.0: Cho neH* ^ d i todn tap hap {1, 2 , n f ( N ) = bib2...b2oo2, v a i bj = 9 - Sj NeA 99 n = l Gid sic n Id mot sotyc nhien, k Id mot so nguyen to vai , Xay d y n g a n h xa f n h u sau: 20 „ (2) ^ k m) D a u bang xay ra <=> f ( i ) = i , V i = l , n Loigiai NeM i ; -I 1=1 Hay tinh trung binh cgng tat cd cdc so Ngom 2 X ^ k=l 1 ^di todn 3.9: Txxdo: ktiVk^ — > n 1 f(k) k=l k f(2) (Tong l a y theo tat c a cac tap X thuQC T). '^'^ va 'V 2' in 2002) f(n) f(2) 1' D o c h i n h la d i e u phai chxmg m i n h . , , , i todn 3.8. (VMO - (1) y J _ = ky= li' A p d y n g bat d a n g thuc Cauchy - Schwarz cho 2 bp so. tuc la so' tap con ciia S c6 k h o n g qua n p h a n t u . k=0 n -1 1 dnh. f:Zn > Z2 = {trSng, xanh) D i e u k i l n 1) cho i) f(a) = f ( - a ) , Va e Z fa- . , ^ D i e u k i e n 2) v a i) cho ii) f(a) = f ( a ^ ) , Va e Z 21 Cty TNHH MTV DWH Boi duang hgc sink gioi Todn to hap - rcri rac, Nguyen Van Thong Khang Vi?t Trong mgt so bai toan de'm, dinh l i tren thuang dugc ap dung bang each: Vay vai mpi so nguyen m do ii) c6: f((m + l ) k ) = f[(m + k)k - k) = f(mk) Ivluon de'm so phan tit cua tap hgp A , ta thiet lap mgt song anh tir A den B ma V i (k, n) = 1 t?ip {mk/m € Z} = Zn B la mgt tap hgp da biet so phan t u . Vay f(Zn) la tap chi c6 1 phan t u . Trong bai toan bat dSng thuc to hgp, y tuong tren thuang dugc ap dung ^ d i todn 4.2: Trong mgt hgi nghf todn hgc quoc tetochdc tai quoc gia X, c6 cdc nhu sau: Muon chung minh | A| < |B| , ta tim mgt anh xa d i tir A vao B (hoac B nhd todn hgc trong mcac X vd nude ngodi. Moi nhd todn hgc quoc gia X gin A) Sau do chung minh anh xa do la mgt dan anh (hoac toan anh) nhung dung mgt thong di^ eho mgt nhd todn hgc nude ngodi. Moi nhd todn hgc nude khong phai la song anh. ngodi gid dung mgt thong diep cho mgt nhd todn hgc cua quoc gia X. Mac du ($di todn 4.3. ( I M O 1989). Mgt hodn vj (xi,X2,...X2n> cua tap hotp (1, 2,2n) vay Cling ed it nhat mgt nhd todn hge khong nhan dugc mgt thong diep ndo cd. Id so nguyen duang) dugc ggi la cd tinh chat P neu [xj - X j ^ i j = 1 vdi it nhat Chihtg minh rang ton tai mgt tap hap S gdm cdc nhd todn hgc quoc gia X vd mgt i e {1, 2 , 2 n tap hap T cdc nhd todn hge nude ngodi thoa man cdc tinh chat sau: nude ngodi khong thugc tap hap T. (i) Cach 1. Dat A la tap tat ca hoan v i ciia (1, 2 , 2 n } ; B la tap tat ca hoan v i 2. Cdc nhd todn hgc nude ngodi thugc T chi gtti thong diep cho cdc nhd todn ciia {1, 2, hgc quoc gia X khong thugc S. i •(-•">: ^ • r. 1 Gpi A la tap hgp cac nha toan hpc cua quoc gia X va B la tap hgp cac nha toan nuac ngoai. Goi f: A -> B va g: B A la cac anh xa dinh nghia nhu sau: f(a) la nha toan hpc nuoc ngoai nhan thong di^p ciia a va g(b) la nha toan hoc cua quoc gia X nhan thong diep cua b. Neu cac tap con S va T ton tai thi T = B\ f(S). Vay ta phai chung minh ton tai mot tap S c A sao cho A\ = g(B\f(S)). Vai m6i tap con X c A, goi h(X) = A\g(B\f(X)). Neu X c Y thi. v;;f(x)cf(y) . ; ' 2n} khong c6 tinh chat P. Ta chia cac so 1, 2 , 2 n thanh n cap sau: (1; n +1), (2; n + 2 ) ; ( n ; 2n). Gia su (x^; X 2 ; . . . ; x^^i; X;^; Xj^^^;...; X 2 n ) la mgt hoan v i thugc C. Gia su la so'ciing cap vai X 2 n , suy ra k < 2n - 2. Ta xay dung anh xa f : C X = (x^, X 2 , , B nhu sau X i ^ _ i , X|^, X | ^ ^ l , X 2 n ) -> Y = ( X j , X 2 , , , >-• '^k+l ) De tha'y rang f la don anh va f khong phai la toan anh. =>g(B\f(Y))cg(B\f(X)) =>A\g(B\f(X))c:A\g(B\f(Y)) That vay, xet yo = (x^, X2 x^-i • ^n+i • ^n+i 2n ) Khi do khong ton tai XQ de f( X g ) = YQ. D O do f khong phai la toan anh. ^ h(X) c h(Y) T u do ta suy dieu can chung minh. theo gia thiet g khong phai la toan anh vay ton tai HQ thugc A ma khong thugc g(B\f(X)) vay thugc h(X) vai mgi X c A. Vay mgi tap hgp trong M chua ag. Vay S = X e M n X khac rong. Theo dinh nghla cua S ta c6 h(S) c S. Theo tinh chat dan d i f u cua h ta c6 h(h(S)) e h(S). Vay h(S) e M va S c h(S). Tong hgp cac ket qua tren ta c6 S = h(S) (dpcm). C| < n(2n - 1)!. T u do dan den each chung minh t h u 2 sau: (ii)Cach 2. Ggi Aj^ la tap tat ca hoan v i thoa man k va k + n dung canh nhau, A la tap hgp tat ca cac hoan v i c6 h'nh chat P. Suy ra A = (JAJ^ . Theo nguyen ly bao ham loai tru, ta C O Cho A va B la hai tap hCru han. mgt dan anh f : A k B thi |A| < |B| ; 2. Neu C O mgt song anh f : A -> B thi | A| = B| ; 3. Neu C O mgt toan anh f : A B thi |A| > JB Ta ' > i M = n(2n-l)! J^MnxetTa c6 |C|n|B| = 0 ma |C|+ |B| = |A| = (2n)! nen |B! A=y:Ak-yKnAhK Sir dung mgt so tinh chat ciia anh xa CO 2nl c6 tinh chat P; C la tap tat ca hoan v j ciia {1, 2, ^B\f(Y)c=B\f(X) G(?i M = {X c A/h(X) c X). Tap hgp M la khac rong v i da c6 A e M . Mat khac 1. Neu - 1}. Chicng minh rang moi n, so hodn vi ed tinh chat P Idn han so hodn vi khong cd tinh chat P. Lai giai 1. Cdc nhd todn hge quoc gia X thugc S chi gid thu eho cdc nhd todn hgc Loigiai (n CO Suy ra kSK|-IKnAh k 2n(2n - 1)! - ^^^^^^ • 4(2n - 2)! = 2n^ (2n - 2)! > ^ T u do ta C O dieu can chiing minh. ^di todn 4.4. (Romania TST 2002). Vai moi so nguyen ducmg, ta goi f(n) la so each chon cac dau +, - trong bieu thiic: = ± 1 ± 2 ±... ± n sao cho En = 0. Chiing minh rang (a) fin) = 0khin^l,2 (mod 4) ta c61 C O the chi ra 6 truong hop khi xay dung — ' — << f(n) Do do anh xa tu den An • T u do xac dinh ^"h. An+4 Mat khac vol moi A n ta xac dinh dupe duy nha't mpt , voi moi En cung xac dinh dupe duy nha't mpt A n . ' + f(4k + 3) = f ( ( 4 k - l ) + 4 ) > 4 f ( 4 k - l ) > 4 ^ f ( 4 f - 5 ) > . . . > 4''f(3) <2"-2L2J (^) = 4^2=- Loi giai (a) Gia su ton tai mpt each dat dau +, - voi n = 1, 2 (mod 4) de Khi do 1 + 2 + ... + n = 0 (mod 2), suy ra "^"^^ An+4 dugc An la duy nha't. Do do f(n + 4) > 4f(n). ta c6 f(3) = f(4) = 2. Suy ra (mod 4). +1 (b) Khi n=0,3 Do do ta Khang Viet = 0. + f(4k + 4) > f((4k - 1) + 4) > 4f(4k - 1) > 4^ f(4f - 5) > ... > 4'' f(4) _(V2p = 0 (mod 2). Ma dieu nay xay ra khi va chi khi n = 0, 3 (mod 4). Ta c6 dieu can chiing minh. (b) Ta chung minh f(n) < 2""^. That vay, chia tat ca bieu thiic thanh 2""^ cap theo dang : (1 + 2a2 + Sa^ + ...+ n a ^ ; - ! + 2a2+ 3 3 3 + ...+ nan)v6i a; e (1;-1}, i = 2,n . Neu f(n) > 2"~^ thi theo nguyen l i Dirichlet ton tai 2 bieu thuc cung nam trong mot cap n tren, hieu cua chung bang 2. Do do chiing khong the dong thoi bang 0 dugc (mau thuan). ^ > ^ »K ' +1 , .,»- Do do f(n) < 2"-^ = 2" - 2""^ <2"-2^^^ j 4 f) Ta chiing minh f(n) > -^^—'—. 1' T u E„ ta se xay dvmg * Ta dinh nghia • , A„+4 nhu sau • Neu 1 € A n thi chon An+4 = An u {1; n + 1; n + 3); • Neu.2 e A n thi chpn An+4 = An \) u (n + 3; n + 4}; • Nell 2 g A n thichon An+4 = AnU{2;n • Ta thay tap An+4 , * ^' |BI| = |B2|. .i , B 2 Ian lupt la tap cac so'chan va le ciia B, 4 , F :D ^ E . ... -^ " Bh^Bin(Y\B2) Ta c6: |f(B)| = n ( Y \I = [B^| + =n |Y|-|B Suy ra f(B) e E. De thay f la don anh. Ta chiing minh f la toan anh. + l ; n + 2). N h u vay voi moi each chon A n ta c6 the xay dung it nha't 4 tap An+4. <5upc xay dung t u tap A n va them diing mpt cap trong tap (n + 1; n + 2; n + 3; n + 4) va A n chiia diing mpt cap nhu the' • Tinh so tap can: Xet anh xa \n + 2 ; n + 4}; An+4 Gpi D la hp tat ea cac t^p can ciia A ; E la hp tat ca tap con n phan t i i ciia A . khi do = An la tap tat ca cac so c h i n eiia A ; Y = {1; 3 ; 2 n - 1} la Gia sii B la mpt tap can ciia A . E„+4 An+4 bang sole. Bat so tap tot 2^""^ la T, so tap can la C. Chiing minh rang: T+C< K i hieu X = (2; 4 ; 2 n ) tap tat ca eac so le ciia A . ^ N e u l e A n thichQn Gia sir cho truac tap tap tot neu trong tap do so cac sochan it han so cac sole. Mot tap con B cua A duoc goi la mot tap can neu trong tap do sosochdn Loi giai (if bang (gdi todn 4.5. Cho tap hap A = {1; 2 ; 2 n } . Mot tap con C cua A duoc goi la mot ^jf't.' Xet bieu thiic E n , gpi A n la tap hop cac so xuat hien trong E n vai dau + 6 truoc. Neu En = 0 thi tong cac phan t i i cua n) > — ' — . Vay ta c6 di Vi vay f(n) dieu can chiing minh. That vay, gia sii M la mpt tap con c6 n phan t i i ciia A . Gpi , IVI2 Ian lupt la tap cac so chan, cac so le ciia M . Dat Bi = M l , B2 = Y \ M 2 , B = B^ u B2. . , , , ; 9=; Cty TNHH MTV DWH Boi duang hoc sink gioi Todn to hap - red rac, Nguyen Van Thong B2I = |Y\M2| = |Y| - IM2I = n - IM2I = | M I | . D O d o B la Suy ra m p t tap can hay f la toan anh. DAI s6 T 6 H O P V i vay f la song anh. T u d o suy ra so tap can la C^n • • fj T i n h so'tap to't: §1. Gia su C la m o t tap tot ciia A . G p i F la hQ talt ca tap tot ciia A . /' tarn ky su. M o i k y t u c6 the la m p t c h i i so hay m p t c h u cai. M o i m a t k h a u p h a i ^ chii'a i t nha't m p t chir so. Ta thiet lap anh xa sau G:E^F H o i CO bao n h i e u m a t khau n h u vay? N h i r n g k y thuat can thiet de tra l o i • ,,„:,; cho cau h o i d o va m p t l o p r p n g Ian cac bai toan d e m khac se d u p e g i o i thieu Cin(Y\C2) trong c h u a n g nay. Suy ra |g(C)| < n . Ta CO g la m o t d o n anh nen |F| < C^n + Bai toan d e m cac p h a n t u xuat h i e n rat n h i e u t r o n g toan hpc c u n g n h u t r o n g + ...+ C^'^ = 2^"-! - C 5 „ . tin hpc. V i d u c h i i n g ta can d e m so n h i i n g ket qua t h a n h cong ciia cac t h i T u cac dSng t h u c va bat d a n g t h i i c tren, ta c6 d i e u can c h u n g m i n h . N h a n xet. Ta c6: C^n = (2n)! (n + l ) ( n + 2)...2n (n!f n! nghiem va toan bp n h i r n g ket qua kha d i ciia n h i i n g t h i n g h i ^ m d o de xac d i n h xac sua't cac bie'n so r a i rac. C h i i n g ta can t i n h so cac p h e p toan p h a i l a m t r o n g >2L^J mpt thuat toan de n g h i e n c i i u d p p h i i c tap ciia no. T r o n g p h a n nay c h i i n g ta se t r i n h bay cac p h u o n g p h a p d e m co ban, c h i i n g T u d o ta CO bai toan sau: ^di todn 4.6. Chiing minh rang so'cac thanh tong ciia cac songuyen mot so cho truac) xuai him thanh tong cac songuym dumg qua mot each bieu dim mot ma khong c6 sonao Idn khong Ian han duang ma khong eo sonao songuym duong n chia hei cho p (p la so each bieu dim chia hei cho n . Lai giai " Xet bo f , 8 2 , } ^ao cho t r o n g bo k h o n g c6 p h a n t i i nao chia het cho p la nen tang cho h a u n h u tat ca cac p h u o n g p h a p khac. 1.1. Q U Y T A C C O N G : Chimg minh: Xay d u n g song anh f : A - > (1, =n an} = { b i , b,,, p ^ i . t ^ ; . . . ; p'"'.tt) G p i M la tap tat ca cac each bieu d i e n n t h a n h t o n g ciia cac so n g u y e n d u a n g ma k h o n g c6 so nao chia het cho p (p la m o t so cho t r u o c ) xuat h i ^ n qua m p t Ian va N la tap tat ca cac so bieu d i e n n t h a n h t o n g cac so n g u y e n d u o n g a^} h-> bi,b2 " ' ' • '''' bi,,pti,pti,...pti,pt2,pt2,-pt2,-.Ptt>Ptf-Ptt p-J^ so p De thay f la m p t d o n anh nen ta c6 d i e u can c h u n g m i n h . ' + n} "^"^^^ neu X E B , 1/ '1 111 i 1 V x i , x 2 e A w B , h ( x i ) = h(x2) v i do A n B = 0 nen f ( x i ) = f(x2) va g f x j + m ^ g ( x 2 ) + m f ( x i ) = f ( x 2 ) v a g ( x i ) = g(x2) ^1 = ^2 ( V i f, g deu la song anh) Vay anh xa h la d a n anh. N V- {ai, ' Ta c h i i n g m i n h h la song anh: ^ ma k h o n g c6 so' nao chia het cho p^. Xet anh xa sau: f : M v6ih(x)= j^W [g(x)+m ' 2 , m } h : A u B ^ { l , 2 , m Bieu d i e n tat ca cac so chia het cho p d u a i d a n g p*" .t (r > 1 ; t / p). •'r.-i ' V Gia s i i |A| = m , IBI = n g :B { 1 , 2 , n ) xuat h i ^ n qua m g t Ian va ^ ^ B j 82,..., r Cho A , B la hai tap him han va A n B = 0 t h i |A| + |B| = |A + B| m Giasu{ai, PHfiPDEM J\fhdn xet: M a t k h a u de t r u y cap vao m p t h | m a y t i n h g o m sau, bay hoac G p i Ci, C 2 Ian l u g t la tap so chan va le ciia C t h i Ch^ Khang Viet *;A • N g o a i ra, h toan anh v i m p i p h a n t i i ciia h deu c6 anh va m p i p h a n t i i ciia 2 , m + n) d e u c6 tao anh nen h la toan anh. V a y h la song anh. h : A u B -»{1, 2 , m + n} la song anh hay | A U B | = |A| + |B Cty TNHH Boi duang hqc sink gidi Todn to hap - rbi rac, Nguyen 1.2. QUY TAG C O N G GHO n TAP 1 4. QUY HOP; =0 t^pd6,thi A;^ u . - . u A ^ = | A I | + | A 2 | + . . . + A ^ ] , neu i ; ^ j , t h i Chung Chung minh Gia su A^.-.A^ la cac tap h u u han d o i m p t r o i n h a u . Bang TAG N H A N G H O n TAP | A I X A 2 X . . . X A „ | = |AI||A2|...|A„| A i X...XAk XAk+i I = |(Ai X...XAk)xAk+i = |(Ai X...XA J^an la k + 1 tap h i n i han d o i m o t r o i n h a u . K h i do (Aj u...uAi^) va Aj^^i c i i n g r o i n h a u . Theo gia thiet q u i nap, ta c6: =|(AiU...uAJuAk+i xet qui tdc nhdn: ; ^ . ..^ . Gia su m g t h a n h d g n g H bao g o m n giai doan ke tie'p va dgc lap v o i nhau, +...+ + Bj each thuc hien. K h i do hanh d g n g H c6 ca thay ai,a2,...,an each thuc hien. iNhdn xet guy tdc cong: 'Bdi todn chia khda J. Gia s u ta c6 n h a n h d g n g loai t r u Ian nhau Hi,...,Hn, t i i c la k h o n g the xay ra Co bao nhieu anh xa t u m g t tap hgp X eo k phan t u t o i m g t tap Y c6 m phan t u . hai h a n h d g n g d o n g t h o i . Ta c i i n g gia s u rang h a n h d g n g H i c6 3 ; each thuc C O ca thay Chicng xay ra, hoac H2 xay r a , h o a c H„ xay ra, h i f n. K h i do h a n h d g n g H : hoac minh: Giasu Y = {yi,y2 « A = {ai,a2,...,a^}, T i c h De-cac A x B . X , f(x) B = {bi,b2,...,bk}. g o m cac cap (aj.bj), 1< i < m, 1< j < k , c6 the v i e t thanh m g t bang chir nhat c6 m d o n g k cgt n h u sau. /• 5 (ai-bi), (ai,b2)...(3i,bk) ' ( 3 2 , b i 3 , [a2,b23... ( 3 2 . b k ) I » J >i Ji'i ' i u X2 f(Xl) D o n g t h u hai f ( x i ) , f ( x 2 ) , •• f(X2) Xj ... f(Xi) Xk f(Xk) f ( X k ) la m g t day k p h a n t u cua Y. N o la mgt p h a n t u ciia rich De-cac Y x Y x Y x w/., /» ,t y^} M o i anh xa t u X t a i Y d u g c hoan toan xac d i n h b o i bang cac gia t r i cua no. Cho A, B la hai tap h u u han va A n B = 0 t h i A x B = A . B C h u n g m i n h : Gia s u |A| - m, |B| = k va ! X = {xi,X2,.Mk} +...+an each thuc hien. 1.3. Q U Y T A C N H A N : ' |Ak+i|- |Ai| |A2|...|Ak||Ak+i trong do giai doan t h u i la hanh d g n g H j . Ta cGng gia s u rang hanh d g n g Hj c6 =(AiU...uAJ ,j , Ta c i i n g c h i i n g m i n h dang thuc tren bang q u i nap theo n . V o i minh t u d i n h nghia t o n g cua hai ban so. Gia su dang thuc tren da d u g c c h u n g minh AiU...uAkUAk+i HOP. ...,Ak,Ak+i la k + 1 tap h i r u han bat ky. K h i do gia thiet q u i nap. V a i n = 1, d a n g thuc tren hien nhien d i i n g . V o i n = 2, dang t h i i c tren suy ra va Ai,...,A|^+i Viet tich cua h a i ban so'. Gia s u dang t h u c da d u g c c h u n g m i n h cho n = k > 2 va q u i nap theo n, ta c h u n g m i n h rang: A^ u . . . u A n = A^ +...+ A„ . cho n = k > 2 Khang dang t h u c la hien nhien d u n g . V a i n = 2, dang t h u c suy ra t u d i n h nghia 6 day JAjj la luc l u g n g (so cac p h a n ttr) cua tap A j . , DWH Neu A i , . " , A n la cac tap h u u han bat ly va AjX...xAn la tich De-cac cua cac A j , A 2 , A n la cac tap h i i u han d o i m o t r o i nhau, t i i c la A j n A j Neu MTV Van Thong x Y = Y"" Dao l a i , m g i day k p h a n t u cua Y la (y„^ ,y^^ <-,yak) xac d i n h m g t anh ' x? f tir X t o i Y, neu ta dat f ( X i ) = y ^ j . Su t u o n g u n g d o g i i i a tap h g p cac anh xa Cam-bi)' Cam,b2)...(a„,,bJ D a t Aj = { ( a i , b i ) , ( a i , b 2 ) R6 rang |Aj| = k v o i l < i < m ^^ (ai,bk]}vdi ^ X t a i Y va rich De-cac Y"" la m g t song anh. Vay so anh xa riJ X t d i Y bang yk l rUJ • Theo q u i tac cgng, ta c6: |AXB| = |A]^| + IA2I +...+ |An,| = m.k = |A| . |B Vay = m Jle qud:C6 Chung bao n h i e u each p h a n p h o i k do vat vao m ngan keo ? minh M o i each p h a n p h o i la m g t anh xa tir tap h g p k d o vat vao tap ^liVp m ngan keo. V i v$y c6 m"^ each p h a n pho'i k do vat vao m ngan keo. |AXB| = |A|.|B 29 Cty TNHH MTV DWH Boi duong hoc sinh gioi Todn to hop - rcri rac, Nguyen Van Tfiong 1.5. C A C Vf DU MINH H O A . Vi du l:Mot Nguai ChOng minh: ban ddi c6 2 day ghe dot dien nhau, moi day gont c6 6 ghe. ta muon xep cho ngoi cho 6 hoc sinh trudng A va 6 hoc sinh truang B trudng ki 2 hgc sinh ndo ngoi c^nh nhau hoac dot di?n nhau tht khdc cho ca hai tap h o p A va B tuc la A n B| d u o c t i n h hai Ian. D o d o | A | + | B | = | A u B| + | A n B| <=> | A u B | = | A | + | B | - | A n B t,) T n r t m g h A n B = 0 + Jie qud:Gia six A , B la h a i tap hiJu han ne'u B c A t h i B ngoi Vidii 2:Trong V a y so each xep 2 hoc sinh n g o i canh hoac d o i d i f n p h a i khac t r i r o n g la: mot cdu veHinh 12 X 6 X 5^ X 4^ X 3^ X 2^ X 1^ =1036800 b) Ghe So' each xep cho mot dethi 1 12 2 11 3 10 4 9 5 8 6 7 12 6 10 5 8 4 6 3 4 2 2 1 tich, hgc. Trong 60 tht sinh dvc thi, co 48 tht sinh gidi duoc cdu So thi sinh gidi duoc cdu So hgc hoac Gidi tich, 50 thi sinh gidi duoc cdu Gidi tich hoac Hinh hgc, 25 thi sinh gidi duoc ca hai cdu So hgc va Hinh hgc, 15 thi sinh gidi duoc cd ba cdu. Hoi co bao nhieu thi sinh khonggidi duoc cdu ndo? Loi giai V a y so'each xep 2 hoe sinh n g o i d o i d i f n phai khac la: K i h i f u T la tap tat ca cac t h i sinh. A , B, C Ian l u g t la tap h g p cac t h i sinh 1 2 x 6 x 1 0 x 5 x 8 x 4 x 6 x 3 x 4 x 2 x 2 = 33177600 giai dugc cau So hoc, Giai tich, H i n h hgc. Theo t i n h chat 2 ta co: Q U A : Q u i tac trir AnB = A + B A la m o t tap hxxu han, va B la m o t tap con cua A . D a t B = A - B . Ta c6: mot cdu veGidi hgc, 40 thi sinh gidi duoc cdu Gidi tich, 32 thi sinh gidi duoc cdu Hinh hgc. Co 57 ngoi 1.6. co ba caw. mot cdu veSohgc, B n C =|B + C B= A- B= A - B A u B | = 48 + 40-57 = 31 B u C =40 + 32-50 = 22 I n e n : A u B u C | = A | + | B | + |C| - | A n B| - | B n C| - |C n A | + | A n B n C| Chung CO: minh : That v a y v i A = B u B va B n B = 0 nen theo q u i tac cpng ta B T u d o suy ra: 1.7. s6 = 48 + 40 + 32 - 31 - 22 - 25 + 15 = 57 V i (A u B u C) c T nen theo t i n h chat ta CO T \ ( A u B u C ) | = | T | - | A u B u C | = 6 0 - 5 7 = 3. = A - B P H A N TCT C U A H O P H A I H O A C B A T A P H O P H O U (1) Vay CO 3 t h i sinh k h o n g giai d u g c cau nao. HAN a) Tnrcmg hgrp h a i tap h g p : Cho hai tap hop huxi han A va B ta c6 cong thuc. A u B = A + B - A n B ' ' Vidu 3:Khi dim tra kei qud hgc tap cdc mon Todn, Ly, Hoa cua mot lap co 45 hgc sinh, nguai ta nhan thay: co 19 hgc sinh khong gidi mon ndo, 18 hgc sink gidi Todn, 17 hgc sinh gidi Ly, 13 hgc sinh gidi Hoa, 10 hgc sinh gidi ^on Todn vd Ly, 9 hgc sinh gidi hai mon Ly vd Hoa, 10 hgc sinh gidi hai hai mon T^odn vd Hoa. Hdi bao nhieu hgc sinh gidi cd ba mon? 30 31 Boi duang hgc sinh gidi Todn to hop - rai rac, Nguyen Van Thong Cty TNHHMTV DWH Khang Viet Lai giai Ki hieu T la tap hgp hoc sinh ciia lap. A, B, C Ian lugt la tap hgp cac hgc sinh gioi Toan, Ly, Hoa cua lop do. Vi A u B u C = T \ [ T \ ( A u B u C ) ] Nen so'hoc sinh gioi it nhat mot mon la t A u B u C| = |T| - |T \A u B u C| = 46 - 19 = 26 Suy ra so'hoc sinh gioi ca ba mon la • r A n B n C = A u B u C - A - B - C + | A n B + B n C + Cr.B = 26 - 18 - 17 - 13 + 10 + 9 + 10 = 7 ,, ,, Vi du 4: Tim hieu kei qua hoc tap d mot lap hoc, nguai ta thay: • Han - so hgc sinh dcit diem gioi a mon Todn cung dong thai dat diem 3 gioi a mon Vat ly; ; H • Han - so'hgc sinh dat diem gioi & mon Vat ly cUng dong thod dat diem 3 gioi d mon Van; ^ thai dat dieM giai a « Han -2 so hgc sinh dat diem gioi a Van cung dong mon Lich sit; e Han - so hgc sinh dat diem gioi a mon Lich sii cung dong thai dat diem 3 gioi a mon Todn; Chicng minh rang trong lap hgc noi tren c6 it nhat mot hgc sinh dat diem gioi cd ban mon Todn, Vat ly, Van vd Lich SM'. (De thi MSG Quoc gia THPT Bang B-2005). Ldi giai Ki hi|u T, L, V, S Ian lugt la tap hgp cac hoc sinh gioi Toan, Vat ly. Van, Lichsu. Theo | T n Lde> bai, - T , ta c6: L n V > (*) V n S > 3— V S n T > 3— 3 ' 3 Ta giai bai toan bang phuang phap phan chung. Gia su.khong c6 hgc sinh nao dat diem gioi 6 ca bo'n mon Toan, Vat ly. Van va Lich su, khi do chi con: T n V = 0 hoac L n S = 0 . Neu T n V = 0 thi ( T n L ) n ( L n V ) = 0 va ( T n S ) n ( S n V ) = 0 . Ma ( T n L ) n ( L n V ) e L va (TnS)n(SnV)cS y'y 32 •(•If Nen (TnL)+(LnV)|<|L|. Va |(TnS) + ( S o V ) <|S Suyra |TnL| + |LnV| + |TnS| + |SnV|<|L| + |S| (1) , ; r:;;;. - : Mit khac, tu (*) ta c6: |T n L| + |L n V| + |T n S| + |S n V| > | ( | T | + |L| + |v| + |s|) •J Ma |(|T| + |L| + |V| + |S|) = i[(|T| + |L|) + (|T| + |S|) + (|L| + |V|) + (|S| + |V|); = i(|T u L| + |T n L| + | T u S| + |T n S| + |L u V| + |L n V| + |S u V| + |S n V|) Nen 2(|TnL| + |LnV| + |VnS| + |SnT|)>|TuL| + |TuS| + |LuV|+ |SuV , >|L| + |S| + |L| + |S Suy ra |TnL| + |LnV| + |TnS| + |SnV|>|L| + |S| (2) Tix (1) va (2) ta gap mau thuan nen dieu gia su ban dau la sai. • Neu L n S = 0 lap luan tuong tu ciing dan den dieu mau thuan. Bai toan dugc chung minh ^ ^, , .^j,, ,^^^., ,. . §2 T O H O P KHONG LAP jVhan x^t: Gia su mgt dgi quan vgt c6 muai cau thu huan luy|n vien can chgn nam nguai di thi dau a mgt truong khac. Ngoai ra ong ta cung chuan bi mpt danh sach c6 thu tu gom bon cau thii de tham gia bo'n tran chai don. Trong muc nay ta se nghien cuu cac phuang phap de'm so each chgn khong c6 thii tu nam cau thu de di thi dau va c6 danh sach khac nhau gom bon cau thii tham gia tran choi don. ^ Tong quat han, chung ta se trinh bay cac phuang phap de'm so each chgn khong CO thu tu cac phan tu khac nhau va nhirng sap xep c6 thii tu cac do'i hrgng cua mgt tap hiiij han. 2.1. T6 HOP (J6 HOP KHONG LAP) So'tap con ciia mgt tap hop c6 m phan tu. Cho t^p hgp A c6 m phan tii. Ta hay xet xem tap hgp tat ca cac tap con ciia ^O/ T(A), CO bao nhieu p h a n tu. ^ Y nhu sau: Cho x e A , neu x e B thi ta dat f(x) k(k-i)...2 = 1, con neu x g B thi ta dat f(x) = 0. ( m - k + 2) k_2 _ — — k-1 ™ la so tap con 1 phan tir cua A. No bang so phan tir ciia A, tuc la m. Vay N h u vay ling voi moi tap con B ciia A , c6 mgt anh xa f tir A toi Y. k Dao lai, neu f la mgt anh xa tir A toi Y thi ung voi no c6 mgt tap con B cua A , gom tat ca cac phan tir x e A sao cho f(x) = 1. Svr tuong ung ay giira tap hgp cac tap hgp cua tap hgp A va tap hgp cac m(m-l)...(m-k + l) _ m ( m - l ) . . . ( m - k + l)(m-k)...3.2.1 _ m! 1.2...k(m-k)...3.2.1 k!(m-k)! anh xa tir A toi X ro rang 1 - 1. Do do so tap con cua A , tuc la T { A ) , bMng so .; , „ Vi du 1: Cac duang cheo cua mot n -giac loi gap nhau tai bao nhieu diem, anh xa tir tap hgp A c6 m phan tir toi tap hgp Y c6 2 phan tir. Ta bie't rang so nay la 2™ . Vay: Khang Vi$t Chuy: Ta CO CjJ, = 1 , vi chi c6 mgt tap con khong chua phan tir nao, do la tap bang sm-i vi cac tap con do ding la cac tap con cua tap hgp A ' = A - {a}. Vi T{A) = DWH nhi hat ki 3 dubmgcheo nao cung khong cat nhau tai mgt diem? |T(A)| = 2" Loi giai 2.2. T 6 HOP: Moi giao diem ling voi 4 dinh cua n -giac, dao lai 4 dinh cua n -giac xac ^inh nghia 2.2.1. Mgt tap con k phan tir cua mgt tap hgp m phan tir dugc ggi •linh mgt giao diem (do la giao diem cac duong chte cua t i i giac xac djnh boi la mgt to hgp chap k cua m phan tir. cac dinh ay). V i vay so tat ca cac giao diem bang so to hgp chap 4 cua n dinh. So' to hgp chap k cua m phan tir. n(n-l)(n-2)(n-3) m! m(m-l)...(m-k + l) k!(m-k)! 1.2...k " (1) n(n-l)(n-2)(n-3) 1.2.3.4 24 Vi du 2: Co bao nhieu cdch phan phot 5 do vat cho 3 nguai, sao cho ^Sum deu nhan dugc it nhai mot do vat? 34 ; f jL • moi , M 35 Boi duang hgc sitth gidi Todn to hap - riri rac, Nguyen Van Thong Cty TNHH MTV DWH Khang Vi?t L6i giai N e u k h o n g ke d e n t i n h giao hoan ciia phep cpng, t h i so' 5 c6 the p h a n ticli t h a n h m p t t o n g cua 3 so' ty; n h i e n khac 0 theo cac kieu khac n h a u sau day: 5=1+1+3=1+2+2=1+3+1=2+1+2=2+2+1=3+1+1. L f n g v d i cac k i e u p h a n tich d o , c6 cac k i e u p h a n pho'i 5 d o v a t cho 3 nguoj A , B, C sao cho m o i n g u o i d e u n h a n d u p e i t nhat m p t d o v a t n h u sau: \ K i e u II III IV V VI A 1 1 1 2 2 3 B 1 2 3 1 2 1 C 3 2 1 2 1 1 Theo k i e u I , A n h a n d u p e 1 d o v ^ t t r o n g so'5 d o vat, v a y A c6 C3 = 5 each chpn. B n h a n d u p e 1 d o v a t t r o n g so'4 d o v | t con l a i , v a y B c6 the chpn theo C4 = 4 each. C o n C t h i n h a n 3 d o v a t con l a i theo d u n g 1 each. Theo q u y tac nhan, so each p h a n p h o i theo k i e u I la C5C4.I = 5.4.1 = 20 each. Lap luan tuong t y , ta se tha'y rang, phan phoi theo l^nnhat. kieu I I c6 C^C^.1 = 5.6.1 = 30 each; theo k i e u I I I c6 C^cil = 5.4.1 = 20 theo k i e u I V c6 2r2 C^C^.1 = 10.3.1 = 30 each, theo k i e u V c6 C^C^.l = 10.3.1 = 3 0 , theo k i e u V I c6 m-i C„, neu o ( 2 n - l ) = 15<^n = 8 n-k +1 k n-k +1 > 1 , tir d o k < < 1 , t u do k > 1 1^1 "'fie. +1 J J , , do do n-1 , n+1 c;;"^ t u d o k < k + l> (don>2) «) Trong tophdi co mat cd nam Ian nit. n +1 b') Trong tophdi co 1 to truang, 5 to vim, han nita An vd Binh j ^^oi CO mat trong to. - ;1 * L o i giai 6 14! each chpn 6 n g u o i bat k i : €^4 = — = 3003 , 6!8 >; m:. • khongdong ] ;"'"4 37 Boi duang hpc sink gioi Todn tohqp - rcri rac, Nguyen Van Thdng Cty TNHH MTV DWH So'each chon 6 nguoi toan nam: Cg = 1 Moi duang ngan nhat di tu diem (0, 0) den diem (m, n) deu gom m + n doan 8! = 28 6!2! Do do so' each chgn to eong tac de c6 nam Ian nvt. 3003 - (1 + 28) = 2974. So' each chon 6 nguoi toan nu: Cg b) Cdchl: '^ ' ' " " + IZC^^ = 4752 Tuong t u so'each chpn c6 Binh ma khong c6 A n cung la: + 12Cji = 4752 So each chon khong eo A n Ian Binh: 12C^i = 1 2 - ^ = 5544 Do do yeu cau bai toan: 2(0^2 + UC^i) + UC^^ = 2(4752) + 5544 = 15048 jigan nhat t u diem (0, 0) tai diem (m, n) bang so each ehpn n doan dpc t u m + n c|^^_^)^,^ c6 y nghia hinh hpc nhu sau: Do la duang ngan nhat tir diem (a 0) tai diem (m - k, k). ^ 'M " ' Chon tuy y 6 trong 14 hoc sinh eo: Chii y: Ta eung eo the xet so' each ehpn m doan ngang thay cho n doan dpc. Khi do so duong ngan nhat t u diem (0, 0) toi diem (m, n) se la Cj^^^ . N h u vay ta da chung minh dupe bang hinh hpc dang thuc C^^^ = Cj^+n. 2.5. MOT S 6 TINH CHAT QUAN TRONG C U A C A C S6 2.5.i.Ne'u 0 < k < m t h i Zi . (2) Chicng minh: each. Chon A n va Binh roi chon them 4 hoc sinh trong 12 hoc sinh eon lai c6: C^2 each. Vay so' each chon 6 hoe sinh do A n va Binh khong dong thai c6 mat: Vol 6 hoc sinh da chpn xong c6 6 each ehpn ra to truong. Vay so each ehpn thoa yeu cau de toan la: = cf^.^j.^ Cdch 1: Theo y nghia hinh hpc cua so' cJ^=cL_|^wk, ta da thay rang C(m-k)+k = • Cdch2:Neu chinh la cong thuc (2) dimg eong thuc (1) thi ta eo ngay „m-k sicf^ - ^ 1 2 ) = 15048 each. m! {m-k)!(m-(m-k)!) m! =C (m-k)!k! V nghia tap hop eua eong thuc (2) nhu sau: Gia su tap hop A c6 m phan tu. • Xet mot mang duang hinh chir nhat kich thuae m x n, tao thanh bai nhiing hinh vuong, ngan each nhau boi n - 1 duong ngang va m - 1 duong dpc nhu tren hinh ve. Ta hay tim so duong ngan nhat tren mang duang do de di t u goc dual ben trai diem (0, 0) tai goc tren ben phai (diem (m, n)). (0,n)- Ne'u B mpt tap con k phan t u eiia A, phan bu B eua B trong A la mot tap con (m - k) phan t u cua A. N h u vay giira tap hop cac tap con k phan t u ciia A va tap cac con (m - k) phan t u eiia A c6 mot tuong ung 1 - 1. Do do so' tap eon k phan tu bang so'tap con m - k phan tu. Dieu nay dupe dien ta boi eong thiie (2). •2.5.2. Ne'u m va k la nhiing so t u nhien sao cho 1 < k < m - 1 thi ta c6. pk _ p k - l (m, n) pi -m-1 (4) Cong thuc nay dupe gpi la quy tac Pascal Chung minh: £a£lLl: ViC;;-_\ •58 ' Cong thuc nay dupe gpi la quy tac do'i xung. x ; , ,// 2,4. Y NGHlA HINH HOC CUA thii t u ke'tie'p eiia eac doan ngang va cac doan dpc. Vi vay so tat ea cac duong N h u vay, so Cj^ = 11! . So'each chon A n lam to vien va khong c6 Binh: IZ.Cn - 12.-^^ = 3960 Vay so'each chon CO A n ma khong CO Binh: thang, trong do c6 m doan ngang, n doan doe. Cac duang ay chi khae nhau boi do^n dpc ngang, hie la bang Cj^+n . = ' So each chon A n lam to truong va khong eo Binh: I.C12 = Cdch2: Khang Viet (m, 0) X Va C m - l (m-1)! (m-l)!k (k-l)!(m-k)! k!(m-k)! (m-l)! (m-l)!(m-k) k!(m-l-k)! k!(m-k)! \ )
- Xem thêm -