Toán rời rạc-Chương 4: Bài toán tồn tại pot

Ph ng pháp ch ng minh tr c ti p.

TOÁN R I R C

Lecturer: PhD Ngo Huu Phuc

Tel: 0438 326 077 Mob: 098 5696 580 Email: ngohuuphuc76@gmail.com

BÀI TOÁN T N T I

4.1 Gi i thi u bài toán (1/6)

 Trong n i dung ch ng 3, đ m s l ng các ph n t

c a t p h p, s các c u hình t h p tho mãn nh ng tính ch t nào đó, v i gi thi t s t n t i c a c u hình là

4.1 Gi i thi u bài toán (2/6)

1 Bài toán v 36 s quan (Euler đ ngh )

 Có m t l n ng i ta tri u t p t 6 trung đoàn m i trung

đoàn 6 s quan thu c 6 c p b c khác nhau: thi u uý, trung

uý, th ng uý, đ i uý, thi u tá, trung tá v tham gia duy t binh s đoàn b

 H i r ng có th x p 36 s quan này thành m t đ i ng hình vuông sao cho trong m i m t hàng ngang c ng nh m i

m t hàng d c đ u có đ i di n c a c 6 trung đoàn và c a

c 6 c p b c?

4.1 Gi i thi u bài toán (3/6)

2 Bài toán 4 m u

 Ch ng minh r ng m i b n đ trên m t ph ng đ u có th tô

b ng 4 m u, sao cho không có hai n c láng gi ng nào l i

b tô b i cùng m t màu

 Chú ý r ng ta xem nh m i n c là m t vùng liên thông và hai n c g i là láng gi ng n u chúng chung m t đ ng

biên gi i là m t đ ng liên t c

4.1 Gi i thi u bài toán (4/6)

3 Hình l c giác th n bí

 N m1910 Clifford Adams đ ra bài toán hình l c giác th n bí sau: Trên

19 ô l c giác hãy đi n vào các s t 1 đ n 19 sao cho t ng theo c 6

5

2 7

1

16 19

4.1 Gi i thi u bài toán (5/6)

4.1.2 M t s ph ng pháp gi i quy t bài toán t n t i đ n gi n

1 Ph ng pháp ch ng minh tr c ti p

 gi i quy t các bài toán t n t i, ph ng pháp đ n gi n nh t là

ch ra m t c u hình, m t ph ng án tho mãn các đi u ki n đã cho.

4.1 Gi i thi u bài toán (6/6)

4.1.2 M t s ph ng pháp gi i quy t bài toán t n t i đ n gi n

2 Ph ng pháp ph n ch ng

 M t trong nh ng cách gi i bài toán t n t i là dùng l p lu n ph n

ch ng gi thi t đi u đ nh ch ng minh là sai t đó d n đ n m u thu n

4.2 Nguyên lý Dirichlet (1/12)

4.2.1 M đ u

 Nguyên lý Dirichlet đ c phát bi u nh sau:

 N u x p nhi u h n n đ i t ng vào n cái h p thì t n t i ít

nh t m t h p ch a không ít h n 2 đ i t ng

4.2 Nguyên lý Dirichlet (2/12)

 Ví d 01:

 M t n m có nhi u nh t 366 ngày Do v y trong s 367 ng i b t

k bao gi c ng có ít nh t 2 ng i có cùng ngày sinh

 Ví d 02:

 Thang đi m bài ki m tra đ c cho t 0 đ n 10, t c là có 11

thang đi m khác nhau Do v y, trong s 12 sinh viên b t k c a

l p s có ít nh t 2 ng i có k t qu bài ki m tra gi ng nhau

 Ví d 03:

 C p b c quân hàm c a s quan có 8 c p t thi u uý đ n đ i tá

Do v y trong m t đ n v có 9 s quan thì s có ít nh t hai ng i cùng c p b c

 Không th đ ng th i có m t giá tr 0 và 19 vì n u trong t p  có giá tr 0

t c là có m t thành ph cô l p thì s không có thành ph nào đ c n i

v i c 19 thành ph còn l i, ng c l i c ng v y

 Do đó t p  ch có t i đa 19 giá tr khác nhau Theo nguyên lý Dirichlet

s t n t i ít nh t m t c p i  j sao cho a = a

4.2 Nguyên lý Dirichlet (4/12)

 Ví d 05:

 Cho n m đi m M1(x1,y1), M2(x2,y2), M3(x3,y3), M4(x4,y4), M5(x5,y5) có các

