Bồi dưỡng kiến thức cho học sinh giỏi Toán tổ hợp - Rời rạc: Phần 1

Chia sẻ: Cô đơn | Ngày: | Loại File: PDF | Số trang:74

Thêm vào BST

Báo xấu

393
lượt xem 93
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Tài liệu Bồi dưỡng học sinh giỏi Toán tổ hợp - Rời rạc được biên soạn dành cho học sinh chuyên Toán - Tin. Phần 1 tài liệu trình bày các nội dung: Ánh xạ và lực lượng của các tập hợp, đại số tổ hợp, lý thuyết đồ thị. Mời các bạn cùng tham khảo.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bồi dưỡng kiến thức cho học sinh giỏi Toán tổ hợp - Rời rạc: Phần 1

'^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 MCI I Danh cho hpc sinh chuyen Toan-„^in^ D M NHA XUAT BAN DAI HOC QUOC GIA HA NQI NAII
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; Tu duy ve toan roi rac ra doi rat som. O Trung Quo'c, vao thoi nha Chu Hanh chinh: (04) 39714899: Tona bien tap: (04) 39714897 nguai ta da biet den nhimg hinh vuong than bi. Fax: (04) 39714899 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 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 Gidmdoc- Tong bien tap : 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: pi Bi^n tap N G Q C LAM
Boi dudng hqc sink gioi Toan tohgrp - red rac, Nguyen Van Thong Cty TNHH MTV DWH Khang Vi^l 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 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. ' " • 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 - 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 . ^ , ,r 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 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 ^di toan2: >5,., •f>:v,i
Boi duanghQc sinh gioi Toan tohgp-rari r^c, Nguyeu //••,; Cty TNHH MTV DWH Khang Vi?t Day la ket qua ky thi Olympic toan quo'c te cua doan hpc sinh Vi^t Nam Ian . Qua qua trinh giang day cac lop chuyen Toan + Tin va ket hpp voi thii 47 tai Slovenia nam hpc 2006 (trich t u toan hpc va tuoi tre so'8/2006). 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 Bail Bai 2 Bai 3 Bai 4 Bai 5 Bai 6 S B D \ qua trinh giang day. Trong tai lieu nay, toi eiSng manh dan dua ra mot so khao VNl 7 sat mdi cua minh de tong quat hoa mpt so ket qua da biet. 0 1 7 3 0 VN2 7 1 7 6 7 0 T6NGQUAN :f^K'rWl':,:~::^ly/,r^,.. - VN3 7 1 7 7 7 0 Quyeh sach nay se dupe chia lam sau chuong. r i , VN4 7 0 1 6 1 0 Chuong 1: A n h xa va luc lupng ciia cac tap hpp. , X i ;j ; i 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 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 (Bang 2) thuong su dung trong giai Toan pho thong theo gioi han chuong trinh ciia Bp Bai 2 va Bai 6 la hai bai toan roi rac do nude (Serbia) de nghi. Ket qua ciia giao due. doan Viet Nam rat thap trong ky I M O Ian thu 47 to chuc tai Slovenia 2006. Chuong 5: Toan to hpp va thi HSG y g / \ Den nay ket qua I M O ciia chiing ta van chua c6 dau hieu tien bo, ma hpc Chuong 6; Nguyen ly Dirichlet - Djnh ly Ramsey ^ ,, , sinh van con lam tot cac bai toan Pi va Ps chuyen ve hinh hoc phang, con bai - Trinh bay theo quan diem ly thuyet voi nhung chung minh dinh ly, vi du 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. 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 STT Hp va ten PI P2 P3 P4 P5 P6 quoe gia, quo'c te. diem chuong - Chiing minh nhieu bai toan chia khoa, de nhin nhan van de don gian hon. 1 Nguyen Ta Duy 7 7 0 6 7 0 17 Bac 2 - Cac dinh ly ve to hpp thuong su dung phuong phap anh xa, phuong Dau Hai Dang 7 7 3 7 7 0 31 Vang 3 Nguyen Phuong Minh 7 7 0 6 7 phap song anh de chiing minh. 0 27 Bac 4 Le Quang Lam 7 7 0 5 0 0 19 Dong - Cac bai toan ve do thi dua vao logic de suy luan va chiing minh eo gang 5 Tran Hoang Bao Linh 7 1 0 5 7 0 20 Dong dua ra nhieu bai toan chia khoa de hpc sinh de ap dung va van dung. 6 Nguyen Hung Tarn 7 7 1 2 7 0 24 Bac Day la van de kho nhung tac gia mong muon gop phan minh vao ky nang (Bang 3 (Trich Toan hpc va tuoi tre so 8 - 2012)) lam toan roi r^c cho hpc sinh chuyen toan nen khong khoi tranh sai sot. Rat - Qua nhiing ky thi dinh cao, nhu vay, thi sinh d u thi toan la nhung hpc 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 Y la m p t song anh hay m p t anh xa m p t do'i m p t t u 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 CO m p t v a chi m p t x e X sao cho y = f (x) §1. A N H X A • Chang han anh xa d o n g nhat I x la m p t song anh v o i m p i X. 1.4. TfcH A N H X A . I.I.OINHNGHTAANHXA: ' ^inh nghla 1.4.1. ^inhnghia 1.1.1. •' ' >' ' Gia s u cho f: X Y v a g: Y -> Z. '« 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 Anhx? X->Z > • ' .^ m p t p h a n tvr xac d i n h y e Y, k y hi?u f(x). » s cr-" x-^g(f(x)) '^'f • I'M .f 1.2. A N H V A T A O A N H : _ » G p i la tich anh xa f v a anh xa g. K i hieu: g.f ^inh nghla 1.2.1. ^inhly 1.4.2. ' 1 " 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 Gia s u cho f: X ^ Y, g: Y, g: Y ^ Z, h: Z ^ T 3'- W ' 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: The t h i 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 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 . (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 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 'i>inhnghla 1.4.8. ' • - s:.v, ^.T ,inur- x e f"^ (b) g p i la m o t tao anh ciia b b o i f. Gia s i i f: X - » Y v a g: Y - » X la hai anh xa sao cho 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 gf = l x v a f g = l y 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: 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. Tir d i n h nghia ta suy ra f cung la m p t anh xa ngupc ciia g. v» B c f ( r ^ (B)) v o i m p i b p phan B ciia 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 nghla 1.4.4. ^inh nghla 1.3.1. A n h xa f: X Y CO m p t anh xa ngupc k h i v a chi k h i f la m p t song anh. 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') Chung mink G i a sii- f c6 m p t anh xa ngupc g: Y -> X keo theo q u a n h$ x = x', hay x ^ x ' keo theo f(x) f(x'), hay v o i m p i y e Y c6 Theo d i n h nghia ta c6: gf = I x v a fg = ly , 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 Tucla: - g(f(x)) = x v o i m p i x. v , , la m p t anh xa m p t d o i mot. Xetquanhe: f(x) = f(x') ^inh nghla 1.3.2. Tasuyra x = g(f(x)) = g(f(x')) = x'. 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, 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 = 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 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. toan anh f: X ^ Y la m p t anh xa t u X len Y. 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 X va ta thay ngay 8 9
Boi duong hQc sink gidi Todn tohipp - rai rac, Nguyen Van Thdnjj Cty TNHH MTV DWH Khang Vi^t gf = I x va fg = ly 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 1. H a i tap hiJTi h a n c i i n g so'lugng t h i t u o n g d u o n g . 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 , 2. H a i tap A = { 1, 2, 3, n, ...} va B = { 2, 4, 6, 2n, t u o n g d u o n g v i c6 Y g(y) = X, sao cho f(x) = y g the thiet lap phep t u o n g d u o n g l i n g : N g o a i anh xa ngugc nay, f con c6 anh xa ngugc nao khac khong? Ta c6: n I A I . Vay f-ig-^=(gf)-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. TAP HOP TUONG O JONG: 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 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 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: ' hai tap t u a n g d u a n g nhau. 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 N h u vay, neu tap A t u o n g d u o n g v o i m g t 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 bg phan ciia tap B t h i chi c6 the I A I < IBI hoac phantuciiaA. ly, •' .>vi l A I = IBI (ta vie't l A I < I B I ) . N o i each khac. 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 l A I < I B I , IBI < l A I l A I = IBI nay, tap A la v 6 han. Chung mink theo gia thiet c6 m g t phep t u o n g 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 li'ng 1 - 1 f giiia cac p h a n t u ciia A v a i cac phan 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). t u ciia m g t bg p h a n ciia B, va ngugc lai cung c6 Hinh 2 11
C t y TNHH M T V DWH Khang Vift BSi duang htfc sink gioi Todn tohgrp - rcri r^c, Nguyen Vin Thdng mpt p h e p tirong ung 1- 1 g giiia cac p h a n t u Vi du;Theo v i d\ 1 (a myc truoc), t a p |2, 4, 6, 2n, ...} la dem dupe. Ta cua B vai cac phan t u ciia mpt bp phan ctia A . s'< < ^ii ; ' ; ; cung thay ngay rang cac t a p { 3, 6, 9 , 3 n , ...), { 1 , 4, 9 , n ^ , . . . } , v.v ... deu dem Ta qui uoc gpi mpt phan t u x la "ho" cua phan t u y hay y la "con" cua x, dupe; t a p hpp cac so nguyen (bao gom ca so nguyen duong, am, va so khong) 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, C l i n g la dem dupe v i c6 the viet dual dang: 4;,; , y e A va y = g(x) (y ung vdi x trong phep tuong ung g). 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 Viec luc lupng dem dupe la lue lupng be nha't eiia cac t a p v6 han dupe xac day XI, X2, XK sao cho x la bo cua xi, xi la bo cua X2, X2 la bo ciia X3, XK la bo dinh boi hai dinh l i sau day: ciia y. Chang han trong hinh 2, x la to tien cua y dong thai x ciing la to tien ciia ^inh ly 22.1. ^ai cu t a p v6 han nao cung c6 mpt bp phan la t a p dem dupe. XI, X2, X3; XI la to tien ciia X2, xs; y, v.v... Bay gio ta hay chia A ra lam ba tap con: Chung minh; That vay, cho M la mpt tap v6 h^n. Ta hay lay mpt phan t u bat Ac gom tat ca cac phan t u ciia A c6 mpt sochSn to tien, A i gom tat ca cac phan ky, ai 6 M , roi mpt phan t u a2 e M \, roi mpt phan t u as e M \, 32), v.v... 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. Vi M v6 h?n, nen dieu do c6 the tie'p tyc mai va ta thu dupe tap dem dupe (ai, Dong thoi ta cung theo each do chia B ra lam ba tap: Be, Bi, B~. Sau do ta xac a2, as,...} c M. dinh mpt phep tuong ung cp nhu sau giua cac phan t u ciia A voi eae phan t u ciia ^inh ly 2.2.2. Mpt bp phan eiia mpt t a p dem dupe thi phai la h i m han hay B: voi moi phan t u thupc Ac hay A - thi cho ung con eiia no, vai moi phan t u dem dupe. thupc A i t h i cho ung bo ciia no. (i r? spi;:; Chung mink That vay, cho B la mpt bp phan ciia tap dem dupe A = { ai, a2, De thay rang (p la mpt phep tuong ung 1 - 1 giua A va B. That vay, trong as,...}. Gpi la phan t u dau tien ciia B ma ta g a p trong day { 8 1 , 8 2 , 8 3 , . . . } , a^^ phep tuong ung do, voi moi x e A d l nhien ung mpt phan t u duy nhat y e B. la phan t u t h u hai ciia B trong day so'do, v.v... Neu trong eae so' 11,12, ••• c6 mpt 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 so Ion nhat, v i du ip, thi B = { , a^^a,^ ] la hihi han. Con neu trai lai day la y la con ciia mpt phan t u x nao do thupc Ac; con neu y e B - thi bo' ciia no , a i 2 k e o dai v6 tan thi B = ( ,a^^.....} la dem dupe. ' ' thupc Aoo, nghia la y la con ciia mpt phan t u x nao do thupc A - . Thanh t h u moi ^inh ly 2.2.3. H p p ciia mpt hp huu han hay dem dupe t a p dem dupe cung phan t u y e B ung voi mpt phan t u duy nhat x e A trong phep tuong ling (p. la t a p dem dupe. ^* " Vay (p la mpt phep tuong l i n g 1-1 giua A va B. Chung mink Cho mpt day tap dehi dupe: A i , A2, A3... Ta hay viet eae phan tu Tir dinh ly nay ta suy ra rang cho truoc hai tap A , B, chi c6 the xay ra mpt eiia moi tap ay thanh mpt day va xep dat cac day thanh mpt bang nhu duoi day. trong 4 truong hop: R6 rang tren moi duong cheo (c6 miii ten) chi eo mpt so hiiu han phan tu: tren 1. lAI = IBI • K''^' ->niVx F] duong cheo thu nhat chi c6 a n , tren duong eheo thu hai chi c6: 821,812, v.v... noi 2. l A I < IBI ^ J"r?>v chung tren duong cheo thii n chi c6 n phan tu (eae apq ma p + q = n +1). •j; 3. IBI < l A I ^iyjy^ .(;• .XA& • Ai ^ ^11 ^ ^12 >^^13 ^^ ^14 4. A khong tuong duong voi B, hoac bo phan nao ciia B, va B cung khong ^23 324 tuong duong voi bp phan nao ciia A . A3 ^332 ^ ^33 334 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, Veiy ta CO the Ian lupt danh so cac phan tu" tren duong eheo thii nhat, roi cung CO the noi: Mpt tap dem dupe la mpt tap ma ta eo the danh so dupe cac den duong cheo t h u hai, v.v... phan t u ciia no thanh mpt day v6 han: a i , a 2 , a 3 , a n , . . . ^inh ly 2.2.4. Khi them mpt tap hpp hixu han hay dem dupe vao mot tap v6 hcin M , ta khong lam thay doi luc lupng ciia t^p M . 12 ' 13
Boi duang hoc sink gidi Todn tohgrp - rcri r^c, Nguyen Van Thong Cty TNHH MTV D W H Khang Viet Chung minh:Cho N la tap thu dugc khi them vao M mQt tap A hiru han hay 2.3. Ll/C LUQNG CONTINUM: dem dxxoc. Theo Dinh ly 2.2.1 c6 the lay mot tap dem dugc B cz M . Dat M ' = 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, M\B, ta CO M = M ' u B, N = M ' u B u A. Theo dinh ly truac B u A ciang la dem roi den tap cac so dai s6^ moi tap bao gom v6 so phan t u moi so voi cac tap da dugc, cho nen c6 the lap mot phep tuong ung 1-1 giiia B va B u A. Sau do chi xet truoc, the ma luc nao ta ciing chi c6 nhiing tap de'm dugc. Vay thi c6 tap can lap mot phep tuong ung 1- 1 giiia M ' va chinh M ' , ta se c6 mot phep tuong nao khong de'm dugc khong? ling 1-1 giiia M va N . N h u vay M va N cung luc lugng. ^inh ly 2.3.1. Tap cac so thuc la khong de'm dugc. Theo dinh ly nay, ta thay rang tap cac diem thugc mot khoang (a, b) Chung mink V i tap cac diem thugc doan [0, 1] tuong duong voi tap cac tuong duong voi tap cac diem thugc doan [a, b]. Vay tap cac diem thugc doan diem tren toan duong thSng, ta chi can chung minh rang tap cac diem thugc [a, b] tuong duong voi tap cac diem tren toan duong thang. do^n [0,1] la khong dem dugc. ^inh ly 2.2.5. Tap tat ca cac day hiiu han c6 the thanh lap dugc voi cac phan Gia sir trai l^i rang tap do de'm dugc, nghla la c6 the danh so' thanh day: t u ciia mot tap dem dugc la dem dugc. Xi,x2,X3,... ta hay chia doan [0, 1] thanh ba doan bang nhau. Trong ba doan do Noi ro hon, cho A = {31,82,33,...} la mot tap dem dugc, S la tap tat ca cac phai CO mgt doan khong chua x^: cho doan ay la . Ta lai chia ra ba doan day CO dang (a^^, HJ^ , . . . , 3 ; ^ ) trong do m la mgt so' t u nhien bat ky, a^^ (k = 1, 2, bang nhau. Trong ba doan do phai c6 mgt doan khong chua X 2 : cho doan ay la m) la nhiing phan t u (khong nhat thiet phan biet) ciia A. Ta khang dinh A2 . Ta lai chia A 2 ra ba doan bang nhau, v.v. Tie'p tuc mai, ta se c6 mgt day doan rang S la dem dugc. Aj 3 A2 3> A3 3 Chung mink Ggi Sm la tap cac day gom dung m phan t u ciia A. Voi do dai I A„ 1= va voi x^ g A ^ . V i I A „ I - > 0 (n -> °°) nen do la mgt ' ViS=U-.iS„ 3 Nen theo Dinh ly 2.2.3 chi can chung minh rang moi Sm la de'm dugc. Voi day doan that lai va theo nguyen ly Cantor, phai c6 mgt diem ^ chung cho tat dieu do hien nhien v i rang = A. Ta hay gia thiet dieu do diing voi ca cac dogn ay. Co' nhien ^ e [0, 1]. Vay ^ phai triing voi mgt x^^ nao do. (hie de'm dugc), va chung minh cho S^^^. 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 cac doan A „ . Do do gia thiet rSng tap cac diem thugc [0,1] de'm dugc la v6 ly. dang (Hj^ ,3(2 , . . . , 3 ; ^ , 3 k ) . Giiia s[^+i va ro rang c6 su tuong ung 1-1. 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. y: (aii'ai2'aim'3k)
Boi dumtg hpc sink gidi Todn td'hgp - red n^c, Nguyen Van Thong 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 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 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 . do la A ' 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. if 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 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 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 . 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 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 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 . 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. 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 2.4. Lyc LLTONG 2 " : '^v'' ' - ••AM.A H ..n mt,: 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 ' 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 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 tap cac ban so. . ; . . « 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 : ,a2'-.^n v o i m o i b p p h a n M ciia so n g u d i quen ciia A . A ta CO the cho u n g day ( ^ i , ^ 2 ' - ' ^ n ) t^ong d o = 0 neu 3 ; ^ M va = 1 neu mtodn3.2.(TrungQuoc-1997). * 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 Trong cac xau nhi phan c6 do dai n, goi a^, /« so cac xau khong chiea 3 so 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 lien tiep 0,1, 0 va \ so"cac xau khong chtta 4 so lien tiep 0, 0,1,1 hoac 1,1, 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 . 0,0. Chihtgminh rang: = 2a^. V g y S g o m 2" p h a n t u : I S I = 2" . Loi giai >,.-n. 4 i-t •(••••Vsv™:,*.! - 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 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 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°'. 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 , 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: 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 §3. C N G D U N G A N H X A D E G I A I 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 M O T SO BAI TO AN ROI R A G ^ ^ ' k h i va chi k h i f(X) thupe B. ' * 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 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 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 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 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 y t u o n g d o ta t i m d u p e l a i giai cac bai toan sau: ~> 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 ^di todn 3.1. / bat d a u b a n g so'O. T i r d o ta ed d p e m . Mgt cuoc hgp c6 n nguai: Mgt so nguai trong ho khong quen hiet nhau, dong 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 thai cH moi cap 2 nguai khong quen nhau lai c6 dung 2 nguai quen chung, con 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 hai nguai quen nhau lai khong c6 nguai quen chung. Chttng minh rang moi mgt 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 . ,» con ngupi trong cugc hgp c6 mgt so nhu nhau nhung nguai quen. ^ d i todn 3.3. (Vd dich Ucraina - 1996) Lin giai Ggi M la so cac songuyen duong viet trong h? thap phan c6 2n chit so, 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 ^ong do CO n chit sol vd n chit so 2. ggi N la so tat cd cac soviet trong h? thap 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, , A j , A ^ (n > k) la phan CO n chit so, trong do chi c6 cac chU sol, 2,3, 4 vd sochUsol hang so chU 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 so 2. Chiing minh rhngM = N. \'^{i'^^p]\m B i N H THUAN 17
Cty TNHHMIV f H VHKhangVift Lai giai ^ai todn 3.5. Vai moi so' c6 n chiJ' so' gom cac chu so 1, 2, 3, 4 va so' chu so 1 bang so' chu Chiing minh rang vai m, n, k e , m > k thi: so'2, ta "nhan d o i " thanh so'co 2n chu so'theo quy tac sau: dau tien, hai phien '-m+n+l-^m*-n+^m-l'-n+l+-+'-m-k%+k , ban cua so' nay duQc vie't ke nhau thanh so' c6 hai chu so', sau do cac chu so 3 6 Loi giai 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: Ta de'm so cac bg so nguyen T = (a^.^z.-.a^+n+i-k) vai 1234142 12341421234142 ^ 12121221221112. l < a i 0 2
Bdi duong hpc sink gioi Todn to hap - rdi r^c, Nguyen Van Thong Cty TNHH MTV DWH Khang Vi$t m Lin giai N h u vay Cn+k 2""" la so tap con ciia S c6 n h i e u h o n n p h a n t u . k=0 D o f la m o t song a n h t u (1, 2 , n ) vao {1, 2 , n ) n n 1 n -1 T u a n g hx X'-'m+k^"'^ la so tap con ciia S c6 nhieu h o n m p h a n t u , cung (1) y J _ = ky= li' k=0 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 . f(n) V^y Xm Cn+k 2"'"'' + Z n Cm+k Z"""" la so tat ca cac t^p con cua S, tuc la 2'"+"+^. f(l) f(2) va k=0 k=0 1' 'V 2' D o c h i n h la d i e u phai chxmg m i n h . , , , i »t I in n 1 f(k) 1 n -I todn 3.8. (VMO - 2002) Ta d u o c (2) l kI =-i f' W ^ k Cho tap S gom tat cd cdc so"nguyen trong doan [1; 2002]. Got T Id tap hap ktiVk^ m) tat cd cdc tap con khong rong cua S. Vdi moi X thugc T, ki hi^u m(X) Id trung Tu (1) va (2) ta suy ra: ^ — > ^ i ; „ .•-.-^tls :>«ysi ivJ*::.::,, b k=l k k=l binh cgng cdc phdn tit cua X. Tinh m = ^ f(2) 1 f(n). (Tong l a y theo tat c a cac tap X thuQC T). '^'^ • .8 6 • i t e J 5fa>^ 'i 2^ "^(2) n2 V f M M Xay d u n g s o n g a n h f: T ^ T n h u s a u : f(X) = {2003 - x |x6X}, V X E T . R6 r a n g n = l (X) + m ( f ( X ) ) = 2 0 0 3 . D o d 6 : ' a n ' " ' Vfrn f(l)_f(2)_ f(n) g'"' 2;Xni[X)=2(m(X) + ( f C X ) ) ) H T | . 2 0 0 3 ^ m = 2 ^ = ^ ^di todn 3.9: 1=1 Hay tinh trung binh cgng tat cd cdc so Ngom 2002 chit sothoa man N: 99 n = l vd cdc cha so"cua N thugc {1, 2,3,4, 5, 6, 7,8}. D a u bang xay ra f ( i ) = i , V i = l , n ,;,(/> < v ^ •, Loigiai I ^ ^ d i todn 4.1:(IM0-1985) G Q I M la tap cac so N thoa d i e u kien de bai. , Gid sic n Id mot sotyc nhien, k Id mot so nguyen to vai n,l - • k=i k^ i ^ k D i e u k i e n 2) v a i) cho ii) f(a) = f ( a ^ ) , Va e Z fa- 20 21
Cty TNHH MTV DWH Khang Vi?t Boi duang hgc sink gioi Todn to hap - rcri rac, Nguyen Van Thong Vay vai mpi so nguyen m do ii) c6: f((m + l ) k ) = f[(m + k)k - k) = f(mk) Trong mgt so bai toan de'm, dinh l i tren thuang dugc ap dung bang each: 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) (n 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 tap hap T cdc nhd todn hge nude ngodi thoa man cdc tinh chat sau: mgt i e {1, 2 , 2 n - 1}. Chicng minh rang moi n, so hodn vi ed tinh chat P Idn 1. Cdc nhd todn hge quoc gia X thugc S chi gid thu eho cdc nhd todn hgc han so hodn vi khong cd tinh chat P. Lai giai nude ngodi khong thugc tap hap T. 2. Cdc nhd todn hgc nude ngodi thugc T chi gtti thong diep cho cdc nhd todn (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 hgc quoc gia X khong thugc S. ciia {1, 2, 2nl c6 tinh chat P; C la tap tat ca hoan v j ciia {1, 2, 2n} khong c6 Loigiai i •(-•">: ^ • r. tinh chat P. 1 Gpi A la tap hgp cac nha toan hpc cua quoc gia X va B la tap hgp cac nha Ta chia cac so 1, 2 , 2 n thanh n cap sau: (1; n +1), (2; n + 2 ) ; ( n ; 2n). toan nuac ngoai. Goi f: A -> B va g: B A la cac anh xa dinh nghia nhu sau: Gia su (x^; X 2 ; . . . ; x^^i; X;^; Xj^^^;...; X 2 n ) la mgt hoan v i thugc C. f(a) la nha toan hpc nuoc ngoai nhan thong di^p ciia a va g(b) la nha toan hoc Gia su la so'ciing cap vai X 2 n , suy ra k < 2n - 2. , cua quoc gia X nhan thong diep cua b. Neu cac tap con S va T ton tai thi T = B\ Ta xay dung anh xa f : C B nhu sau f(S). Vay ta phai chung minh ton tai mot tap S c A sao cho A\ = g(B\f(S)). Vai X = (x^, X 2 , X i ^ _ i , X|^, X | ^ ^ l , X 2 n ) -> Y = ( X j , X 2 , , , >-• '^k+l ) m6i tap con X c A, goi h(X) = A\g(B\f(X)). Neu X c Y thi. ' v;;f(x)cf(y) ^B\f(Y)c=B\f(X) De tha'y rang f la don anh va f khong phai la toan anh. . ; =>g(B\f(Y))cg(B\f(X)) That vay, xet yo = (x^, X2 x^-i • ^n+i • ^n+i 2n ) =>A\g(B\f(X))c:A\g(B\f(Y)) 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. > i M = n(2n-l)! 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 J^MnxetTa c6 |C|n|B| = 0 ma |C|+ |B| = |A| = (2n)! nen |B! 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. C| < n(2n - 1)!. T u do dan den each chung minh t h u 2 sau: Vay S = X e M n X khac rong. Theo dinh nghla cua S ta c6 h(S) c S. Theo tinh (ii)Cach 2. Ggi Aj^ la tap tat ca hoan v i thoa man k va k + n dung canh 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 nhau, A la tap hgp tat ca cac hoan v i c6 h'nh chat P. Suy ra A = (JAJ^ . cac ket qua tren ta c6 S = h(S) (dpcm). Theo nguyen ly bao ham loai tru, ta C O Sir dung mgt so tinh chat ciia anh xa A=y:Ak-yKnAhK I |AknAhnAj-...>SK|-IKnAh Cho A va B la hai tap hCru han. k k
Boi duang hoc sink gioi Todn to hap - roi rac, Nguyen Van Thong Cty TNHH MTV DWH Khang Viet Do do ta C O the chi ra 6 truong hop khi xay dung An+4 • T u do xac dinh Vi v^y A| > 2n(2n - 1)! - ^^^^^^ • 4(2n - 2)! = 2n^ (2n - 2)! > ^ dugc An la duy nha't. T u do ta C O dieu can chiing minh. Do do anh xa tu An den An+4 ^"h. ^di todn 4.4. (Romania TST 2002). Vai moi so nguyen ducmg, ta goi f(n) la so Mat khac vol moi A n ta xac dinh dupe duy nha't mpt , voi moi En cung each chon cac dau +, - trong bieu thiic: = ± 1 ± 2 ±... ± n sao cho En = 0. Chiing xac dinh dupe duy nha't mpt An . minh rang (a) fin) = 0khin^l,2 (mod 4). Do do f(n + 4) > 4f(n). ta c6 f(3) = f(4) = 2. Suy ra ' +1 + f(4k + 3) = f ( ( 4 k - l ) + 4 ) > 4 f ( 4 k - l ) > 4 ^ f ( 4 f - 5 ) > . . . > 4''f(3) (b) Khi n=0,3 (mod 4) ta c61 — ' — ^ »K ' la T, so tap can la C. Chiing minh rang: T+C< 2^""^ +1 , .,»- 1' ^jf't.' Do do f(n) < 2"-^ = 2" - 2""^
Boi duang hoc sink gioi Todn to hap - red rac, Nguyen Van Thong Cty TNHH MTV DWH Khang Viet Suy ra B2I = |Y\M2| = |Y| - IM2I = n - IM2I = | M I | . D O d o B la m p t tap can hay f la toan anh. V i vay f la song anh. T u d o suy ra so tap can la C^n • DAI s6 T 6 H O P fj • T i n h so'tap to't: §1. PHfiPDEM Gia su C la m o t tap tot ciia A . 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 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 G p i F la hQ talt ca tap tot ciia A . /' 1 ; t / p). [g(x)+m neu X E B Giasu{ai, 82,..., an} = { b i , b,,, p ^ i . t ^ ; . . . ; p'"'.tt) Ta c h i i n g m i n h h la song anh: 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 V x i , x 2 e A w B , h ( x i ) = h(x2) v i do A n B = 0 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 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) 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 ma k h o n g c6 so' nao chia het cho p^. ^ ^1 = ^2 ( V i f, g deu la song anh) Xet anh xa sau: f : M N Vay anh xa h la d a n anh. *;A • V- ' • '''' 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 {ai, a^} h-> bi,b2 bi,,pti,pti,...pti,pt2,pt2,-pt2,-.Ptt>Ptf-Ptt 2 , m + n) d e u c6 tao anh nen h la toan anh. V a y h la song anh. p-J^ so p h : A u B -»{1, 2 , m + n} la song anh hay | A U B | = |A| + |B 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 .
Cty TNHH MTV DWH Khang Viet Boi duang hqc sink gidi Todn to hap - rbi rac, Nguyen Van Thong 1 4. QUY TAG N H A N G H O n TAP HOP. 1.2. QUY TAG C O N G GHO n TAP HOP; Neu A i , . " , A n la cac tap h u u han bat ly va AjX...xAn la tich De-cac cua cac Neu 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 =0 t^pd6,thi | A I X A 2 X . . . X A „ | = |AI||A2|...|A„| , neu i ; ^ j , t h i A;^ u . - . u A ^ = | A I | + | A 2 | + . . . + A ^ ] , Chung minh 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 6 day JAjj la luc l u g n g (so cac p h a n ttr) cua tap A j . 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 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 , 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 ...,Ak,Ak+i la k + 1 tap h i r u han bat ky. K h i do gia thiet q u i nap. q u i nap theo n, ta c h u n g m i n h rang: A^ u . . . u A n = A^ +...+ A„ . A i X...XAk XAk+i I = |(Ai X...XAk)xAk+i 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 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 = |(Ai X...XA |Ak+i|- |Ai| |A2|...|Ak||Ak+i cho n = k > 2 va Ai,...,A|^+i 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 J^an xet qui tdc nhdn: ; ^ . ..^ . (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: 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, AiU...uAkUAk+i =|(AiU...uAJuAk+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 +...+ + Bj each thuc hien. K h i do hanh d g n g H c6 ca thay ai,a2,...,an each thuc hien. ,j 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 Chicng minh: h i f n. K h i do h a n h d g n g H : hoac xay ra, hoac H2 xay r a , h o a c H„ xay ra, Giasu X = {xi,X2,.Mk} ! C O ca thay +...+an each thuc hien. Y = {yi,y2 y^} 1.3. Q U Y T A C N H A N : « 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 X X2 •• Xj ... Xk C h u n g m i n h : Gia s u |A| - m, |B| = k va . , f(x) f(Xl) f(X2) f(Xi) A = {ai,a2,...,a^}, B = {bi,b2,...,bk}. f(Xk) T i c h De-cac A x B g o m cac cap (aj.bj), 1< i < m, 1< j < k , c6 the v i e t thanh D o n g t h u hai f ( x i ) , f ( x 2 ) , f ( X k ) la m g t day k p h a n t u cua Y. N o la m g t bang chir nhat c6 m d o n g k cgt n h u sau. /• 5 >i Ji'i I » J mgt p h a n t u ciia rich De-cac Y x Y x Y x x Y = Y"" (ai-bi), (ai,b2)...(3i,bk) ' ' u w/., Dao l a i , m g i day k p h a n t u cua Y la (y„^ ,y^^
Boi duong hoc sinh gioi Todn to hop - rcri rac, Nguyen Van Tfiong Cty TNHH MTV DWH Khang Viet 1.5. C A C Vf DU MINH H O A . ChOng minh: | A | + |B| la s o ' t i m duoc k h i ta de'm t r u a c he't so'tat ca cac phan Vi du l:Mot ban ddi c6 2 day ghe dot dien nhau, moi day gont c6 6 ghe. ^ cua A r o i sau d o so tat ca cac phan t u B. N h u n g k h i do, so p h a n t u chung Nguai ta muon xep cho ngoi cho 6 hoc sinh trudng A va 6 hoc sinh truang B 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 vao ban noi tren. Hoi c6 bao nhieu each xep cho ngoi trong moi truang hap sau: | A | + | B | = | A u B| + | A n B| | A u B | = | A | + | B | - | A n B a) Bat ki 2 hgc sinh ndo ngoi c^nh nhau hoac dot di?n nhau tht khdc t,) T n r t m g h
Boi duang hgc sinh gidi Todn to hop - rai rac, Nguyen Van Thong Cty TNHHMTV DWH Khang Viet Lai giai Nen (TnL)+(LnV)||L| + |S| + |L| + |S 3 Suy ra |TnL| + |LnV| + |TnS| + |SnV|>|L| + |S| (2) gioi a mon Vat ly; ; H 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 • Han - so'hgc sinh dat diem gioi & mon Vat ly cUng dong thod dat diem dugc chung minh ^ ^, , .^j,, ,^^^., ,. . 3 §2 T O H O P KHONG LAP gioi d mon Van; « Han -2 so hgc sinh dat diem gioi a Van cung dong ^ thai dat dieM giai a jVhan x^t: Gia su mgt dgi quan vgt c6 muai cau thu huan luy|n vien can mon Lich sit; chgn nam nguai di thi dau a mgt truong khac. Ngoai ra ong ta cung chuan bi e Han - so hgc sinh dat diem gioi a mon Lich sii cung dong thai dat diem mpt danh sach c6 thu tu gom bon cau thii de tham gia bo'n tran chai don. 3 Trong muc nay ta se nghien cuu cac phuang phap de'm so each chgn khong c6 gioi a mon Todn; thii tu nam cau thu de di thi dau va c6 danh sach khac nhau gom bon cau thii Chicng minh rang trong lap hgc noi tren c6 it nhat mot hgc sinh dat diem tham gia tran choi don. ^ gioi cd ban mon Todn, Vat ly, Van vd Lich SM'. Tong quat han, chung ta se trinh bay cac phuang phap de'm so each chgn (De thi MSG Quoc gia THPT Bang B-2005). khong CO thu tu cac phan tu khac nhau va nhirng sap xep c6 thii tu cac do'i Ldi giai hrgng cua mgt tap hiiij han. Ki hi|u T, L, V, S Ian lugt la tap hgp cac hoc sinh gioi Toan, Vat ly. Van, 2.1. T6 HOP (J6 HOP KHONG LAP) Lichsu. y'y •(•If Theo - T , ta c6: L n V > - | T n Lde> bai, (*) So'tap con ciia mgt tap hop c6 m phan tu. ' 3 3 V n S > 3— V S n T > 3— Cho t^p hgp A c6 m phan tii. Ta hay xet xem tap hgp tat ca cac tap con ciia Ta giai bai toan bang phuang phap phan chung. ^O/ T(A), CO bao nhieu p h a n tu. Gia su.khong c6 hgc sinh nao dat diem gioi 6 ca bo'n mon Toan, Vat ly. Van ^
Boi dtithi}; hoc sink gioi Todn to h
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 Mg'u n la chan, n = 2 m , t h i m-i , do do
Boi duang hpc sink gioi Todn tohqp - rcri rac, Nguyen Van Thdng Cty TNHH MTV DWH Khang Viet 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! thang, trong do c6 m doan ngang, n doan doe. Cac duang ay chi khae nhau boi So' each chon 6 nguoi toan nu: Cg = 28 6!2! thii t u ke'tie'p eiia eac doan ngang va cac doan dpc. Vi vay so tat ea cac duong Do do so' each chgn to eong tac de c6 nam Ian nvt. 3003 - (1 + 28) = 2974. jigan nhat t u diem (0, 0) tai diem (m, n) bang so each ehpn n doan dpc t u m + n b) Cdchl: '^ ' ' " " = ' do^n dpc ngang, hie la bang Cj^+n . So each chon A n lam to truong va khong eo Binh: I.C12 = N h u vay, so Cj^ = c|^^_^)^,^ c6 y nghia hinh hpc nhu sau: Do la duang ngan 11! nhat tir diem (a 0) tai diem (m - k, k). ^ 'M " ' ' . So'each chon A n lam to vien va khong c6 Binh: IZ.Cn - 12.-^^ = 3960 Chii y: Ta eung eo the xet so' each ehpn m doan ngang thay cho n doan dpc. Vay so'each chon CO A n ma khong CO Binh: + IZC^^ = 4752 Khi do so duong ngan nhat t u diem (0, 0) toi diem (m, n) se la Cj^^^ . N h u vay Tuong t u so'each chpn c6 Binh ma khong c6 A n cung la: + 12Cji = 4752 ta da chung minh dupe bang hinh hpc dang thuc C^^^ = Cj^+n. Zi So each chon khong eo A n Ian Binh: 12C^i = 1 2 - ^ = 5544 2.5. MOT S 6 TINH CHAT QUAN TRONG C U A C A C S6 . Do do yeu cau bai toan: 2(0^2 + UC^i) + UC^^ = 2(4752) + 5544 = 15048 2.5.i.Ne'u 0 < k < m t h i (2) Cdch2: x ; , ,// Cong thuc nay dupe gpi la quy tac do'i xung. Chon tuy y 6 trong 14 hoc sinh eo: each. Chicng minh: Chon A n va Binh roi chon them 4 hoc sinh trong 12 hoc sinh eon lai c6: C^2 each. Cdch 1: Theo y nghia hinh hpc cua so' cJ^=cL_|^wk, ta da thay rang Vay so' each chon 6 hoe sinh do A n va Binh khong dong thai c6 mat: C(m-k)+k = • chinh la cong thuc (2) Cdch2:Neu dimg eong thuc (1) thi ta eo ngay Vol 6 hoc sinh da chpn xong c6 6 each ehpn ra to truong. „m-k m! m! =C Vay so each ehpn thoa yeu cau de toan la: sicf^ - ^ 1 2 ) = 15048 each. {m-k)!(m-(m-k)!) (m-k)!k! 2,4. Y NGHlA HINH HOC CUA = cf^.^j.^ • V nghia tap hop eua eong thuc (2) nhu sau: Gia su tap hop A c6 m phan tu. Ne'u B mpt tap con k phan t u eiia A, phan bu B eua B trong A la mot tap con Xet mot mang duang hinh chir nhat kich thuae m x n, tao thanh bai nhiing (m - k) phan t u cua A. N h u vay giira tap hop cac tap con k phan t u ciia A va hinh vuong, ngan each nhau boi n - 1 duong ngang va m - 1 duong dpc nhu tap cac con (m - k) phan t u eiia A c6 mot tuong ung 1 - 1. Do do so' tap eon k tren hinh ve. Ta hay tim so duong ngan nhat tren mang duang do de di t u goc phan tu bang so'tap con m - k phan tu. Dieu nay dupe dien ta boi eong thiie (2). dual ben trai diem (0, 0) tai goc tren ben phai (diem (m, n)). •2.5.2. Ne'u m va k la nhiing so t u nhien sao cho 1 < k < m - 1 thi ta c6. (0,n)- pk _ p k - l pi (m, n) -m-1 (4) Cong thuc nay dupe gpi la quy tac Pascal Chung minh: (m-1)! (m-l)!k £a£lLl: ViC;;-_\ (k-l)!(m-k)! k!(m-k)! \ ) (m-l)! (m-l)!(m-k) Va C m - l (m, 0) X k!(m-l-k)! k!(m-k)! •58