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 2

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

Thêm vào BST

Báo xấu

257
lượt xem 87
download

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

Nối tiếp nội dung phần 1 tài liệu Bồi dưỡng học sinh giỏi Toán tổ hợp - Rời rạc, phần 2 giới thiệu tới người đọc các kiến thức: Tô màu đồ thị, các bài toán rời rạc, tổng hợp và toán thi, nguyên lý Dirichlet - Định lý Ramsey. Mời các bạn cùng tham khảo nội dung chi tiết.

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 2

Cty TNHHMiV DVVH Khang Viet Boi duang hoc sinh gioi Todn to hap - roi rac, Nguyen Van Thong qua sai khong? L i l u a n cua hp c6 thuc su la m o t c h u n g m i n h hay k h o n g , ne'u no p h u thuoc vao t h o n g t i n tir m p t may t i n h k h o n g d a n g t i n cay? Lam Bai toan b o n m a u ap d u n g chi cho cac d o t h i phang. Cac d o t h i k h o n ^ p h a n g CO the c6 so'mau Ian t u y y n h u se c h u n g m i n h t r o n g v i d u 2. Nau Can p h a i l a m hai dieu k h i c h u n g m i n h so mau cua d o t h i la n . T r u o c tien, c h u n g ta phai c h u n g to rang do t h i c6 the dugc to bang n m a u . D i e u nay c6 t h e Luc f Lam Luc /Lam thuc hien b a n g each to m a u d o thj do. Sau do c h i i n g ta p h a i c h u n g to rang G H k h o n g the to m a u d o t h j v o i so m a u it h a n . Cac v i d u sau day m i n h hoa each H i n h 4. To m a u do thj G va H . . ;• ' t i m so'mau. Vi du. 2: Tim so mau cua do thj Kn. 'S,'-'' '"^ Vi du 1: So mau cua do thi GvdH tren htnh 3 bang bao nhieu? L a i giai ' ' L o i giai Co the xay d u n g each to m a u d o thj K n v o i n m a u khac n h a u . Co each to So'mau cua G i t nha't la 3, v i cac d i n h a, b va c p h a i d u p e gan cac m a u khnr mau nao d i i n g i t m a u h o n khong? Cau tra l o i la k h o n g . K h o n g c6 hai d i n h nao n h a u . De tha'y G c6 the to bang ba m a u ta gan m a u d o cho a, m a u l a m cho b va CO the gan c i i n g m a u v i m p i cap d i n h ciia d o thj nay deu lien ke. V i the so mau m a u luc cho c. k h i d o d c6 the (va phai) to m a u d o v i no lien ke v o i b va c. Tiep ciia K n bang n . ( N h o lai rang K n la k h o n g phang ne'u n > 5, v i theke't qua nay theo e CO the (va phai) to m a u luc v i no lien ke v a i cac d i n h m a u d o va m a u luc. khong m a u t h u a n v o i d j n h ly bo'n mau). Cach to m a u K5 bang 5 d u p e the hien Cuo'i c i i n g , g c6 the (va phai) to m a u d o v i no lien ke v o i cac d i n h m a u l a m va tren h i n h 5. m a u luc. V a y la ta da to m a u d o t h j G bang d i i n g ba m a u . H i n h 4 the hien each to m a u n h u the. D o t h i H d u p e tao nen tLi* d o t h i G bang each t h e m vao m p t canh n o i a v o i g. m p i y d i n h to H bang ba m a u can phai tuan theo l i l u a n da d u n g k h i to mau G, t r u giai doan cuo'i cung, k h i cac d i n h khac g da d u p e to m a u . V i g lien ke (tron;; H ) v o i cac d i n h m a u do, m a u l a m va m a u luc nen ta ta bupc phai d u n g mau nau t h u t u , chSng han m a u nau. V i the H c6 so m a u bang 4. Cach to m a u U the h i ^ n tren h i n h 4. ^ lam vang H i n h 5. To m a u d o t h i K 5 . H i n h 6. To m a u d o thj K 3 4 . Vi du 3: Tim so mau ciia do thi phan doi day du K „ trong do m va n la f«c songuyen duang. L a i giai H i n h n h u so m a u can thiet p h u thupc vao m va n . T u y nhien, ta chi can hai Utau. To tap m d i n h b a n g m p t m a u va tap n d i n h bang m a u khac. V i m o i canh ••^i n o i cac d i n h tir tap m d i n h t o i d i n h thupc tap n d i n h nen k h o n g c6 hai d i n h ii'^n ke nao c i i n g m a u . H i n h 6 the hien each to m a u d o thj K3 4 . H i n h 3. D o t h i G va H 149
Moi dan do thi phan doi lien thong c6 so' mau bang 2 hoac 1, vi li le nhu ^5ng i " ^ " ^^y' ^' *° P^^" hoach tap dinh cua do jj^j thanh k lap dinh dong mau. trong vi d^ 3 ap dung duoc cho moi do thi nhu the. Ngu^c lai, mpi do thj c6 so mau bang 2 deu la do thi phan doi. Sac so ciia mpt do thi G, ky hi^u la , la so tu nhien k nho nhat de G c6 Vi du 4:So"mau cua do thi Cn Id hao nhieu? (Nho lai rang Cn la do thi vdtig k-to mau. Do thi G dupe gpi la do thi k-to mau dupe neu x(G) S k va dupe vai n dinh). ,i 1^ k- sac neu x{G) = k. ... :„( & ; - ,^ :• Giai: Truoc tien, ta nghien cuu mot vai truong hg-p cu the. Gia su n = 6. lay 1 2 1 2 1 3 2 1 3 ra mpt dinh va to no bang mau do. Di theo chieu kim dong ho ciia do thi -Q- -o O- -O O- -O o- -o- -O- phang tren hinh 7, can gan mau thii hai, chang han mau xanh cho dinh tiep theo, cu tiep tuc nhu the theo chieu kim dong ho, dinh thu ba c6 the to mau do, o- 6- -6 O- dinh thii tu to mau xanh dinh thii nam to mau do va cuoi cung dinh thu sau c6 1 2 4 (a) the to mau xanh. Vay so mau cua la 2. (b) (c) (d) Hinh 1: Dimg cho Vi du 2. Vi du 1: Gia su G la do thi cap p. Khi do, hien nhien la G c6 p- to mau va ^(G)-t6mau. V.'.',< ang mau do. khong CO mpt canh nao. Cac do thj 2- sSc dupe mo ta boi dinh ly duoi day. Dinh tiep theo chieu kim dong ho mau xanh, cu tiep tuc ta dugc dinh d mau 'i>inh ly 1 (Konig, 1936). Gid su G = (V, E) la mot do thi bat ky. Khi do cac khang xanh. Dinh thu nam, dinh e, khong the to mau do hoac xanh duoc vi no lien ke ^inh sau day la tuang duong nhau: voi cac dinh c6 mau xanh va do. Do do can mau thu ba cho dinh nay, chSng '^^'(a)Glcidothi2-sdc; ' ' ' ^ _ ' * (f . han mau vang. Vay so mau cua C5 la 3. Xem hinh 7. < (b) G la do thi 2- phan khac nhau do thi rong; (a): Gia sii G la do thi 2- phan khac do thj rong. Ta cung gia sii rang han hoac bang k thi to mau do cijng duoc goi la k- to mau. Tap tat ca cac dinh ^1 va V2 la cac phan ciia G. Ta to cac dinh ciia bang mpt mau va to cac dinh duoc to bai cung mpt mau trong mpt to mau ciia do thi dupe gpi la lop dinh |ia V2 bang mpt mau khac. Khi do ta nhan dupe mpt 2- to mau ciia G vi G la - 151 150
BUI uuim}( nyi Kinn j j i u i i UUH W nop - rm rae, i\^ym van inong — do t h i 2- p h a n . M a t khac, G k h o n g c6 1- to m a u v i no la d o t h i khac d o t h i ronjv nhat v o i / ( H ) = k. N h u vay, x ( H - v ) = k - l cho m o i d i n h v cua H . suy ra, Vay x(G] = 2 va G la d o t h i 2- sac. deg(v) > k - 1 cho m o i d i n h v ciia H . D o do. 5(H3>k-l va v i the: 3. (b) => (c): Gia s u G = (V, E) la do t h i 2- p h a n khac d o t h i r o n g v o i cac phas, k - 1 < §CH) < max5(H') < max5[G') a day m a x i m u m t h u nhat d u g c lay theo tat ca la va V2. Ta ciang gia s u rang C = ViV2V-i-Vj^v^ la m o t chu t r i n h bat k y tron,, cac d o t h i con cam sinh ( H ' ) ciia H , con m a x i m u m t h u hai d u g c lay theo tat ca G. neu v^eV-^, t h i V 2 e V 2 , V 3 e V i , V 4 e V 2 , . . . , hie la n h i i n g d i n h v o i chi so cac do t h i con cam sinh G ' ciia G. K h i do, xC^) = k < 1 + max5(G'). d u o i le la d i n h thuoc V^, con n h i i n g d i n h v o i chi s o ' d u d i chan la d i n h thupc , Jig ( ; u d : V 6 i d o t h i G bat k i ta l u o n CO x ( G ) < l + A(G) / ^ ; V2. V i the^ d o d a i cua chu t r i n h C phai la chan. ^^^^-9^ Brooks da c h i n h xac hoa ket qua 6 H $ qua tren. C u the la o n g ta da c h u n g 4. (c) =:> (b): Gia su G = ( V , E) la d o t h i khac d o t h i r o n g t r o n g d o m o i ch^ m i n h d u g c ket qua sau day. 1 ' ( t r i n h deu co d o dai chan. Truoc het ta xet t r u o n g h o p G la l i e n t h o n g . Ta co 3 . r o n g , la d o t h i 2- p h a n . V i G la h o p cua cac Gi, t r o n g d o co i t nhat m o t Gi k h o n g T r o n g ca hai t r u o n g h o p , gia s i i Xn_i E V - { x i , X 2 , X n } la d i n h ke v o i xn, con la do t h i rong, nen G c i i n g la do t h j 2- p h a n . \_2 d i n h ke v o i Xn hoac X n _ i . Tie'p tuc, ta chgn x ^ . j la d i n h ke v o i i t nhat V a n de dac t r u n g cac d o t h i k- sac v o i k > 3 con chua d u g c giai quye't. Tham nigt t r o n g cac d i n h Xn_2, x „ _ i , Xn, ... K h i do, ta t i m d u g c day x^, X2, X3,.. chi con chua t i m d u g c p h u o n g phap h i r u hieu de xac d j n h sac to cua m g t do t h i bat k y . T u y nhien n g u o i ta da t i m d u g c cac d a n h gia khac n h a u x(G). D u o i x„_2, X n _ i , Xn tat ca cac d i n h ciia G co t i n h chat la m o i d i n h ciia day, trir xn, ke day ta xem xet m g t vai d a n h gia do. Voi it nhat m g t d i n h sau no t r o n g day. Bay g i d ta to m a u cac d i n h ciia G n h u ^ink ly 2:V6i moi do thi G ta luon co x(G3 < 1 + max8(G"), a day maximum duac sau: Xj va X2 d u g c to bang m a u 1 ( v i X1X2 ^ E ( G ) ) ; neu X3 ke v o i m g t t r o n g cac d i n h x^ va X2 t h i ta to bang m a u 2, con t r o n g t r u o n g h g p n g u g c lai ta to bang lay theo moi do thi con cam sinh G" cua G. 'ft^au 1; ... Ta tie'p tuc to m o i d i n h ciia day bang m a u n h o n h a t co the 6 t h o i Chung mmAi.-Khang d i n h la hien nhien neu G la do t h i r o n g . Gia s u G la do t h i k - sac bat k y v o i k > 2, con H la do t h j con cam sinh bat k i co so d i n h nho
Bdi duang hoc sink gioi Todn tohQrp - rai rac, Nguyen Van Thong tren v i m o i d i n h chi ke vol n h i e u nha't la A - 1 d i n h t r u a c n o t r o n g day. V i vay, y.^ i = 1, 2 , k, la m o t tap d i n h doc lap cua G. G i a s u |Vi| = n ; . K h i d o to m a u tren cCing c h i n h la A - to m a u ciia G. i . (ii) G la d o t h i 2 - lien thong v o i A = A[G) = 2 . v ; i ^ afG) v o i m g i i = 1, 2 k. D o d o n = + 03 +... + < k a ( G ) c:> - I L - < xCG). m - o(,(_Gj K h i d o G la chu t r i n h d o dai chan va d o d o x(G) = 2 = A . fiW vay la bat dSng thuc t h i i nha't da dugc c h i i n g m i n h . (iii) G la d o thj lien thong, n h u n g k h o n g la d o t h i 2 - lien thong. p e c h u n g m i n h bat d a n g thvic t h i i hai ta xet tap d i n h dgc l a p S g o m a(G) K h i d o neu A = A(G) = 2 , t h i G la m o t d u o n g . D o d o x{G) = 2 = A va G c6 A - R6 rang la x C G - S ) > x ( G ) - l . Vi G - S c6 n-aCG) d i n h , nen to m a u . N e u A = A(G) = 1 , t h i G = K 2 . D i e u nay m a u t h u a n v o i gia thiet ve G. ^ ( G - S ) < n - a ( G ) . S u y r a x(G) 3 . V i G k h o n g la d o t h i 2 - lien thong, jvlot to m a u canh ciia m g t d o t h i la m g t phep gan cac m a u cho cac canh ciia nen n o c6 i t nhat hai kho'i va v i the m o i kho'i chua it nha't m o t d i n h cat cua G. ^5 thj d o sao cho hai canh ke n h a u ba't ky c6 mau khac nhau. N e u so m a u khac Gia s u Vi,V2,...,Vj„ la tat ca cac d i n h cua G thoa m a n A = d e g ( v i ) = ... = d e g ( v ^ ) , nhau, m a ta s i i d u n g t r o n g m g t to m a u canh ciia m g t d o t h i , n h o h o n hoac K h i d o cac kho'i ciia G chiia m o t trong cac d i n h d o deu k h o n g la d o thj K,,^ vi bang k, t h i to m a u canh d o c i i n g d u g c g g i la k- to m a u canh. So t y n h i e n k nho t r o n g t r u o n g h o p n g u g c lai d i n h cat thuoc k h o i d o c6 bac Ion h a n A . D i e u nay nha't de d o t h i G c6 k- to m a u canh d u g c ggi la sac so canh ciia G v a d u g c k y la d i e u k h o n g the xay ra. V a y hoac bac Ion nha't ciia cac kho'i nay nho h o n A hi?ula x'(G). hoac bac Ion nha't ciia cac kho'i nay bang A n h u n g kho'i k h o n g la K^^_i. T u H(> Hien n h i e n la x'(G)> A(G). Can tren cho x'(G) d u g c c h u n g m i n h t r o n g d j n h qua va khang d j n h (i) da c h u n g m i n h 6 tren, ta tha'y cac kho'i nay deu c6 A - to ly sau day. m a u . Cac k h o i con lai c6 bac Ion nha't nho h a n A . D o d o c h u n g cung c6 A - to M l y 5(Vizing, 1964). AiG) 0 ) va H la m g t d o t h i bat k y t r o n g Q v o i | E { H ) | = k + 1 . Ta d i n h nghla n h u sau. Tap h o p cac d i n h cua m g t d o t h i G d u g c g g i la dgc lap, chung m i n h rang H c i i n g c6 (A + 1 ) - to m a u canh. neu k h o n g c6 hai d i n h nao trong tap d o ke nhau. So d i n h ciia tap doc lap c6 Gia s i i x y i la m g t canh bat k y ciia H . K h i d o H - xy^ e Q v a H - xy^ c6 k n h i e u p h a n t u nha't t r o n g G d u g c ggi la so doc lap d i n h cua d o t h i G va dugc c?nh. Theo gia thiet q u i nap H - xy^ c6 (A + 1 ] - to m a u canh cp. T r o n g t o m a u k y hieu la a ( G ) . c^nh nay ciia H chi c6 xy^ la chua d u g c to m a u . -.i-iiirtf^rrs iSiiki mnh ly 4:Vai moi do thi G = (V, E) cap n, ta ludn cd , ., Ta n o i rang m a u t k h o n g d u g c s u d u n g trong to m a u canh cpo d i n h z ciia H -JJ-
Boi duang HQC sink gidi Toan toh h b a n g m a u ti, con xyn t h i d u g c coi la canh chua d u g c to m a u . N h u n g \ thanh p h a n lien t h o n g chiia yh ciia H(s,th) (no k h o n g thay d o i k h i ta xay d u n g t h k h o n g d u g c s u d u n g ca a x va xh, nen ta c6 the to xyh bang th va ta nhan
Boi dumtg hoc sink gidi Todn tohgp - rcri rac, Nguyen Van Tftong Cty TNIJH MTV DWH Khang Viet gia Qi C i i a M ta chon ra m o t d i e m v- k h o n g n a m tren bien g i a i . Tap tat ca ca^ iChung minh: (a) Gia s u va e^ la hai canh khac n h a u bait k y ciia M * . Ta d i e m V* d o c h i n h la lap d i n h ciia do t h i M * . Ne'u ej la m o t canh ciia ban do M ^cung gia s u rang e|^ la canh n o i d i n h v^ t r o n g quoc gia v o i d i n h V2 t r o n g con va Q2 la hai quoc gia c6 ej la bien g i o i chung, t h i ta ve d u o n g cong quoc gia Q 2 , la canh n o i d i n h V3 t r o n g quoc gia Q3 v o i d i n h V4 t r o n g n o i Vj v o i V2 va cSt ej tai m o t d i e m t r o n g ciia no n h u n g k h o n g cat canh nho quoc gia Q 4 . K h i d o ej^ n a m t r o n g p h a n mat phSng A la h g p ciia hai m i e n Qj khaccuaM. v o i Q 2 ' f^on 6 ^ n a m t r o n g phan mat phSng B la h g p ciia hai m i e n Q3 v o i . V I vay ne'u { v j , V 2 } n { v 3 , V 4 } = 0 , t h i A va B k h o n g c6 p h a n c h u n g . D o d o ej^ Ichong cat n h a u v o i ej^ . Gia s i i { v i , V 2 } n { v 3 , V 4 } = l . K h o n g l a m m a t t i n h tong quat, ta c6 the gia thie't rang v^ = V 3 . K h i do, Q i =Q3, con Q2 va Q4 la cac m i e n khac n h a u . Theo each xay d u n g , phan d u o n g cong t r o n g ciia e^ va ej„ chi CO m g t d i e m c h u n g la v ^ , con p h a n d u o n g cong ciia ej^ va e^ tuong ung trong Q2 va Q4 k h o n g c6 d i e m chung nao v i Q2 va Q4 la cac m i e n khac nhau. V ^ y el va ej„ k h o n g c6 d i e m chung ngoai d i n h c h u n g v ^ . H i e n n h i e n la t r u o n g h g p { v i , V 2 } o { v 3 , V 4 } = 2 k h o n g the xay ra v i ej^ va e^ la h a i canh khac nhau. V a y M * la d o t h i phSng. KhSng d i n h (b) c6 the c h u n g m i n h d u g c k h o n g m a y k h o k h a n , H i n h 3: Ban d o M va d o t h i M* t u o n g u n g ''»'''''''' (c) Gia s u M la m g t b a n d o c6 the to dugc bang k m a u . Ta lay m a u to quoc H o n the n u a , ne'u ei,e2,...,ei^ la cac canh tren bien g i o i ciia quoc gia la mien gia Qi ciia M de to cho d i n h v* ciia M * . K h i d o , ta to cac quoc gia ciia M chua b j chan ( t u o n g u n g , k h o n g b i chan) Qi dugc ke bat d a u t u canh theo t h i i tu d i n h ke n h a u t r o n g M * se d u g c to bang cac m a u khac n h a u v i cac quoc gia ciia chieu quay k i m d o n g ho, t h i ta c6 the chgn p h a n d u o n g cong cua t u o n g u n g v o i n o d u g c to bang cac m a u khac nhau t r o n g M . V i M c6 the dugc ei,e2,...,ek n a m t r o n g Qi sao cho chung k h o n g cat n h a u 6 d i e m nao khac ngoai to bang k m a u , nen to m a u tren ciia M * la k- to m a u . N g u g c l a i , gia s u M * la Vj va k h i ta quay theo chieu k i m d o n g ho ' ' u o n g u n g , theo chieu n g u g c vol 'do t h i k- to m a u d u g c . k h i d o , ta to quoc gia ciia M chua d i n h v* bang m a u ma chieu k i m d o n g ho) ta se Ian l u g t gap e2,e3,...,eS^. Tap cac d u o n g cong e* nav d i n h v* d u g c to t r o n g k- to m a u ciia M * . K h i do hai quoc gia c6 bien gioi c h i n h la tap canh ciia M * rtr ban d o M 6 tren H i n h 3. Tren h i n h nay cac d i ' chung se d u g c to bang cac m a u khac nhau v i cac d i n h t u o n g u n g v o i cac quoc ciia ban d o M la cac v o n g t r o n trang, con cac canh cua M la cac d u o n g lien. C gia d o ke nhau t r o n g M * . Vay M c6 the to d u g c bang k m a u . d i n h ciia do t h i M * l ^ cac v o n g t r o n den, con cac canh ciia M * l a cac d u o n ; T u m e n h de 1 ta thay ngay rang v a n de to m a u ban d o t u o n g d u o n g v o i cham cha'm. De thay rang M * c 6 the c6 canh b g i , n h u n g k h o n g c6 k h u y e n n Van de d m sac so Ion nha't cho cac d o t h i p h ^ n g va gia thuye't bon m a u tncmg v i M k h o n g c6 cau. T u y nhien, viec ton tai canh bgi k h o n g anh h u o n g g i f' d u o n g v o i gia thuye't rang m g i d o thj phSng deu la d o thj 4- to m a u d u r Vi v a n de to m a u t r o n g d o t h i M l y , n g u a i ta c u n g t h u o n g coi gia thuye't sau cung la gia thuye't b o n m a u . Menh del: Gia su M la ban do va M*la do thi dot ngau tucmg ung. Khi do: ^inh ly 6 : M g i d o t h i phang deu la d o thj 5- to m a u d u g c (a) M* la (da) do thiphanglien thong; Chung minh: G\a su khSng d j n h trong d j n h ly la sai va G = {V(G), E(G)) la d (b) ( M * ) * dang cau voi M ; :thi phang v o i x(G) > 6 c6 so d i n h nho nha't. K h i do G phai la do thi lien thong. N e i ; v o i m g i V e V(G) ta deu c6 deg(v) > 6, t h i 2|E(G)| = ^ v e ( ( , '^eg(v)>6|V(G (c) Ban do M c6 the to dugc bhg k mau khi va chi khi do thi phang M * la do thi «>|E(G)|>3|V(G)| . D i e u nay c h u n g to G k h o n g the la cay v i 'ong truong h g r
Cty TNHH MTV DWH Khang Vift Boi difmig hoc sink gioi Todtt to hop - red rac, Nguyen Van Thong thi phang bang 4 hoac 5. Giai thuyet bo'n mau thi khang dinh rang so'mau it ngugc lai ta nhan dugc mau thuan do |E(G)| = |V(G)| - 1 . V i vay ta c6 the ap jjxi't do chinh la 4. dung Dinh iy Bat d5ng thiic canh dinh cho G. Theo djnh ly nay ta c6. ^6.CACBAITOANVANDUNG: - v . . ' |E(G)|.-l^(|V(G]|-2).^(|V(G)|-2) v i - 1 - , - i l l - . Tu hai ba't d^n, fodn 1: 6 hgc sinh tham gia dau cb loai lap thanh mot hang dau tiic la moi thu gap moi nguai cdn lai moi nguai mgt Idn. Chimg minh rang ludn c6 the thuc nhan duoc ta suy ra. ^tn tfo^S ^'P S^V nhau roi, hoac chua gap nhau van nao. 3|VCG3 < E(G)
Boi duang UQC sink gioi Todn tohQrp - rcri rac, Nguyen Van Tltong Cty TNHH MTV DWH Khang Vi$t iNhdn xet J;Moi dinh ciia do thi dii, voi 6 hoac nhieu dinh hon, va vol c^;, heo gia thiet, dieu nay khong the dupe, chi con phai noi cac dinh D va E, B va canh gom hai mau, deu thupc vao it nhat la ba canh ciing mau. bang canh do. Cac canh con lai phai la xanh (Hinh 7). JVhdn xet 2: Trong mpi do thi du, voi 6 hoac nhieu dinh hon va voi cani, gom hai mau, c6 the tim duoc it nhat mpt tam giac c6 cac canh cimg mau. 'Bdi todn 2: Tren ban do dia ly nguai ta chgn ra nam thdnh pho. Biei rang gjQ^^ chung trong 3 thdnh pho bat ky deu c6 the tim ra 2 dugc not voi nhau ban^ hdng khong, vd 2 khong dugc noi. Chiing minh rang khi do: 1) Moi thdnh pho deu dugc noi true tiep bang duang hdng khong voi hai chi hai thdnh phokhdc. Hinh 6 Hinh 7 2) Bay tit mot thdnh pho bat ki, c6 the qua mgi thdnh pho cdn lai, ni6i Vay ta c6 them mpt nhan xet niia. thdnh pho mot Idn, vd quay ve. s;^- ? '! V:= i d wrt J^han xet 3; Neu trong do thi du, voi 5 dinh va 2 mau cgnh, khong t i m dupe Loigiai V'- f mpt tam giac nao voi canh cung mau thi do thi c6 the bieu thj dual dang :hinh Trong bai toan nay ta cung xet tap hop cac doi tupng thanh pho', va hij nam canh" voi canh do va duong cheo xanh. >; quan he da cho giiia cac phan t u ciia tap hop do; moi cap hai thanh pho o vao Trong phat bieu ciia nhan xet 3 ta c6 the thay "do" bang "xanh" dong thoi mpt trong hai quan h$- hoac dupe noi voi nhau bang duong hang Ichong, hoac voi "xanh" bang "do", tuc la noi den hinh nam canh voi canh xanh va duong khong. Gia su cac dinh ciia do thi ling voi cac thanh pho: canh do- khi do t cheo do. Dieu nay de hieu v i hinh nam canh, va chi no, c6 dac trung la, cac duong hang khong canh xanh- khi khong. Theo gia thiet trong 3 canh noi 3 duong cheo ciia no, ciing lap thanh mpt hinh nam canh (Hinh 7). dinh bat ky c6 mpt la do, canh thu hai la xanh (Hinh 4). Ma dieu nay c6 n g h i a ^dj todn 3: Trong vong mot ngdy, hai trong sdu nguai thue dim thoai, hie'n la, trong do thi khong c6 mpt tam giac nao voi canh dong mau. T u loi giai C L I I nhien Id c6 the noi chuyen voi nhau qua dim thoai md ciing c6 the khong. bai toan truoc, khi do se suy ra la, moi dinh nhat thiet phai thupc hai canh do Chung minh rang, luon co the chi ra hai bo 3 nguai, md trong moi bg, mgi va hai canh xanh (Hinh 5) boi v i trong truong hop trai lai se c6 mpt tam gia; nguai deu da noi chuyen voi nhau hoac deu chua. voi c^nh dong mau. Ma dieu nay c6 nghia la moi thanh pho' dupe noi ban; Lbi giai hang khong voi hai va chi hai thanh pho'. Gia sir rang trong do thi du voi 6 dinh cac canh do ung voi cap nhiing nguoi thue da noi chuyen voi nhau bang dien thoai, canh xanh la chua. Khi do trong do thi se tim dupe it nhat mpt tam giac, chang han ABC, voi canh ciing mau (Hinh 8) chi con phai chiing minh rang, nhat thiet con tim dupe mpt tam giac nhu vay niia. > ' O Hinh 4 Hinh 5 Chi con phai chung minh rang c6 the tim dupe trong do thi mpt "hinh na'i canh" ma mpi canh deu do. Ta hay chpn mpt trong cac dinh, chang han A, va cac canh do, chSng han I'' (A, B) va (A, C) (Hinh 6). Canh (B, C) (Hinh 6) khong the la do, thanh thu, canh do la mpt trong ca*^ canh: hoac (C, D) hoac (C, E). Gia sir (C, D) do. Neu bay gio noi cac dinh D v^i bang canh do thi dinh E phai dupe noi voi cac dinh da thupc vao hai canh ^'^
BSi duang hpc sink gioi Todtt toh)^ - rcri rac, Nguyen Van Thong • Cty TNHH MTV DWH Khang Vi^t Ta hay tarn thoi khong xet den dinh, chang han A, cung tat ca cac ceinh Kt dupe it nhat mpt tam giac c6 canh hoac xanh da troi, hoac xanh la cay. Bai thupc no. toan da giai xong. Co the t i m dugc chang trong do thj 5 dinh con lai mpt tarn giac voi canh Bay gia ta hay phat bieu nhan xet da dupe chung minh trong khi giai bai dong mau? Neu t i m dugc thi no ciang chua trong do thi xuat phat. toan. •^•:.v,r;"\.7t Trong truong hgp trai lai ta se dirge mpt hinh 5 canh vdi canh do va dirorig J^lhdn xet 5; Trong do thj du voi 17 dinh hoac nhieu hon va canh to bang ba cheo xanh (Hinh 9). Bay gio ta se khoi phuc lai dinh A thu sau va cac canh cua n6 liiau, luon C O the tim dupe it nhat mpt tam giac vai canh cung mau. (Hinh 10). Neil canh (A, D) hoac canh (A, F) cOng se dupe to mau do thi toi thieu Chii y rang, khong phai ngau nhien, nhirng quan he ma khi giai bai toan ta la mpt tam giac voi canh do rma dvtgc hinh thanh ADB hoac ACF. Neu ca hai canh bieu thj bang canh mau, la doi xung (neu A la ban ciia B thi B la ban cua A), deu mau xanh thi se xuat hi^n tam giac AFD voi canh xanh. Co the chuyen de nhung khong nhat thiet la bae eau (neu A la ban ciia B, B la ban cua C, thi A dang ket luan nay t u ngon ngii cua do thi sang ngon ngir cua bai toan. van CO the khong la ban cua C). Trong truong hpp ma quan he giira cac doi Vgy nhan xet sau day ciia do thj la mo rpng cua nhan xet 2 da dupe khang tupng la tuong ung thi cac canh tuang ung lap thanh mpt tam giac vai canh djnh. dong mau. j{han xet 4; Trong mpi do thi du, vai 6 dinh hoac nhieu hon voi canh to mot Nhiing quan h§ nhu vay la dac trung cho nhung bai toan ma ta c6 the giai trong hai mau, luon c6 the tim dupe hai tam giac voi canh dong mau khac dupe nha do thj mau. ! nhau. Hai tam giac nay c6 the eo dinh chung hoac ca canh chung. 4.7. 06 TH! G I U P V I ^ C G I A I C A C BAI T O A N : Ta se gpi hai tam giac c6 dinh hoac canh chung la hai tam giac gan nhau. Ta se xet a day, mpt so bai toan nvta, ma cac do thj giiip ta mpt each ca ban Ta hay lam quen voi nhijng tinh chat ciia do thj du, c6 canh dupe to mot trong viee giai. Cac bai toan nay eon givip ta tim ra cac tinh chat khac niia cua trong ba mau (moi mau ung voi mpt trong ba quan h§ cua eae doi tupng trong nhiing do thj ay. tgip hpp da eho). Sdi toan 5: Trong khong gian ba chieu c6 chit} diem, phdn bosao cho khong c6 Hay mang bai toan cua ky thi v6 djch toan quoc te Ian thir sau, ma ta c6 the dung cac do thj mau de giai, dieu nay se rut gon buac ly luan mot each ca ban. ha diem ndo nam tren mot duong thang. Moi diem duoc noi bang doan thang 'Bai toan 4: Moi ngubi trong 17 nhd khoa hoc trao dot thu vai nhimg ngucd con vai ddng ban diem khdc. Chdng minh rang luon ca the tim thdy it nhat mot lai. trong thu cua ho chi noi ve ba de tdi. Moi cap nhd bdc hoc chi trao doi vc tam gidc vai dinh tai cac diem ndy. tngt detdi. Hay chttng minh rang, c6 khong it hon nhd bdc hoc trao doi vai nhau vecung mgt detdi. ; Loi giai I Gia thiet cua bai toan ung voi mpt do thj du 17 dinh voi canh gom 3 mau. Tu moi dinh xuat phat 16 canh. Ta se chung minh rang, trong mpt do thj nhu vay se tim ra dupe it nhat la mpt tam giac eo canh dong mau. Chii y rang, moi dinh ciia do thj nay se thupc vao it nhat la 6 c^nh dong mau (ban hay t u chung minh lay!). Gia su chang han, dinh A thupc 6 canh do. (Hinh 11). Neu trong so cac dini^ B, C, D, E, F, H CO the tim dupe hai dinh noi voi nhau tung cap bang cac can'^ cua hai mau (xanh la cay va xanh da troi). Trong do thi 6 dinh nhu vay c6 th 164
Boi duong hqc sinh gioi Todn to hap - roi rac, Nguyen L a i giai Van Thong Ta thiet lap s u t u a n g l i n g giira cac d i e m cvia k h o n g gian v o i cac d i n h ciia d o W L o i giai Cty TNHH Ml '! V I f Khang Xa C O d o t h i d i i n d i n h va canh h a i m a u (canh xanh la hai n g u o i c6 the n o i Viet t h i . Cac doan da n o i cho t u o n g l i n g v o i canh do, chua noi v o i canh xanh. Ta n h a u b a n g m p t t h u tieng nao do, canh do la khong) theo gia thiet, trong hay c h u n g m i n h r a n g t r o n g d o t h i d u 9 d i n h ma m o i d i n h thuoc b o n m a u can]-, jjgn d i n h bat k y l u o n c6 the t i m d u g c it nhat mpt, ma bac xanh ciia no bang 3. do va b o n canh xanh, c6 the t i m d u o c m p t t a m giac v o i canh do. T r u a n g h g p ma m p i canh deu xanh la tam t h u a n g , k h o n g q u a n t r p n g ve H a y gia thiet rang k h o n g c6 t a m giac canh do, gia s u m o t d i n h A nao d o j^^t toan hpc, gia s u c6 the t i m d u p e m p t canh d o (A, B). Ta t h e m vao hai d i n h d u g c n o i b a n g canh d o v o i 8^,82,63 va 84 canh xanh v o i Ci,C2,C3 vaC^ . Cai va D nao do. T i r b o n d i n h A , B, C va D se t i m d u p e it nhat m p t , c6 bac xanh bang 3. D o la C hoac D . Ta gia su, chAng han C c6 bac xanh bang 3, ta se t h e m canh d a n g (Bi, Bj) deu xanh ( H i n h 1). M o i d i n h Bi d u o c n o i bang ba canh do v 6 i vao m p t d i n h ni>a E. T r o n g cac d i n h A , B, C, E. cac d i n h Q . H a i canh d o no'i cac d i n h dang C v o i n h a u ( v i rang so cac canh d o (Bi, Bj) la 12). Gia su, rang B^ d u g c n o i bang canh d o v o i Ci,C2, va C3. Car $di todn 8: Trong thanh pho c6 n nguai dan. Hai nguai bat ky trong he deu \ioac than nhau, hoac thii nhau. Them nUa, ba bat ky trong ho deu hoac than d i n h Ci,C2, va C3 d u g c no'i v o i nhau bang canh xanh, neu k h o n g , da hinh nhau cd ba, hoac chi hai. Chung minh rang neu khong phai moi nguai dan thanh m p t t a m giac canh ( H . 2). K h i d o C 4 thuoc h a i canh d o d a n g ( C 4 , C), thanh pho deu than thien, thi se tim dugc mot nguai thu nhieu han ban. chang han (€4,03) va ( C 4 , C 2 ) . N h u n g C4 con thuoc h a i canh d o n u a . M o t L a i giai t r o n g chving chang h a n la (C4,B2) (h. 2). I t nhat m o t t r o n g cac canh (B2,C2) va Ta lap t u o n g u n g m o i n g u o i d a n thanh p h o v o i m p t d i n h cua d o t h j . Gia su (82,C3] Cling do, nghia la it nhat m o t t r o n g cac t a m giac B^.Z'^.Cj^ va B2,C2,C4 cgnh xanh c6 n g h i a la hai n g u o i than nhau, va d o la t h u n h a u . Theo gia thiet C O canh d o . j , . trong do t h j da cho t a m giac c6 the la c6 3 canh xanh, hoac 1 xanh 2 do, va c6 it ^ d i todn 6:Chtmg minh rang trong moi nhom chin nguai, ma trong do khong tim nhat m p t canh do. Can c h u n g m i n h rang c6 the t i m d u g c m o t d i n h c6 bac d o duoc ba nguai quen nhau timg cap, se tim duoc ban nguai quen nhau titng cap. Ian h o n hoac bang bac xanh. ^ h • L a i giai Ta hay xet m o t canh d o ( A , B) nao do. Gia su bac xanh ciia A la k. Gia thiet Ta dat t u o n g u n g m o i n g u a i t r o n g n h o m v o i m g t d i n h cua d o t h i . Gia su canh xanh c6 nghia la hai n g u a i quen n h a u canh do la k h o n g quen. Theo gin la 1^ - ~ • De thay r a n g d i n h B d u g c n o i bang canh do v o i cac d i n h , m a v o i thiet t r o n g d o t h i k h o n g c6 m o t t a m giac canh d o nao. Can p h a i c h u n g m i n h chung t h i A d u g c n o i bang canh xanh. D o do neu bac d o ciia B la m t h i rang, t r o n g m o t d o t h i n h u v a y t o n tai m p t h i n h b o n canh v a i canh la d u o n g cheo xanh. Gia s u la t r o n g d o thj ay t o n tai d i n h A , thuoc b o n hay n h i e u hon, m=k+l>k>- i canh do: ( A , B ) , ( A , C), ( A , D ) , ( A , F) t h i k h o n g the c6 t a m giac do, cac d i n h A , Sdi todn 9: Trong thanh pho c6 n nguai dan. Hai nguai bat ky trong ho deu C, D va E d u g c n o i t u n g cap bang canh xanh. Ta da t i m d u g c h i n h 4 canh phai hocic than, hoac thii nhau. Moi ngdy c6 khong qua mot nguoi co the bat dau t i m . Ta se xet t r u o n g h g p k h i t r o n g do t h i k h o n g t o n tai d i n h nao thuoc 4 hay citpc sang men; bat hda vai tat cd cac ban, thay vi than thien voi tat cd cac thu n h i e u h o n , canh d o . C h i i y rang tir m o i d i n h k h o n g the c6 d i i n g 3 canh d o d i r
Boi dumtg hoc sinh gidi Todn to h(pp - rai r^c, Nguyen Van Thong Cty TNHH MTV DWH Khang Vtgt giac canh xanh hoac tarn giac mpt canh xanh, hai canh do (Hay chiing minf, rang, tinh chat nay ciia do thi khong thay doi qua cac phep bien doi). Trong mot do thi bat ky nhu vay, c6 the tim dupe mpt dinh ma bac do cu;, no Ion hon b^c xanh (xem Bai toan 8). Neu moi Ian ta deu chpn trong do thi dinh voi do Ion nhat va to mau lai cac canh thupc vao no, thi so' canh xanh tang dan qua tung buoc. DT nhien so'cac canh cua do thi la hiju han, do do q u a mpt so hiiu han buoc tat ca cac canh ciia do thi se tro thanh xanh. 4. 8. BAI TOAN V§ CAC HINH TAM GIAC KHONG GAN NHAU VOI CANH D 6 N G MAU: ^ d j todn 10: Ta se goi mot nhom nguai la "thudn khiet" neu hat kt cap ngudi ndo cua nhom nay ciing thich ung voi nhau vetdm ly hoac nguoc lai, bat ki cap Hinh 1 Hinh 2 Hinh 3 ndo ciing khong thich ung ve tam ly. Chitng minh rang, trong 8 ngudi khong 4.9. NHONG CTNG DUNG CUA BAI TOAN TO MAU O 6 THI quen biei, gap go nhau mot each ngau nhien, nhat thiet tim duoc chia nhom Bai toan to mau do thi eo nhieu ling dung khae nhau de xe'p Hch va gan thudn nhat, moi nhom 3 nguai, ma khong nguai ndo trong mot nhom ndy c6 a nhan. (Chii y la vi khong c6 thuat toan c6 hieu qua nao de to mau do thi va trong nhom khdc. dieu nay khong dan den nhirng thuat toan hieu qua de lap lieh va gan nhan). N6i each khdc, can chihtg minh rang, trong mot do thi 8 dinh voi canh to Cac vi dy ling dung nhu vay se dupe xet 6 day. Ung dung dau tien lien quan mot trong hai mdu, nhdt thiet tim duoc hai tam gidc voi canh dong mdu khong t6i vi?csap lich thi. i , > fi i gdnnhau. Vidu l:Ldp lich thi. Hay lap lich thi trong truong dai hoc sao cho khong cd sinh Lai giai vien nao co hai mon thi ciing mot luc. Ta hay xet trong do thi mpt tam giac K L M voi canh dong mau. Theo dinh Giai: Co the giai bai toan lap lich bang mo hinh do thi, voi cac dinh la cac ly, tam giac nhu vay luon tim dupe. mon thi, c6 mpt canh giiia hai dinh neu eo sinh vien phai thi ca hai mon dupe N^'u nam dinh con lai va cac canh noi chiing tung cap chua mpt tam giac bieu dien bang cac mau khae nhau. N h u vay viec lap lich thi se tuong ling voi voi canh dong mau nira, thi no chinh la tam giac thii hai phai tim (trong vi^c to mau do thi nay. truong hop do bai toan da dupe giai). Vi du CO bay mon thi can xe'p lich. Gia sii cac mon hpe dupe danh so'tu 1 toi Neu nam dinh con lai A, B, C, D, E khong chua mpt tam giac nao voi canh 7 va cac cap mon thi sau c6 ehung sinh vien: 1 va 2,1 va 3,1 va 4,1 va 7, 2 va 3, dong mau, thi chiing se lap thanh mpt hinh nam canh voi canh do va duong 2 va 4, 2 va 5, 2 va 7, 3 va 4, 3 va 7, 4 va 5, 4 va 6, 5 va 7, 6 va 7. Tren hinh 8 bieu cheo xanh. Tren (Hinh 1) khong ve mpi canh ciia do thi ung voi bai toan ma chi dien do thj tuong ung. Viec lap lich thi chinh la viec to mau do thj nay. ve tam giac K L M voi canh do va hinh nam canh ABCDE, voi canh do v a V i so mau ciia do thj nay la 4 (doe gia t u kiem tra lai dieu nay), nen can eo duong cheo xanh. bon dpt thi. Cach to do thj bang bon mau va lich thi dupe bieu dien tren hinh 9. Ta hay chiing minh rang, neu mpt dinh nao do ciia tam giac K L M dupe noi voi hai dinh, dupe lay each mpt chang han K va A va C (Hinh 2) ciia hinh nam canh bang cac canh xanh, thi se tim dupe mpt tam giac niia, voi canh cimg mau, khong gan voi tam giac KAC. jVLzn xet 6: Trong do thj dii 8 dinh c6 cgnh dupe to bang hai mau, nhat 'i thiet tim dupe hai tam giac voi canh cung mau khong gan voi nhau. 169
., J i l l i odn toh(pp - rcri rac, Nguyen Van Thong CtyTNHHMTV DWH Khang Viet Lai giai • Cau tra l o i la k h o n g . Ta se chijrng m i n h d i e u nay bang p h a n c h i i n g . Gia s\x b a n g each t o ciia b a i toan, ta eo the to m a u tat ea eae 6 ciia bang. K h i (Jo torig tat ca eae Ian to la 1991 x 664. D i e n cac so'vao 6 v u o n g t r o n g bang theo c^ch sau: tai 6 ( m , n) d i e n so m n . G o i tong so eae so da d i e n la S, ta c6: S = ( l + 2 + 3 + ... + 1 9 9 1 ) ( l + l + 2 + ... + 1992) = 0(mod3) Iv4at khae, g o i Si la t o n g cvia 3 so n a m t a i 3 6 d u g c t o 6 Ian t h u i v o i l < i < 1 9 9 1 x 6 6 4 . D e thcYy =:rs + (r + l ) ( s + l ) + (r + 2Ks + 23 = 2(mod3) va Si la Hinh 8: D o thj bieu dien Hinh 9: Dung bai toan to t6ng ciia 3 so c6 d a n g ab, (a+l)b, (a+2)b, suy ra Sj =0(mod33 v a y S = 2 (mod3) bai toan lap Ijch thi mau de l^p lich thi mau thuan! Suy ra d i e u phai e h i i n g m i n h . ' ' '''' ' • '' ' Bay g i o ta xet bai toan p h a n chia kenh t r u y e n h i n h
Cty TNHH MTV DWH Khang Vi$t Boi duang hQC sink gidi Todn to hap - rbi rac, Nguyen Van Thong f(m,n)=|Sb(ACB)-s^(ABC)| Bay gia ta to mau cac dinh cua mot do hinh sao cho 2 dinh dugc no'i nhau boi 1 canh thang thi = iSb(ABDC)-S^(ABDC) dugc to boi 2 mau khac nhau. Ta khang djnh rang Vgy f(m, n) = 0 neu m, n ciing de to mau nhu the chi can 3 mau la du. Ta chung minh khang dinh nay bang qui nap theo n (so' chart va f(m,n) = i neu m, n cijng le. • canh cua da giac). , ( h f e o i n ' ^ ^ a J • 2. Neu m, n ciing chan hay ciing Khi n = 3 phong trien lam la mot tam giac va ta chi can to 3 dinh boi 3 mau, le thi ket qua suy t u (1). Gia su m le ^ Gia su khang dinh dung khi phong trien lam c6 n > 3 tuong. Xet phong n chSn. Xet diem L tren AB sao trien lam c6 n + 1 tuong. Su dung tam phan do'i v6i da giac G do cac biic tuong cho AL= m - 1. ,.;v ^ xac dinh tren nen nha. Goi G' la da giac nham t u G bang each bo tam giac ABC. Theo gia thie't qui nap khang dinh dung voi n - giac G'. Vi A va B chi dugc to Vi m - 1 chan nen ta c6 f ( m - l , n ) = 0 m- boi 2 trong so 3 mau da cho nen ta chi vi^c to dinh C bang mau con lai. Vay nghla la: Sb(ALC) = S^(ALC) khang dinh dung voi n + 1- giac G va do do dieu khang dinh da dugc chiing V a y f { m , n ) = |Sb(ABC)-S,(ABC)| , . , ^^^^^^ minh. Vay ta da chung minh rang neu phong trien lam c6 n buc tuong thi cac tuong xac djnh mot do hinh n- giac tren nen nha. Cac dinh ciia do thi dugc to = |Sb{LBC)-S^(LBC)|
Boi dumg hQc sinh gioi Toan tohfrp - roi rac, Nguyen Van Thong Cty TNHH MTV DWH Khang Viet 4k + 1 1 bcri hai m a u nen t o n tai hai d i e m c i i n g m a u , chSng h a n A^ va A 2 , k h i d o chi> VaySb(LBC3 = k — ^= -(8k-l) nh^t A1A2B2B1 C O 4 d i n h cung m o t m a u . Suy ra fC2k - 1,2k) = •i(2k - 1 ) , tir d o f(m, n) k h o n g b j ch^n tren. i$di todn 2. Gid mpt ban cb hinh chU nhat c6 4 x 7 6 vuong duoc son dm }ioac trdng. Chiing minh rang vai each son man bat ky, trong ban cb luon ton ^di 5: (Viet Nam 2001) t(ii hinh chit nhat gom cac o vuong ma 4 o agoc la cac 6 ciing mau. Cho bang 6 vuong kick thudc 2000 xlOOl gom 2000 hang 2001 cot. Hay thn sff Chiing minh. Ta c h u n g m i n h cho bai toan ban c d 3 x 7 m a u son m a u c6 the nguyen duong lent nhat k sao cho ta c6 the to mau k d vuong con cua bang thdq ay ra v o i b a n ca nay C O dang t u 1 den 8. man dim ki^: hai 6 vuong con nao duqtc to mau dm khong c6 dinh chung. Lai giai Q u i uoc: T h u t u cua cac hang dugc ti'nh tir tren xuo'ng d u d i , thu t y ciia c^c cot dugc t i n h tir p h a i sang trai. K i hieu (i, j) la 6 v u o n g n a m 6 6 v u o n g giao hang t h u i va cot thvV j . K y hieu k(T) la so 6 v u o n g d u o c to m a u 6 each to Hia^ T. Xet m o t each to m a u T thoa m a n dieu kien de bai. D e thay, n e u 6 (i, j) V(»i l
Boi duchtg hgc sinkgidi Toan to hap im nu, fv^niyi'i/ t . t i i Thong Cty TNHH MTV DWH Khang Vi?t 2 . Ne'u G C O mau xanh. =73, thi cac diem A va Aj to ciing mot mau. R6 rang tren duong tron do Keo dai GA, GB, GC cac do^n jjion tim dupe hai diem c6 khoang each giira chiing bang 1. A A ' = 3GA, BB' = 3GB, C C = 3GC Ta d upe mau thuan, vay luon tim dupe hai diem ciing mau c6 khoang each Khi do, ne'u goi M , N , P tuong chiing bang 1. • ' * " ling la cac trung diem ciia BC, todn 6. Cho hinh da giac deu 9 canh. Moi dinh ciia no duoc to bang mot CA, AB thi A ' A = 3GA = 6GM trcng hai mau trang hoac den. Chiing minh rang ton tai hai tam giac phan bi^t => A ' A = 2 A M . / ^ dien tich bang nhau, tna cac dinh cua moi tam giac duoc to cung mot mau. Tuongtu ^'-^ Chung mmh.Chin dinh Ai,A2,...A9 c u i da giac deu dupe to bMng hai mau, B'B = 2BN , C C = 2CP. B' lign theo nguyen ly Dirichlet co it nhat nam dinh trong so'do dupe to ciing mpt Do do cac tam giac A'BC, B'AC, C A B tuong ling nhan A, B, C la trpng tam. mau. Gia sir c6 nam dinh dupe to mau trang, nam dinh nay tao ra: Mat khac ta ciing c6 cac tam giac ABC va A'B'C c6 ciing trpng tam G'. Co hai truong hop sau c6 the xay ra: — = 10 a) Ne'u A', B', C cung xanh. Khi do tam giac A ' B ' C va trpng tam G ciing ^ 3!2! mau xanh. Tam giac mau trang (tam giac tiie la tam giac c6 ba dinh ciing mau trang). b) Ne'u it nhat mpt trong cac diem A', B', C c6 mau do. Khong giam tong Gpi la tap hpp cac dinh cua da giac da cho, tuc la: quat gia su A ' do. Khi do tam giac A'BC va trpng tam A mau do. fi = {Ai, A2, As, A9) Vay trong mpi kha nang luon ton tai mpt tam giac ma ba dinh va trpng tam Gpi O la tam cua da giac deu da cho. cimg mau. Bai toan dupe chling minh. • Xet phep quay cac goe 0«, 40^, 80", 120", 160", 200", 240", 280«, 320° xung quanh tam O. R6 rang ling voi moi phep quay nay thi tgp Q bie'n thanh chinh Sdi todn 4. Cac diem tren duang iron duoc to hang 2 mau xanh do. Q (tuc tap cac dinh ciia da giac deu khong thay do'i qua phep quay, mac d i i khi a) Hoi CO luon ton tai mgt tam giac deu c6 dinh ciing mau hay khong? quay dinh nay bie'n thanh dinh kia). b) Hoi CO luon ton tai tam giac can c6 ba dinh ciing mau hay khong? Sau chin phep quay tren thi 10 tam giac trang bie'n thanh 90 tam giac trang, Chung minh. a) Khong ton tai: Ne'u ta to mpt nua duong tron boi mau xanl ma moi tam giac nay deu co cac dinh thupc tap hpp Q. Chii y rang so cac tam va nua con lai boi mau do, thi khong c6 tam giac deu c6 ba dinh ciing man giac khac nhau co dinh trong Q la: dupe vi khong c6 tam giac deu nao npi tie'p dupe nira duong tron. ;s d= = 84 b) Luon ton tai: That vay, ta npi tie'p duong tron nay mpt ngii giac deu. Nhu ^ 6!3! vgy cac dinh cua ngii giac deu dupe to hai mau. Theo nguyen ly Dirichlet ton Vi 84 < 90, nen theo nguyen l i Dirichlet ton tai hai tam giac trang va A2 tai ba dinh ciing mau. Khoang each giiia cac dinh cua ngii giac deu chi c6 hai sac cho cac phep quay tuong img triing voi cimg mpt tam giac. dp do dai ngan khac nhau, ba canh cua tam giac c6 ba dinh ciing mau nay phai CO hai canh c6 ciing mpt dp do, va do do tam giac luon la tam giac can. Vi phep quay bao toan hinh dang va dp Ion cua hinh (noi rieng bao toan ^di todn 5. Nhihtg diem trong mat phang duqic son bang mot trong ba man. di?ntich), tirela: S.^^ =S\ Chung minh rang luon tim duoc hai diem ciing mau each nhau bang 1. Chung minh: Gia sir hai diem bat ky each nhau 1 deu dupe to bang cac mai.! khac nhau. Xet tam giac deu ABC c6 canh bang 1, tat ca cac dinh cua no dupe to bang cac mau khac nhau. Gia sir diem Aj do'i xung voi A qua duong BC. Vi AjB = AjC = 1, nen diem A^ c6 mau khac voi mau cua B va C, tuc la no dupe tc ciing mpt mau vai diem A. Cac lap luan do thue chat da chi ra rang nev 177
Boi duang UQC sink gioi Toan to hap - rai rac, Nguyen Van Thong r Cty TNHH MTV DWH Khang Vi?t - N e u n = 4 m + 2 t u o n g t y , t o n g la m g t so' le h o n chSn = c h i n => n = 4 m + 2 ng k h o n g d u g c CAC B A I T O A N R O I R A C T 6 N G HQfP- T O A N T H I Vay ta phai c6 n s 0 hay 3 (mod4). Dac bi?t, n = 1 , 2, 5, 6, 9, 10 la k h o n g thich . Ta c h u n g m i n h d u o ! day la n = 3, 4, 7, 8 la thich h o p 1 . Moi trdi bong trong tui dung se c6 mot trong hai mau vd mgt trong hai trong 3 J 2 3 2 H I * *f I ' 'fj^'t' • [•< lugng. Co it nhat mgt bong cho moi mau vd mgt bong cho moi trgng luqng. 3 4 J 3 2 4 2 i , ti\ , \ I,*'** M it] M . : ' Chiing minh rang c6 hai qua bong v6i mau khdc vd trgng lugng khdc nhau. 2 5 2 6 7 J 6 5 3 4 6 3 7 4 -^ijM , ^ Giai 2 6 2 5 7 8 J 6 5 3 4 7 3 8 4 ,i ;, Goi h a i m a u d o v a xanh va h a i t r p n g l u g n g la 1 v a 2. M o t q u a b o n g c6 the la => ( d p c m ) D l , D 2 , X I hay X2 (Voi k y hieu D l la b o n g m a u d o c6 t r o n g Ivrong la 1 , . . .)• Neu Ji/hdn xet: Day la mot Men theciia bai todn Langford, bai todn nay da dugc decgp k h a n g d i n h k h o n g d i i n g t h i ta k h o n g the c6 D l v a X2 v a k h o n g the c6 D 2 hay tren bdo Todn Hoc vd Tudi Tre. Co the neu mot hai todn tuomg tu la: X I . D i e u d o c6 nghia la tat ca cac b o n g phai c6 D l va D 2 , hay D l va X I , hay D2 Day soai, ai..., asm gom moi so tit 1 den 1986 c6 mat hai Ian. c6 the sap xep lai cac va X2 hay X I v a X2. N h u n g the t h i v o i t r u o n g h o p t h u nhat ta k h o n g c6 bong so hang sao cho c6 dung n so nam giita hai son ? (China, 1986) \ • m a u xanh, t r u o n g h o p t h u h a i ta k h o n g c6 b o n g t r o n g l u g n g 2, t r u o n g h g p thu Bdi todn tren giai nhusau: ^"^'^ • ''(J^'P m-'(fm^i mdl v.. 3 k h o n g C O b o n g t r g n g l u g n g 1 con t r u o n g h g p t h i i t u k h o n g c6 b o n g m a u do: Ta tong qudt bdi todn tie 1986 den n, khong theco cdch sap xep ndo nhu debdi vai trai gia thuye't. M a u t h u a n nay => (dpcm) n = lhay 2 (mod 4). Nhu vay, noi rieng cho truong hop n = 1986 la khong thethuc 2. C6 2n + 1 qudn bdi. Trong do cH hai qudn bdi dugc ddnh ding mgt so nguyen hien dirge. iitldehnvd mgt qudn bdi joker. Tat cd cac qudn bdi dugc xep thdnh mgt duang To mau cdc vi tri Ian lugt cdc mdu den trang. Cdc sole a cdc vi tri cung mdu vd cdc thdng vai qudn bdi joker a vj tri trung tdm (Moi phia cua qudn joker c6 n qudn so chin d vi tri cung mdu. Nhung tong cdc vi tri la chdn, nen so moi mdu hang nhau bdi. Vai n (dpcm) T u d o t o n g cac cap n h u the la c h i n , n h u n g tong d o c u n g b a n g Cho m + 1 duang tl ang nam ngang cdch deu nhau vdn + 1 duang thang nat . n(ii-l) 1+2 + ... + ( n - l ) = ' ^gc cdch deu nhau tao thdnh mgt luaihinh chUnhdt vai (m + t)(n + 1) niit. GQ f(tn, n) Id solo trinh di tu: mgtgoc den goc dot di?n dgc theo cdc duimg luai sao B e h o n s o ' c a p b g c l a y quan joker «, • '\ 16 trinh khong d qua mgt ndt ndo den hai Idn. Chiing minhf(m, n) ^2""' Neu n c h i n , the t h i m g t so cap phai bgc lay quan joker v a n e u n \h t h i c ' Giai m g t so le cap. D o d o Ta c h u n g m i n h bang each q u y n^p theo n - N e u n = 4 m + 1 t h i tong la c h i n be h o n 16 = M, v i the n = 4 m + 1 la kho! , I? Neu n = 0, the thi chi c6 m g t 16 t r i n h , cho nen: F(m, 0) = 1 < 2'" ' ' the d u g c 179
Boi dttmtg hQC sink gioi Todn tohgp - rcri rac, Nguyen Van Thong Cty TNHH MTV DWH Khang Vi(t Gia d j n h ket qua d u n g d e n n . rang bdi todn cho trumg hap tong qudt n nguoi, cdch chung minh hodn todn G p i d u o n g t h i n g t h i i (n + 1) c6 cac n i i t A', B', ..., X' v o i A ke A'... ]ch6ng dot. Gia sir r a n g A ' la d i e m den. Bay g i o ta d e m so'16 t r i n h v o i m a u da cho truoc Tuy nhien, cdch ly luan nay hai kho hieu. ' ; jn-,: :4 nO:.,, g o m cac doan t r o n g d u o n g thang A'X'. c6 1"" m a u n h u the ( M o i doan t r o n g m 6. Hai dau thu tham gia mot trd chad bat ddu tic mot ban cb 3x3 trong. Moi dau doan ay c6 the 6 t r o n g hoac ngoai). ..; • f * > • ' - > •» • ' • thu den phien minh dat mot qudn cb den hay trang vao mot 6 trong ciia ban cb. N e u cac d o a n D'E'F' thuoc vao m a u d o ( N h u n g khac C D ' va F'G') t h i 16 ffioi dau thu CO the chcn hat ky mau nao. Khi ban cb da day thi dau thu A se dugc t r i n h d o p h a i bao g o m DD'E'F'F. T r o n g t r u o n g h o p m a 16 t r i n h chgn g o m cac fftot diem cho moi hang, cot hay duong cheo chinh no c6 0 hay 2 qudn den tren doan ket thuc 6 A ' n h u A ' B ' C ch^ng han t h i 16 t r i n h ay phai bao g o m A'B'C'C. 4o. Ddu thu B dugc mot diem cho moi hang cot hay dubng cheo chinh neu c6 1 N o i each khac, ta c6 d u o c m p t bo ba cac 16 t r i n h con ma m 6 i 16 t r i n h ay la gom hay 3 qudn den tren do. Trd chcfi c6 the ket thuc hda hay khdng? Ddu thii nao se b o i hai hay ba (c6 m o t t r u o n g h o p ) canh cua h i n h chir nhat ( n h u la DEF, A'BC CO chieh thuat thang neii dau thu A di ddu? Neii ddu thu B di ddu? t r o n g v i d u tren chSng h a n ) , the t h i ta d u g c m o t 16 t r i n h cho t r u o n g h g p m , n. Giai H o n nvta a n h xa nay h i e n nhien d o n anh. Cho nen t o n tai k h 6 n g qua 2""' 16 M o t tran hoa la c6 the. Ta xet v i d u sau: '^^ t r i n h cho m a u da cho va n h u t h e t a c6 ca thay k h 6 n g qua Z-^Z"^" = 2^" * ' 16 trinh. D D D N h u v a y theo n g u y e n l y q u y nap , h'nh chat d u n g v o i m o i m , n e N . D T D 5. Co 15 vi khdch voi ten khdc nhau ngoi quanh mot ban trdn, khong nhan thay D D D rang tai moi cho ngdi c6 mot bang ghi ten. Moi nguoi deu ngoi khong dung vi tri. N e u A d i d a u , c6 the dat quan den vao 6 t r u n g tam r o i sau d o anh ta dat Chung minh ta c6 the quay cdi ban sao cho c6 it nhat hai nguoi ngoi dung cho quan khac m a u v o i q u a n B dat, va vao 6 d o i x i i n g v o i 6 B v u a dat qua 6 t r u n g ghi ten ho. Hay neu mot vi du vemot cdch sap xep ma chi mot nguoi ngoi dung tarn. Dieu do se tao nen hai quan den tren bat k y d u o n g nao d i qua t r u n g t a m . cho ghi ten ho. Hay neu mot vi du ve mot cdch sap xep ma chi mot nguoi ngoi Do do se d u g c i t nhat 4 d i e m . H o n nira hai goc ke phai va hai goc kia la trang. dung, nhung khi quay ban thi khong cdi thien duoc tinh hinh. Neu quan 6 giira hai goc la trang t h i a d u g c t h e m d i e m cho hang hay cot ay, Giai neu k h 6 n g t h i A c i i n g d u g c them d i e m cho hang hay cot d o i dien. D o d o A dat Ta sir d u n g n g u y e n l y Dirichlet. Lay v i t r i ban d a u chuan, ta quay m 6 i Ian it nhat 6 d i e m v a thang cugc. ve ben phai m o t v i t r i . Se c6 15 v j t r i ciia b a n (Ke ca v j t r i ban dau). N h u v a y thi N e u B d i d a u , t h i B c6 the thang bang each dat vao 6 t r u n g t a m quan trang ca 15 n g u o i d e u Ian l u g t d u o c ngoi d i i n g v j t r i . N h u n g v i ban dau k h 6 n g c6 ai roi dat n h u A . ngoi d i i n g v i t r i ca nen se chi c6 14 v j t r i ciia ban ma c6 n g u o i ngoi d u n g v i tri. >Midn xet: Bdi todn nay co khd nhieu hien the. Cdch chimg minh hdu hct dm vao Theo n g u y e n l y Dirichlet, se c6 m p t v i t r i nao ciia ban ma c6 i t nhat hai nguoi iinh doi xung. ngoi d i i n g v i t r i => ( d p c m ) 7. Lubi diem la tap hop tat ca cac diem (x, y) trong mat phang vai it nhat mot V o i t r u o n g h g p chi c6 m p t n g u o i ngoi d i i n g , ta xet s y sap xep sau: diem CO tga do Id nguyen. Ggif(n) Id solan bdch bd gom n bubc doc theo lubi Bang ten: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ^iem hat ddu tit goc. Mot bubc co do ddi mot doit vi tugiao diem nay den giao Nguoi: 1 9 2 10 3 11 4 12 5 13 6 14 7 15 8 ^iem kia. Ta chi dem solan bdch hd sao cho moi diem chi di qua khong qud M o t phep quay d o i 1 sang 2 t r o n g hang, m p t phep q u a y d o i 3 sang 2 tronj' ^Qt Ian. Hay timfin) vai n = l,2,3,4 vd chieng minh rang: 2" < f(n)
Boi duang hoc sinh gioi Todn td'hqp - rod r(ic, Nguyen Van Thong Cty TNHHMI V ;' VH Khang Vift F(4) = 100 (theo bat k y h u o n g nao sau buoc t h i i 3 ngoai t r u 8 d u o n g saq Giai buoc t h u 3 chay v o n g q u a n h 3 canh mgt h i n h v u o n g -> chi c6 hai h u o n g kha dl Neu tat ca d u o n g thang song song v o i nhau t h i se ton tai m o t n u a m a t phang cho m o i t r u o n g hop) ^ tro'ng c> m o t ben ciia d u o n g thang cuo'i ciing; t r o n g do ta c6 the dat m o t d u o n g i Ta k h o n g the d i nguoc l a i h u o n g vira d i den, nen de b u o c t h i i 3, nen c}§ tron v o i ban k i n h I o n t u y y. N e u trai lai, lay m o t bao loi cua tat ca cac giao diem. buoc thijf 2 den buoc t h u n c6 m o t each chon k h o n g qua 3 h u o n g . Cac tia xuat phat t u bao loi nay k h o n g cat nhau o ngoai, the t h i c h i i n g phan tan, pgn CO the dat dugc cac d u o n g tron Ion t u y y giiia chung. (dpcm). D o do: F(n) < 4.3"-' • Ta chi ra t o n t a i m o t tap h g p cac d u o n g thang thoa y e u cau cua de la tap ' N e u ta l u o n d i t u hie den d o n g t h i ta k h o n g the d i q u a m o t d i e m h o n mot h(?p cac d u o n g thang song song v o i m p t true tga d p Ian l u g t qua cac d i e m h i r u Ian nen: F(n) > 2" ty ciia true kia. ^. .= : . : .^ : => ( d p c m ) J\lhdn xet:Bdi todn de ra khong ro rang, thay vi noi mgt tap hap dem dugci?), ta Nhan xet: v&i each chtmg mink tren, ta hoan toan ed the tim ra mot eong thuc ton^ nen noi la mgt tap hap cdc duong thang khdc mat phang thi se phii hap voi chung qudt cho fin) theo n roi m&i dm vac cong thiec do dechimg minh cdc bat dang thuc tren. minh hon. 8. Cdc so tit 1 den 50 duac xep rngt each tuy y thdnh 5 hang, moi hang c6 10 so. 10. Co 11 nhom bieu dim a mgt festival. Moi ngdy bat ky nhom nao khong bieu The thi moi hang duac xep lai sao cho cdc so'duac xep theo thii tu tang. The roi dien thi phai xem cdc nhom khdc dim (nhung cdc nhom dang bieu dim thi moi cot duac xep lai theo thu tu tang. Hoi cdc cgt c6 nhai thiei con theo thu tu khong phai xem cdc nhom khdc dim). So ngdy tot thieu Id bao nhieu de moi tang hay khong? nhom CO the xem moi nhom khdc dim it nhat mot Idn trong festival? Giai ^ G i a i V . . A , Tra l o i : c6 Xet t r u o n g h o p c6 n nhom. De dang thuc hi^n yeu cau de ra trong n ngay Sau k h i sap xep lai hang, ta g p i cac so 6 hang t h u nhat la ai, da,... aio cac so 6 (Nhom i dien ngay t h u i va cac nhom khac xem n h o m i bieu dien hoac ngugc lai) hang t h u hai la b i , hi,... bio v a c u the. ; tst'i Voi n = 3, ta can c6 3 ngay, n h o m 1 x e m n h o m 2, n h o m 2 x e m n h o m 3 va Gia s u rang sau k h i sap xep cot ta c6 x i d t r o n g cot I ciia hang k va yj 6 trong nhom 3 xem n h o m 1 phai dien ra vao cac ngay khac nhau. cot j ciia hang k (j > I). Ta can c h u n g m i n h rang x i < yj. V o i n = 4: gia s u rang 3 ngay la d i i , the t h i vao ngay nao do c6 2 n h o m bieu So t r o n g cot j thuoc hang k hay hang tren nhieu h o n m g t so v o i so t r o n g cot dien. Gia djnh rang n h o m 1 va 2 dien vao ngay t h u 1. The t h i ta can ngay niia de nhom 1 x e m n h o m 2 va n h o m 2 xem n h o m 1. Ta lai gia s u rang n h o m 1 xem I thuoc hang tren k. V i the phai c6 so Zj t r o n g cpt I thuoc hang k hay hang duoi nhom 2 vao ngay t h u 2 va n h o m 2 xem n h o m 1 vao ngay t h u 3. C h i c6 m o t ngay. ( z CO the bang x h a y y). D o d o xi < z i < zj < yj (dpcm) Va chi CO 3 ngay nen n h o m 1 chi dugc xem vao ngay t h u 2. D o d o n h o m 3 va jV/ian xet: bai toan nay twang tir nhir bai todn cho mgt so ngw&i dung thanh hinh nhom 4 phai dien vao ngay t h u 2. T u o n g t u h g cung dien vao ngay t h u 3. N h u vuong va xet cdc sap xep nguai cao nhat vd nguai thap nhat trong hang, cot trong sack y^y n h o m 3 va 4 k h o n g the xem nhau bieu d i | n . V 6 ly => phai c6 i t nhat 4 ngay Cdc bai todn so hgc va dgi so chgn Igc ciia D.O.ShkyarsI
Boi dttang hoc sink gioi Todn tohpp - riri rac, Nguyen Van Thong Cty TNHH MTV DWH Khang Vift do 4 ngay cung d i i cho truong hop n = 5. Tuy nhien dieu k i | n tren chi la die\ Xet n + 2 nguai choi. Goi A , B la cap diing gan nhau nhat (hay la mgt trong ki^n can va khong c6 menh de dao. cic cap gan nhau nhat). The thi A b i n B . Neu cho rang c6 ai ban A hay B thi Bay gio ta xet n = 12, ta c6 the to chuc trong 6 ngay (Va nhu the cung c6 tho ^^n nhan bj ban hai Ian. Chi c6 n + 2 phat sung, nen neu c6 mot nguoi bi ban to chuc cho 11 nhom trong 6 ngay): ; j.:. i, i i(yv, -* • w ^Qfx 1 Ian, thi c6 khong qua n nguoi bj ban trong so n + 1 nguoi con lai nen se 123 ABC xem 456DEF £.(3 it nhat mot nguai khong bj ban. Neu khong c6 ai ban A , B thi ta tach A , B ra 145ADE xem 236BCF rieng va trong n nguoi con lai theo gia thuyet se c6 mot nguoi khong bi ban. 246BDF xem 135 ACE N h u vay theo nguyen tac quy nap, mfnh de dung voi moi n le 356CEF xem 124ABD Voi n chan, khong the ket luan gi. Ta c6 the tach rieng ra tung cap bang 123456 xem ABCDEF nhau va each xa cac cap khac. N h u vay moi nguoi deu bi ban. Nguoc lai ta ABCDEF xem 123456 ch(?n nguoi dung xa nhung nguoi khac, con moi nguoi con lai dung gan Ta chung minh rang 5 ngay la khong the dii cho 11 nhom nhau, the thi anh ta se khong bj ban. Gia su ta chi can 5 ngay. M o i ngay it nhat 6 nhom trinh dien. V i vay phai c6 12. Cho n>4 diem trong mat phang, mot so diem trong chung dugc to mdu do 3 ngay voi it nhat 6 nhom xem hoac it nhat 6 nhom trinh dien. Nhung dicu va socdn lai dugc to mdu den. Khong c6 3 diem ndo trong chung c6 cung mdu md kien do c6 nghTa la c6 4 nhom hoac deu cung trinh dien trong 2 ngay hoac deu l^i thang hdng. Chiing minh rang ta c6 the'ttm dugc 3 diem cung mdu sao cho hai cijng xem trinh dien trong hai ngay. Nhung theo tren 4 nhom nay can hon 4 trong chung thi khong c6 diem khac mdu a tren doan not hai diem do. ngay de xem Ian nhau => mau thuan. Giai N h u vay voi 11 nhom thi so ngay can la 6 ngay. Tu gia thiet ta c6 the suy ra la c6 it nhat 5 diem, vi the phai c6 it nhat 3 diem cung mau, goi chiing la A i , B i , C i . ' JVhan xeV.ta c6 the chung minh tiep cho cdc tneang hoy n = 5,7 roi suy ra ban\; sau: Neu mot cap khong c6 diem khac mau a tren doan thSng noi chiing thi bai :i,:Hjqrh; 3 4 5 g J g p 10 11 11 toan da dugc giai. Neu ngugc lai, goi 3 diem khac mau la A 2 , B 2 , C 2 . Ke do lap lai qua trinh ngay 3 4 4 4 5 5 5 5 6 6 tren. Qua trinh nay phai ket thiic vi tai moi buoc ta c6 3 diem moi (khong c6 Nhung ta khong the suy ra hai todn tong quat: tint each bieu thi so ngay theo n hay diem nao a tren cac canh cua tam giac AnBnCn, v i moi diem cua tarn giac tim quy luat bien thien songdy. So dt khong thevi each chung minh tren dua vdo vice AnBnCn ngoai t r u dinh deu 6 trong tam giac An-iBn-iCn-i). Do do vai mot n nao tim ra mot cdch sap xep eho n roi dim vdo cdc truang hap v&i cdc sonhd hon deehi ra do thi A n B n C n la tam giac can tim (dpcm) rang khong the tim ra mot cdch xep it ngay han. Tuy nhien viec tim mot cdch xep cho n lai khong phu thugc vdo mot quy luat ndo cd. diing Giai ' ' Gia su menh de diing den n (n le) Ta phai chung minh hai v i f c: moi con khi leo den dinh ciia mot cai thang ^ao do va hai con khi khong the leo len den dinh tren cung mot cai thang. 184 ' 185
Boi dumig hoc sink gioi Todtt to hap - rcri r^c, Nguyen Van Thong Cty TNHH MTV DWH Khang Viet Ta g o i m g t bo p h a n la m o t p h a n cua thang 6 giua h a i d a y l i e n tiep. Ta Gpi An la tap h o p n h i i n g n g u d i d o n g y v d i i t nhat m o t t r o n g h a i n g u d i ben c h i i n g m i n h rang c h i m p t con k h i c6 the treo qua m o t bo phan cho trudc. i n h o Ian t h a m d d t h i i n . 6 tren ta da c h u n g m i n h rang An cz An+i v d i n > 1 . Gia s u trai l a i . The t h i gia d i n h con k h i A va B d e u treo q u a m o t bp ph^,^ nixa ta se c h u n g m i n h x o n g neu ta cd the c h u n g m i n h rang A n chua ca 25 nao do. G o i S la bo p h a n d a u tien m a A , B cung treo qua. N o k h o n g the la f d i v d i n nao d d . p h a n bat d a u ciia thang m a A treo len v i B k h o n g the treo len xit do, va cung ; V i cd m o t so le n g u d i q u a n h ban, k h o n g the xay ra t i n h h u d h g la m g i n g u d i k h o n g the la bo p h a n d a u cua cac thang khac v i the t h i A c i i n g k h o n g the treo L k h o n g d o n g y v d i ca h a i n g u d i ben canh m i n h d Ian t h a m d d t h u nhat. V i len. Cho nen no p h a i la m o t bo phan c6 sgi day R tai d i e m tha'p nhat. V i ca A , B Ig'Ai chua i t nhat h a i n g u d i . Va An c: An+i v d i m g i n , t o n t g i m g t T < 25 sao cho deu p h a i treo qua R t r u o c k h i d e n S, v i neu c h i i n g leo tu* d u d i len t h i ca hai * j « AT + 1 p h a i treo theo R c h i i k h o n g p h a i S. N h u n g nhu the t h i c6 n g h l a la ca hai phaj f Gia s u rang A T k h o n g chua tat ca 25 n g u d i ; ta se s u d u n g d i e u nay de c h i i n g treo qua bo p h a n tan c u n g tai d a u kia ciia sgi day, trai v o i d i n h nghia ciia s niinh m a u t h u a n . V i A T khac trong, nen phai cd hai n g u d i n g o i canh n h a u , ma D i e u d o da c h u n g m i n h k h a n g d i n h . H o n niia, chi m o t con k h i c6 the treo qua ta goi 1^ ^ Y' '^ho X e A T va y g A T . V i x € A T , a n h ta se tra I d i d Ian t h a m bo phan cuoi c i i n g cua m o t thang, phia tren day tren cung, cho nen k h o n g hoti 46 t h u T v a (T + 1). N h u n g y g A T , the nen cau tra I d i cua y d Ian t h a m d d t h u m o t con k h i d e n d i n h thang cua m o t thang. T khac v d i cau tra I d i ciia x. That ra, ta biet rang y k h o n g d o n g y v d i ca hai T u o n g t u , ta c h u n g m i n h rang m o t con k h i c6 the treo qua m o t bo phan cho ngudi n g o i canh d Ian t h a m d d t h u T, va v i the anh ta p h a i thay d d i y k i e n d t r u o c k h o n g qua m o t Ian. Gia d j n h ngugc lai. G p i S la bo p h a n t h i i nhat m a A Ian t h u T + 1 . D o d d d Ian t h a m d d t h u T + 1 , y p h a i tra I d i g i o n g x. D i e u nay vira treo qua. G o i R la sgi day bat d a u ciia S (theo c h u n g m i n h tren t h i phai c6 dan den rang y € A T + 1 , trai v d i d i e u la A T = A T +1 ( m a u thuan). V i the ta ket m o t sgi d a y n h u the). V i the hai Ian treo qua S phai d e n dgc theo R, nhun^ luan rang A i chua taJt ca 25 n g u d i , va the'la c h i i n g m i n h x o n g . ,\ d i e u d o CO nghla la no treo qua b g p h a n tan cung cua sgi d a y k i a h a i Ian, trai tMidn xet: Bai todn mai nhin thoat qua thi cd ve phuc tap nhitng sau khi dat cdc v o i d j n h nghia ciia S. D i e u d o da c h u n g m i n h cho khSng d j n h . N h u n g chi co lap hop ra thi tra nen rat rd rang; day la mot cdch dat hay c6 the ung dung trong m o t so h u u h a n b g phan, nen m o i con k h i phai d u n g l a i va p h a i d e n d i n h ciia nhieu hai todn khdc. m o t cai thang ( d p c m ) Co the ma rong bai todn cho truang hap n le bat ky vai cdch chung minh hodn todn jWian xet: Bai todn khong kho nhmg ddi hoi tu duy kha phuc tap ve viec hmh tuang tu. dung va xdc dinh hitmg gidi. Viec chia bai todn thdnh hai phan de chung minh da lam 15. Khodng dong [0, 50] la hap cua mot so huu han cdc khodng dong, moi doan cho bai todn tra nen minh bach, de hieu. c6 AQ ddi 1. Chdng minh rang mot so trong cdc khodng do c6 the bo di sao cho 14. Hai mucd lam nguai ngoi quanh mot cdi ban trdn. Cd moi gib c6 mgt cuoc cdc khodng con l^i titng ddi mgt phan ly vd co tang cgng do ddi > 25. & iv thdm do y kien, va moi nguai phai tra lai Yes hay No. Moi nguai phai xd sU nhu sau: 6 Idn thdm dd thd n, y kien cua anh ta giong voi y kien cua it nhat Ta c h u n g m i n h m g t ke't qua tdng quat h a n , d d la [0, 2n] = U A i |Ai| = 1 , A i la mot trong hai nguai ngoi ben canh, thi anh ta se c6 y kien Idn thttn + l giong khoang t h i t o n tai a i , aa,..., an sao cho Aai n A.ij = 0 nhu y kien Idn thu n; nhung neu y kien Idn thd n cua anh ta khdc voi ca hai ChoO