to đ nguyên trên m t ph ng to đ Decac Ch ng minh r ng t n t i ít

nh t hai đi m mà có to đ trung đi m c a đo n th ng n i hai đi m đó

là các s nguyên

 L i gi i:

 t  = M 1 , M 2 , M 3 , M 4 ,M 5 

 Xây d ng ánh x f(Mi)=(xi mod 2, yi mod 2) t c là f :  -> B2

 Ta có N() =5, N(B 2 )=4, theo nguyên lý Dirichlet t n t i Mi Mj sao cho f(Mi) = f(Mj) t c là các to đ c a hai đi m theo tr c x và y đ u cùng

ch n ho c cùng l

 V y trung đi m c a đo n th ng n i hai đi m này có t o đ là các s nguyên

4.2 Nguyên lý Dirichlet (5/12)

 Ví d 06:

 Khi ki m kê danh m c 80 chi ti t

 M i chi ti t có th đ c đánh giá là “t t” ho c “không t t”

 Có 50 chi ti t đ c đánh giá là “t t”

 Ch ng minh r ng có ít nh t hai chi ti t đ c đánh giá là

“không t t” có s th t cách nhau 3 ho c 6 đ n v

4.2 Nguyên lý Dirichlet (6/12)

 L i gi i ví d 06:

  = a1, a2, …, a30, 1  ai  80 là t p các s th t khác nhau c a các chi ti t đ c đánh giá là "không t t",

 Các s bi, bj không đ ng th i n m trong , bi, bj c ng không đ ng th i

n m trong ’ và bi, bj c ng không đ ng th i n m trong ’’

 V y ch có th là bi = ai  và bj = ak +3 ’, t c là ai = ak +3 ho c bi =

ai  và bj = aq +6 ’’, t c là ai = ak +6 ho c bi = ak+3 ’ và bj = aq+6  ’’, t c là a = a +3

4.2 Nguyên lý Dirichlet (8/12)

4.2.2 Nguyên lý Dirichlet t ng quát

 Theo ngôn ng t p h p và ánh x , nguyên lý Dirichlet t ng quát có th phát bi u nh sau :

 Cho X và Y là t p h u h n f : X -> Y là ánh x t X vào Y, g i N(X) = n, N(Y) = m và k = [n/m], khi đó t n t i không ít h n k

ph n t c a t p X : x1  x2  xk sao cho f(x1) = f(x2)= = f(xk)

 Ch ng minh Ta dùng ph ng pháp ph n ch ng, không gi m tính t ng quát ta ký hi u ta ký hi u X = x1, x2, …, xn và Y = y1,

y2, …, ym, Xi = {x X / f(x)= yi} Gi s N(Xi)  k-1 v i 1  i  m, n= N(X) = N(X )  (k-1)m <km<n, t đó suy ra t n t i N(X )  k

4.2 Nguyên lý Dirichlet (9/12)

 Ví d 07: Trong 150 ng i có ít nh t ng i cùng tháng sinh

 Ví d 08:

 C n ph i có t i thi u bao nhiêu sinh viên ghi tên vào l p toán h c R i r c

đ ch c ch n r ng s có ít nh t 6 ng i đ t cùng m t đi m thi, n u thang

đi m g m 6 b c 0,1,2,3,4,5?

nguyên nh nh t sao cho S đó là N = 6.5 + 1 = 31

 Ví d 09:

 Ch ng minh r ng có p s 1 và q s 0 x p thành vòng tròn theo tr t t ng u nhiên, n u p, q, k là các s nguyên d ng tho mãn đi u ki n p  kq thì t n

t i ít nh t m t dãy không ít h n k s 1 đi li n nhau

nguyên lý Dirichlet t n t i ít nh t m t khe có không ít h n  k s 1.

4.2 Nguyên lý Dirichlet (10/12)

 Ví d 10 :

 Trong m t tháng 30 ngày m t công nhân làm ít nh t m i

ngày m t s n ph m, nh ng c tháng làm không quá 45 s n

ph m

 Ch ng minh r ng có nh ng này liên ti p ng i này làm ra đúng 14 s n ph m

 i u này có ngh a là t ngày j + 1 t i h t ngày i ng i đó đã làm đúng 14 s n

ph m.

 Vì ch có n s nguyên d ng l nh h n 2n nên theo nguyên lý Dirichlet t n

t i hai trong s l q1, q2, …, qn+1 b ng nhau, t c là có hai ch s i và j sao cho

