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