qi = qj = q (q là giá tr chung c a chúng)

 Khi đó ai = và aj = Suy ra n u ki  kj thì aj chia h t cho ai còn trong

tr ng h p ng c l i a chia h t cho a

j j k

q

2

 Ví d :

 S={1,2,3,4,5}, S1 = {2,5},S2 ={2,5},S3 ={1,2,3,4}, S4={2,5}

 H này không t n t i TRAN vì S1S2S4={2,5} có ít h n 3 ph n t

2 1

4.3 H đ i di n phân bi t (5/15)

4.3.2 nh lý Hall (ti p)

nh ngh a

 i u ki n (1) (N(Si1Si2 Sik)  k) đ c g i là đi u ki n Hall

 G i m t h con c a h S1, S2, ,Sm g i là h con t i h n

n u đ i v i nó b t đ ng th c (1) tr thành đ ng th c

 Theo gi thi t qui n p h này có ít nh t (t-1)! TRAN khi t-1  m-1

hay t  m và có ít nh t (t-1)!/(t-m)! khi t-1>m-1 hay t > m

 M t khác m i TRAN c a S2’,S3’, ,Sm’,cùng v i a1, xác đ nh m t TRAN c a S2’,S3’, ,Sm’ (a1 đ i di n cho S1)

 i u này đúng cho m i cách ch n a1 trong s ít nh t t cách ch n

nó t S1.T đó nh n đ c đánh giá c n ch ng minh.

4.3 H đ i di n phân bi t (10/15)

 Có m ng i thi hành và n công vi c gi s v i m i ng i th i,

ta bi t đ c t p Si là t p h p các công vi c mà ng i đó có th làm H i có th phân công m i ng i làm m t vi c không?

 L i gi i c a bài toán d n v vi c xét s t n t i TRAN c a h (Si)

và vi c xây d ng m t TRAN chính là xây d ng m t s phân

công nh th

4.3 H đ i di n phân bi t (11/15)

 T i m t làng quê n có m chàng trai đ n tu i l y v v i m i

chàng trai i ta bi t t p S i các cô gái mà chàng ta thích

 H i r ng có th ghép m i cô cho m i chàng mà chàng nào

c ng v a ý hay không?

 L i gi i d n đ n vi c xét s t n t i TRAN c a h (Si) Trong

tr ng h p t n t i m i TRAN s t ng ng v i m t cách ghép mong mu n

4.3 H đ i di n phân bi t (12/15)

Ví d 01:

 Có 5 giáo viên là Anh, Bình, C ng, D ng, Giang m i giáo viên có th gi ng d y m t s môn h c sau:

 Anh d y đ c các môn {Toán, Lý, Sinh}=S1,

 Bình d y đ c {Toán, Sinh, K thu t}=S2,

4.3 H đ i di n phân bi t (13/15)

 T đó nh n đ c s TRAN c n đ m là Dn, (bài toán b

th )

 bài toán xác đ nh c v i n=1 ta xem trong tr ng h p này S1={1}

 G i Fn là s TRAN c n đ m ( ng v i n >1) Chia các TRAN này thành 2 lo i :

 {1} là đ i di n cho S1 khi đó các thành ph n còn l i s là m t h đ i di n c a h {2,3},{2,3,4}, ,{n-1,n} do v y lo i này có Fn-1 TRAN

 {2} là đ i di n cho S1 khi đó b t bu c {1} ph i là đ i di n cho S2 và các thành

ph n còn l i s là m t h đ i di n c a h {3,4},{4,5}, ,{n-1,n}do v y lo i này có Fn-2 TRAN

 T đó nh n đ c h th c Fn=Fn-1+Fn-2 Các giá tr F1=1, F2=2 đ c tính tr c

ti p đây c ng là h th c truy h i xác đ nh các s Fibonaci

Ch ng minh r ng t n t i ít nh t 3 c u th đ ng li n nhau

có t ng các s áo ít nh t là 26

4.4 Bài t p (2/2)

Bài 3 : Cho (Xi, Yi ,Zi ) i=1,…,9 là to đ nguyên c a 9 đi m

trong không gian ba chi u Ch ng minh r ng t n t i ít nh t

m t đo n th ng n i 2 đi m trong s đó có trung đi m to

đ nguyên

Bài 4 : Ch ra r ng trong dãy m s nguyên d ng b t k

t n t i ít nh t m t dãy các s h ng liên ti p có t ng chia

h t cho m