Giáo trình Toán rời rạc - Trường Cao đẳng Cơ điện Hà Nội

Tr êng Cao §¼ng C¬ §iÖn Hµ Néi

Ch ¬ng 1. Lý thuyÕt tæ hîp

1.1. S¬ l îc vÒ tæ hîp:

Tæ hîp lµ mét phÇn quan träng cña to¸n häc rêi r¹c chuyªn nghiªn

cøu sù s¾p xÕp c¸c ®èi t îng, chñ ®Ò nµy ®· ® îc nghiªn cøu tõ thÕ kû 17.

Khi nh÷ng trß ch¬i may rñi, liÖt kª,®Õm c¸c ®èi t îng cã nh÷ng tÝnh chÊt

nµo ®ã lµ mét phÇn quan träng cña lý thuyÕt tæ hîp. VÝ dô ta dïng quy t¾c

®Õm ®Ó tÝnh tÊt c¶ c¸c sè ®iÖn tho¹i cã thÓ cã trªn toµn n íc Mü, sè mËt

khÈu cho phÐp truy nhËt hÖ m¸y tÝnh, liÖt kª c¸c thø tù vÒ ®Ých kh¸c nhau

cña c¸c vËn ®éng viªn cã thÓ x¶y ra trong cuéc ch¹y thi.

Mét bµi to¸n kh¸c trong lý thuyÕt tæ hîp lµ viÖc t¹o ra c¸c c¸ch s¾p

xÕp theo mét kiÓu nµo ®ã. VÊn ®Ò nµy rÊt quan träng trong c¸c m« pháng

m¸y tÝnh.

1.1.1. Quy t¾c céng:

Gi¶ sö cã hai c«ng viÖc. ViÖc thø nhÊt cã thÓ lµm b»ng n₁c¸ch, viÖc

thø hai cã thÓ lµm b»ng n₂c¸ch vµ nÕu hai viÖc nµy kh«ng thÓ lµm ®ång thêi,

khi ®ã sÏ cã n₁+n₂c¸ch lµm mét trong hai viÖc ®ã.

VÝ dô1: Gi¶ sö cÇn chän hoÆc lµ mét c¸n bé cña khoa tin hoÆc lµ mét

sinh viªn tin lµm ®¹i biÓu trong héi ®ång cña mét tr êng. Hái cã bao nhiªu

c¸ch chän vÞ ®¹i biÓu nµy nÕu khoa tin cã 37 c¸n bé vµ 83 sinh viªn?.

Chóng ta më r«ng quy t¾c céng cho tr êng hîp cã nhiÒu h¬n hai c«ng

viÖc. Gi¶ sö c¸c viÖc T₁, T₂, …,T_mcã thÓ lµm t ¬ng øng b»ng n₁, n₂, …, n_m

c¸ch vµ gi¶ sö kh«ng cã hai viÖc nµo ®ã cã thÓ lµm ®ång thêi. Khi ®ã sè

c¸ch lµm mét trong m viÖc ®ã lµ n₁+n₂+….+n_m.

VÝ dô2: Mét sinh viªn cã thÓ chän bµi thùc hµnh m¸y tÝnh tõ mét trong

ba danh s¸ch t ¬ng øng cã 23, 15 vµ 19 bµi. Cã bao nhiªu c¸ch chän bµi

thùc hµnh?.

Quy t¾c céng cã thÓ ph¸t biÓu d íi d¹ng ng«n ng÷ tËp hîp nh sau:

NÕu A₁, A₂, …, A_mlµ c¸c tËp rêi nhau, khi ®ã sè phÇn tö cña hîp c¸c tËp hîp

1

Khoa C«ng NghÖ Th«ng Tin

Tr êng Cao §¼ng C¬ §iÖn Hµ Néi

nµy b»ng tæng sè c¸c phÇn tö cña c¸c tËp thµnh phÇn.

A  A ... A_m A  A ... A_m

1

2

1

2

1.1.2. Quy t¾c nh©n:

Gi¶ sö nhiÖm vô nµo ®ã ® îc t¸ch ra lµm hai viÖc. ViÖc thø nhÊt cã

thÓ lµm b»ng n₁c¸ch, viÖc thø hai cã thÓ lµm b»ng n₂c¸ch sau khi thùc hiÖn

viÖc thø nhÊt ®· lµm, khi ®ã sÏ cã n n₂c¸ch thùc hiÖn nhiÖm vô nµy.

1

VÝ dô3: Trong mét trung t©m m¸y tÝnh cã 32 chiÕc m¸y vi tÝnh. Mçi

m¸y cã 24 cæng. Hái cã bao nhiªu cæng kh¸c nhau trong trung t©m nµy?.

Quy t¾c nh©n më réng:

Gi¶ sö r»ng mét nhiÖm vô nµo ®ã ® îc thi hµnh b»ng c¸ch thùc hiÖn

c¸c viÖc T₁, T₂, …,T_m. NÕu viÖc T_icã thÓ lµm b»ng n_ic¸ch sau khi c¸c viÖc

T₁, T₂, …,T_i-1®· ® îc lµm, khi ®ã cã n n₂...n_mc¸ch thi hµnh nhiÖm vô ®·

1

cho.

VÝ dô4: Cã bao nhiªu biÓn ®¨ng kÝ xe « t« nÕu mçi biÓn chøa mét d·y

ba ch÷ c¸i tiÕp sau lµ ba ch÷ sè (kh«ng bá d·y ch÷ nµo ngay c¶ khi nã cã ý

nghÜa kh«ng ®Ñp).

Quy t¾c nh©n th êng ® îc ph¸t biÓu b»ng ng«n ng÷ tËp hîp nh sau:

NÕu A₁, A₂, …, A_mlµ c¸c tËp h÷u h¹n, khi ®ã sè phÇn tö cña tÝch

§Ò-c¸c cña c¸c tËp hîp nµy b»ng tÝch sè c¸c phÇn tö cña c¸c tËp thµnh phÇn.

A  A ... A_m A  A ... A_m

1

2

1

2

1.1.3. C¸c cÊu h×nh tæ hîp ®¬n gi¶n:

1.1.3.1. Ho¸n vÞ

Cho tËp A gåm n phÇn tö (n 1). Mçi c¸ch s¾p xÕp thø tù n phÇn tö

cña tËp hîp A ® îc gäi lµ mét ho¸n vÞ cña n phÇn tö ®ã.

P  n!123....(n1)n

n

Quy íc: 0!=1

1!=1

VÝ dô5: 6 ng êi xÕp thµnh hµng ngang ®Ó chôp ¶nh. Hái cã thÓ bè trÝ

bao nhiªu kiÓu?.

2

Khoa C«ng NghÖ Th«ng Tin

Tr êng Cao §¼ng C¬ §iÖn Hµ Néi

1.1.3.2. ChØnh hîp:

Cho tËp hîp A gåm n phÇn tö. Mçi bé gåm k phÇn tö ( 0  k  n ) s¾p

thø tù cña tËp hîp A lµ mét tæ hîp chÊp k cña n phÇn tö.

A^k n(n 1)....(n k 1)

n

n!



(n  k)!

VÝ dô 6: Gi¶ sö r»ng cã t¸m vËn ®éng viªn ch¹y thi. Ng êi th¾ng sÏ

nhËn huy ch ¬ng vµng, ng êi vÒ ®Ých thø hai nhËn huy ch ¬ng b¹c, ng êi vÒ

®Ých thø ba nhËn huy ch ¬ng ®ång. Cã bao nhiªu c¸ch trao c¸c huy ch ¬ng

nµy nÕu tÊt c¶ c¸c kÕt côc cña cuéc thi ®Òu cã thÓ x¶y ra?.

1.1.3.3. Tæ hîp:

Cho tËp hîp A gåm n phÇn tö. Mçi tËp con gåm k phÇn tö ( 0  k  n

)

cña tËp hîp A lµ mét chØnh hîp chÊp k cña n phÇn tö.

n!

C_n^k

k!(n  k)!

VÝ dô7: Cã bao nhiªu c¸ch tuyÓn 5 trong sè 10 cÇu thñ cña mét ®éi

bãng quÇn vît ®Ó ®i thi ®Êu t¹i mét tr êng kh¸c?.

C¸c tÝnh chÊt cña hÖ sè tæ hîp:

a) TÝnh ®èi xøng

C_n^k C_n^nk

b) §iÒu kiÖn ban ®Çu

C_n⁰ C_nⁿ1

c) C«ng thøc ®Ö qui

n1

C_n^k C C_n^k_1

,

n >k >0

Tõ c«ng thøc b) vµ c), ta cã thÓ tÝnh tÊt c¶ c¸c hÖ sè tæ hîp chØ b»ng phÐp

céng. C¸c hÖ sè nµy ® îc tÝnh vµ viÕt lÇn l ît theo tõng dßng ( mçi dßng chØ

øng víi gi¸ trÞ n=0, 1, 2,…) theo b¶ng tam gi¸c d-ãi ®©y:

C₀⁰

C₁⁰

C₁¹

3

Khoa C«ng NghÖ Th«ng Tin

Tr êng Cao §¼ng C¬ §iÖn Hµ Néi

…

… … …

…

C_n⁰

C_n¹

…

C_n^n1

C_nⁿ

…

B¶ng nµy gäi lµ tam gi¸c Pascal.

C¸c hÖ sè tæ hîp cã liªn quan chÆt chÏ víi viÖc khai triÓn luü thõa cña

mét nhÞ thøc

(x  y)ⁿ C_n⁰xⁿC_n¹x^n1y ...C_n^n1y^n1C_nⁿyⁿ

C«ng thøc trªn ® îc gäi lµ c«ng thøc khai triÓn nhÞ thøc Newton vµ

c¸c hÖ sè cña nã ® îc gäi lµ c¸c hÖ sè cña nhÞ thøc.

1.2. Bµi to¸n ®Õm vµ ph ¬ng ph¸p gi¶i

1.2.1. Giíi thiÖu bµi to¸n

Mét trong nh÷ng vÊn ®Ò ®Çu tiªn cña viÖc nghiªn cøu tæ hîp lµ ®Õm

xem cã bao nhiªu cÊu h×nh tæ hîph cã thÓ ® îc t¹o ra víi nh÷ng quy t¾c ®·

nªu ? Nh÷ng bµi to¸n nh vËy ® îc gäi lµ bµi to¸n ®Õm tæ hîp. Th«ng

th êng, lêi gi¶i cña bµi to¸n ®Õm phô thuéc vµo mét sè gi¸ trÞ tham sè ban

®Çu vµ ng êi ta cè g¾ng biÓu diÔn sù phô thuéc nµy b»ng nh÷ng c«ng thøc

to¸n häc. Nãi chung, ®Ó ®Õm c¸c cÊu h×nh ®· cho, ng êi ta t×m c¸ch ® a vÒ

c¸c cÊu h×nh quen thuéc b»ng c¸c thiÕt lËp mét t ¬ng quan 1-1 gi÷a chóng.

NhiÒu khi mét bµi to¸n ®Õm ® îc ph©n thµnh nh÷ng bµi to¸n ®Õn nhá h¬n

b»ng c¸ch chia viÖc ®Õm thµnh tõng líp ®Ó ¸p dông nguyªn lý céng hoÆc

ph©n tÝch cÊu h×nh cÇn ®Õm nh lµ viÖc ghÐp mét sè cÊu h×nh kh¸c ®Ó ¸p

dông nguyªn lý nh©n. D íi ®©y lµ mét sè kü thuËt ®Õm.

VÝ dô 1. Cã bao nhiªu c¸ch xÕp 5 ng êi ®øng thµnh mét hµng ngang

sao cho A kh«ng ®øng c¹nh B ?

Gi¶i: §Ó ®Õm sè c¸ch xÕp nµy, ta ®Õm phÇn cßn l¹i: sè c¸ch xÕp mµ A

®øng c¹nh B. Xem A vµ B nh mét chç, ta cã 4!= 24 c¸c xÕp. Sè nµy cÇn

® îc nh©n 2 v× A cã thÓ ®øng bªn tr¸i còng nh bªn ph¶i B. Nh vËy cã tÊt

4

Khoa C«ng NghÖ Th«ng Tin

Tr êng Cao §¼ng C¬ §iÖn Hµ Néi

c¶ 48 c¸ch xÕp A ®øng c¹nh B. Toµn bé cã 5! = 120c¸ch xÕp. Tõ ®ã nhËn

® îc sè c¸ch xÕp mµ A kh«ng ®øng c¹nh B lµ 120 – 48 = 72 c¸ch.

VÝ dô 2. Mét ®ît ph¸t hµnh xæ sè víi c¸c sè vÐ gåm 2 phÇn: phÇn ®Çu

gåm 2 ch÷ c¸i lÊy tõ A ®Õn Z (26 ph©n tö) vµ phÇn sau gåm 4 ch÷ sè lÊy tõ 0

®Õn 9 910 ph©n tö). Hái x¸c xuÊt ®Ó tróng gi¶i ®éc ®¾c lµ bao nhiªu ?

Gi¶i: Tr íc hÕt ta ®Õm sè vÐ ® îc ph¸t hµnh. Mçi vÐ gåm 2 phÇn:

phÇn ch÷ vµ phÇn sè. PhÇn ch÷ cã 26²kh¶ n¨ng, phÇn sè cã 10⁴kh¶ n¨ng.

Theo nguyªn lý nh©n, sè vÐ ® îc ph¸t hµnh lµ 26²x 10⁴= 6 760 000. Tõ ®ã

nhËn ® îc x¸c suÊt ®Ó tróng gi¶i ®éc ®¾c lµ:

1 / 6 760 000 ~ 1,48 x 10^-7

VÝ dô 3. Cho mét l íi gåm c¸c « vu«ng. C¸c nót ® îc ®¸nh sè tõ 0

®Õn n theo chiÒu tõ tr¸i sang ph¶i vµ tõ 0 ®Õn m theo chiÒu tõ d íi lªn trªn

(xem h×nh vÏ). Hái cã bao nhiªu ® êng ®i kh¸c nhau tõ nót (0,0) ®Õn nót

(n,m) nÕu chØ cho phÐp ®i trªn c¹nh c¸c « vu«ng theo chiÒu sang ph¶i hoÆc

lªn trªn ?

(0,m)

(n,m)

(0,0)

(n,0)

Gi¶i : Mét ® êng ®i nh thÕ ® îc xem gåm n+m ®o¹n (mçi ®o¹n lµ

mét c¹nh « vu«ng). T¹i mçi ®o¹n chØ ® îc chän mét trong 2 gi¸ trÞ : ®i lªn

(mµ ta m· lµ 1) hay sang ph¶i (mµ ta m· lµ 0). Sè ®o¹n ®i lªn ®óng b»ng m

vµ sè ®o¹n sang ph¶i ®óng b»ng n. Bµi to¸n dÉn vÒ viÖc t×m xem cã bao

nhiªu d·y nhÞ ph©n ®é dµi n + m trong ®ã cã ®óng m thµnh phÇn b»ng 1. ®©y

5

Khoa C«ng NghÖ Th«ng Tin

Tr êng Cao §¼ng C¬ §iÖn Hµ Néi

còng chÝnh lµ sè tËp con m ph©n tö cña mét tËp n + m phÇn t, v× thÕ sè ® êng

®i cÇn ®Õm b»ng C_n^m_m

VÝ dô 4 : ThuËt to¸n ‘næi bät’ dïng ®Ó xÕp t¨ng dÇn d·y a_i(i =

1,2,....,n) ® îc m« t¶ b»ng ®o¹n ch ¬ng tr×nh PASCAL d íi ®©y :

For i : = 2 to n do

Forj : = n down to i do

I  a[ j  I]  a[ j]thenSwap(a[ j  I],a[ j];

H·y ®Õm xem ph¶i lµm bao nhiªu phÐp so s¸nh?

Gi¶i: Ta chia sè phÐp so s¸nh thµn c¸c líp theo vßng lÆp i (i ®i tõ 2

®Õn n). Víi mçi i x¸c ®Þnh, ph¶i thùc hiÖn n-i+1 phÐp so s¸nh. Tõ ®ã nhËn

® îc, theo nguyªn lý céng, sè c¸c phÐp so s¸nh lµ:

n(n 1)

(n 1)  (n  2) ... 1 

2

Cã thÓ lý luËn g¹n h¬n: thuËt to¸n ‚næi bät‛ viÕt trong ®o¹n ch-¬ng

tr×nh ®· cho ph¶i so s¸nh tÊt c¶ c¸c cÆp phÇn tö kh¸c nhau. Tõ ®ã nhËn ® îc

sè phÐp so s¸nh lµ:

n(n 1)

C_n²

2

Mét ®Æc tÝnh cña c¸c bµi to¸n ®Õm tæ hîp lµ sè cÊu h×nh t¨ng rÊt

nhanh khi sè gi¸ trÞ tham gia vµo viÖc t¹o nªn cÊu h×nh ®ã t¨ng. §iÒu nµy

th êng dÉn ®Õn c¸c con sè khæng lå mÆc dï c¸c con sè tham gia ban ®Çu

kh«ng lín. HiÖn t îng nµy th êng ® îc gäi lµ sù bïng næ tæ hîp vµ chÝnh nã

lµ nguyªn nh©n lµm cho c¸c thuËt to¸n dùa vµo viÖc duyÖt toµn bé trë nªn

kh«ng kh¶ thi. ThÝ dô d íi ®©y cho thÊy r»ng, dï qui c¸ch t¹o cÊu h×nh cã vÓ

rÊt h¹n chÕ nh ng sè cÊu h×nh ® îc t¹o, ho¸ ra l¹i rÊt lín.

VÝ dô 5. Ng«n ng÷ PASCAL chuÈn qui ®Þnh ®Æt tªn biÕn kh«ng qu¸ 8

ký tù. C¸c ký tù trong tªn biÕn chØ ® îc phÐp lµ c¸c ch÷ c¸i (tõ A ®Õn Z)

hoÆc c¸c ch÷ sè (tõ 0 ®Õn 9) vµ ph¶i b¾t ®Çu b»ng ch÷ c¸i. Hái cã thÓ ®Þnh

nghÜa bao nhiªu biÕn kh¸c nhau ?

6

Khoa C«ng NghÖ Th«ng Tin

Tr êng Cao §¼ng C¬ §iÖn Hµ Néi

Gi¶i : Ta ph©n c¸c biÕn thµnh c¸c líp: 1-ký tù, … Sè c¸c biÕn thuéc

líp k-ký tù, theo nguyªn lý nh©n, b»ng 26 x 36^k-1(k = 1,2, …, 8). Tõ ®ã, theo

nguyªn lý céng, ta nhËn ® îc sè c¸c biÕn kh¸c nhau lµ:

26.(1+36+36²+ … +36⁷) = 2 095 681 645 538.

1.2.2. Nguyªn lý bï trõ

Mét sè bµi to¸n ®Õm phøc t¹p h¬n, ® îc dùa vµo nguyªn lý tæng qu¸t

cña nguyªn lý céng. NÕu kh«ng cã gi¶ thiÕt g× vÒ sù rêi nhau gi÷a 2 tËp A vµ

B th×

 

N(A B) = N(A) + N(B) – N(A B).

C«ng thøc (1) ® îc më réng cho tr êng hîp nhiÒu tËp nh sau.

§Þnh lý. Gi¶ sö A₁,A₂, …, A_mlµ c¸c tËp h÷u h¹n. Khi ®ã

N(A₁

Trong ®ã N_klµ tæng phÇn tö cña tÊt c¶ c¸c giao cña k tËp lÊy tõ m tËp

®· cho (nãi riªng N₁= N(A₁) + … + N(A_m), N_m= N(A₁A₂...A_m).

Chøng minh. Chó ý r»ng, sè c¸c giao cña k tËp lÊy tõ m tËp b»ng C_m^k_,

k = 1,2, …, m. §Ó chøng minh c«ng thøc (1), ta sÏ tÝnh xem mçi phÇn tö cña

tËp A₁A₂... A_m® îc ®Õm bao nhiªu lÇn trong vÕ ph¶i cña nã. XÐt mét

 

A₂

… A_m) = N₁– N₂+ … + (-1)^m-1N_m,



,



phÇn tö tuú ý a A  A₂... A_m1.Gi¶ sö a lµ phÇn tö cña k tËp trong sè m

1

tËp ®· cho. Khi ®ã a ® îc ®Õm ë vÕ ph¶i cña c«ng thøc (1)

C_k¹C_k² C_k³... (1)^k1C_k^k

LÇn do

C_k¹C_k² C_k³... (1)^k1C_k^k

1[1C_k¹ C_k²C_k³... (1)^kC_k^k] 1 (11)^k1

,

Suy ra mçi phÇn tõ a A  A₂... A_m® îc tÝnh ®óng 1 lÇn ë vÕ ph¶i

1

cña c«ng thøc (1) , ®iÒu ®ã ®· chøng minh tÝnh ®óng ®¾n cña c«ng thøc (1).

B©y giê ta ®«ng nhÊt tËp A_kvíi tÝnh chÊt A_kcho trªn mét tËp X nµo ®ã

vµ ®Õm xem cã bao nhiªu phÇn tö cña X kh«ng tho¶ m·n bÊt cø mét tÝnh chÊt

A_knµo c¶.

7

Khoa C«ng NghÖ Th«ng Tin

Tr êng Cao §¼ng C¬ §iÖn Hµ Néi

Gäi N lµ sè cÇn ®Õm, N lµ sè phÇn tö cña X, ta cã:

N  N  N(A  A₂...A_m)  N  N₁ N₂... (1)^mN_m

(3)

1

Trong ®ã N_klµ tæng c¸c phÇn tö cña X tho¶ m·n k tÝnh chÊt lÊy tõ m

tÝnh chÊt ®· cho.

C«ng thøc (3) ® îc gäi lµ nguyªn lý bï trõ. Nã cho phÐp tÝnh

c¸c N_ktrong tr êng hîp c¸c sè nµy dÔ tÝnh to¸n h¬n.

Ta sÏ xÐt mét sè thÝ dô minh ho¹ cho viÖc sö dông nguyªn lý bï trõ ®Ó

gi¶i c¸c bµi to¸n ®Õm.

N

qua

VÝ dô 6: Hái trong tËp X=[1,2,…, 10000] cã bao nhiªu sè kh«ng chia

hÕt cho bÊt cø sè nµo trong c¸c sè 3,4,7?

Gi¶i. Gäi

A 



x X : xchia hÕt cho i , i=3,4,7.



i

Khi ®ã A₃ A₄ A₇lµ tËp c¸c sè trong X chia hÕt cho Ýt nhÊt mét trong

3 sè 3,4,7, suy ra theo c«ng thøc (3), sè l îng c¸c sè cÇn ®Õm sÏ lµ

N(X)  N(A₃ A₇)  N₁ N₂ N_3.

Ta cã

N₁ N(A₃)  N(A₄)  N(A₇)

 [10000/3][10000/ 4][10000/ 7]

 3333  2500 1428  7261,

N₂ N(A  A ) N(A  A ) N(A  A )

7

3

4

3

7

4





10000/(34)







10000/(37)







10000/(47)



 833 476 357 1666,

N₃ N(A  A  A ) 

10000/(347)



11

3

4

7

Ký hiÖu [r] ®Ó chØ sè nguyªn lín nhÊt kh«ng v ît qu¸ r.

Tõ ®ã sè l îng c¸c sè cÇn ®Õm lµ 10000-7261+1666-119=4286.

1.3. Bµi to¸n tån t¹i vµ ph ¬ng ph¸p gi¶i

1.3.1. Giíi thiÖu bµi to¸n

Trong môc tr íc, ta ®· tËp trung chó ý vµo viÖc ®Õm sè c¸c cÊu h×nh

tæ hîp (sè phÇn tö cña c¸c ®èi t îng tæ hîp) tho¶ m·n nh÷ng tÝnh chÊt nµo

8

Khoa C«ng NghÖ Th«ng Tin

Tr êng Cao §¼ng C¬ §iÖn Hµ Néi

®ã, ch¼ng h¹n ®Õm sè tæ hîp, chØnh hîp, ho¸n vÞ, … Trong nh÷ng bµi to¸n

®ã sù tån t¹i cña c¸c cÊu h×nh lµ hiÓn nhiªn vµ c«ng viÖc chÝnh lµ ®Õm sè

phÇn tö tho¶ m·n tÝnh chÊt ®Æt ra. Tuy nhiªn, trong rÊt nhiÒu baßi to¸n tæ

hîp, viÖc chØ ra sù tån t¹i cña mét cÊu h×nh tho¶ m·n c¸c tÝnh chÊt cho tr íc

lµ hÕt søc khã kh¨n. Ch¼ng h¹n, khi mét kú thñ cÇn ph¶i tÝnh to¸n c¸c n íc

®i cña m×nh ®Ó gi¶i ®¸p xem liÖu cã kh¶ n¨ng th¾ng hay kh«ng, hay chØ lµ

bøc mËt m· gi¶ cña ®èi ph ¬ng tung ra nh»m ®¶m b¶o an toµn cho bøc ®iÖn

thËt…Nh- vËy, trong tæ hîp xuÊt hiÖn mét vÊn ®Ò thø hai rÊt quan träng lµ:

xÐt sù tån t¹i cña c¸c cÊu h×nh tæ hîp víi c¸c tÝnh chÊt cho tr íc. C¸c bµi

to¸n thuéc d¹ng nµy ® îc gäi lµ c¸c bµi to¸n tån t¹i tæ hîp.

Mét bµi to¸n tån t¹i tæ hîp xem nh gi¶i xong nÕu hoÆc chØ ra mét

c¸ch x©y dùng cÊu h×nh, hoÆc chøng minh r»ng chóng kh«ng cã. Tuy nhiªn

c¶ hai kh¶ n¨ng ®Òu kh«ng ph¶i dÔ. §Ó thÊy râ sù phøc t¹p cña vÊn ®Ò, d íi

®©y ta sÏ xÐt mét sè bµi to¸n tån t¹i tæ hîp cæ ®iÓn næi tiÕng.

1.3.1.1. Bµi to¸n vÒ 36 sÜ quan

Bµi to¸n nµy ® îc Euler ®Ò nghÞ, néi dung cña nã nh sau: 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µnh 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.

§Ó ®¬n gi¶n ta dïng c¸c ch÷ c¸i in hoa A, B, C, D, E, F ®Ó chØ c¸c

phiªn hiÖu trung ®oµn cßn c¸c ch÷ c¸i th êng a, b, c, d, e, f ®Ó chØ c¸c cÊp

bËc. Bµi to¸n nµy cã thÓ tæng qu¸t ho¸ nÕu thay con sè 6 bëi n. trong tr êng

hîp n=4, mét lêi gi¶i cña bµi to¸n 16 sÜ quan lµ

Ab Dd Ba Cc

Bc Ca Ad Db

Cd Bd Dc Aa

Da Ac Cb Bd

Mét lêi gi¶i trong tr êng hîp n = 5 lµ

9

Khoa C«ng NghÖ Th«ng Tin

Tr êng Cao §¼ng C¬ §iÖn Hµ Néi

Aa Bb Cc Dd Ee

Cd De Ea Ab Bc

Eb Ac Bd Ce Da

Be Ca Db Ec Ad

De Ed Ae Ba Cb

Do lêi gi¶i cña bµi to¸n cã thÓ biÒu diÔn bëi 2 h×nh vu«ng víi c¸c ch÷

c¸i la tinh hoa vµ th êng chån c¹nh nhau nªn bµi to¸n tæng qu¸t ®Æt ra cßn

® îc biÕt d íi tªn gäi bµi to¸n vÒ h×nh vu«ng la tinh trùc giao. Trong hai thÝ

dô trªn ta cã h×nh vu«ng la tinh trùc giao cÊp 4 vµ 5.

Euler ®· mÊt rÊt nhiÒu c«ng søc ®Ó t×m lêi gi¶i cho bµi to¸n 36 sÜ quan

thÕ nh ng «ng ®· kh«ng thµnh c«ng. V× vËy «ng ®· ®Ò ra gi¶ thuyÕt lµ c¸ch

xÕp nh vËy kh«ng tån t¹i. Gi¶ thuyÕt nµy ® îc nhµ to¸n häc Ph¸p Tarri

chøng minh n¨m 1901 b»ng c¸c duyÖt tÊt c¶ mäi kh¶ n¨ng xÕp. Euler c¨n cø

vµo sù kh«ng tån t¹i lêi gi¶i khi n = 2 vµ n = 6 cßn ®Ò ra mét gi¶ thuyÕt tæng

qu¸t h¬n lµ; kh«ng tån t¹i h×nh vu«ng la tinh trùc giao cÊp n = 4k + 2. Gi¶

thuyÕt nµy ®· tån t¹i suèt hai thÕ kû m·i ®Õn n¨m 1960 ba nhµ to¸n häc Mü

lµ Boce, Parker, Srikanda míi chØ ra ® îc mét lêi gi¶i víi n = 10 vµ sau ®ã

chØ ra ph ¬ng ph¸p x©y dùng hinh vu«ng la tinh trùc giao cho mäi n = 4k +

2, víi k > 1.

T ëng chõng bµi to¸n ®Æt ra chØ cã ý nghÜa thuÇn tuý cña mét bµi to¸n

®è hãc bóa thö trÝ tuÖ con ng êi. ThÕ nh ng gÇn ®©y ng êi ta ®· ph¸t hiÖn

nh÷ng øng dông quan träng cña vÊn ®Ò trªn vµo quy ho¹ch thùc nghiÖm, s¾p

xÕp c¸c lÞch thi ®Êu trong c¸c gi¶i cê quèc tÕ, h×nh häc x¹ ¶nh,…

1.3.1.2. Bµi to¸n 4 mÇu

Cã nh÷ng bµi to¸n mµ néi dung cña nã cã thÓ gi¶i thÝch cho bÊt kú ai,

tuy nhiªn lêi gi¶i cña nã th× ai còng cã thÓ thö t×m, nh ng mµ khã cã thÓ t×m

® îc. Ngoµi ®Þnh lý Fermat th× bµi to¸n 4 mµu lµ mét bµi to¸n nh vËy. Bµi

to¸n cã thÓ ph¸t biÓu trùc quan nh sau: 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

10

Khoa C«ng NghÖ Th«ng Tin

Tr êng Cao §¼ng C¬ §iÖn Hµ Néi

vïng liªn th«ng vµ hai n íc ® îc gäi lµ l¸ng giÒng nÕu chóng cã chung biªn

giíi lµ mét ® êng liªn tôc.

3

2

1

4

Con sè 4 kh«ng ph¶i lµ ngÉu nhiªn. Ng êi ta chøng minh ® îc r»ng

mäi b¶n ®å ®Òu ® îc t« víi sè mÇu lín h¬n 4, cßn víi sè mÇu Ýt h¬n 4 th×

kh«ng t« ® îc, ch¼ng h¹n b¶n ®å gåm 4 n íc trªn h×nh 1 kh«ng thÓ t« ® îc

víi sè mÇu Ýt h¬n 4.

Bµi to¸n nµy xuÊt hiÖn vµo kho¶ng nh÷ng n¨m 1850 – 1852 tõ mét

nhµ bu«n ng êi Anh lµ Gazri khi t« b¶n ®å hµnh chÝnh n íc Anh ®· cè g¾ng

chøng minh r»ng nã cã thÓ t« b»ng 4 mÇu. Sau ®ã, n¨m 1852 «ng ta ®· viÕt

th cho De Morgan ®Ó th«ng b¸o vÒ gi¶ thuyÕt nµy. N¨m 1878, Keli trong

mét bµi b¸o ®¨ng ë TuyÓn tËp c¸c c«ng tr×nh cña Héi to¸n häc Anh cã hái

r»ng bµi to¸n nµy ®· ® îc gi¶i quyÕt hay ch a? Tõ ®ã bµi to¸n trë thµnh næi

tiÕng, vµ trong suèt h¬n mét thÕ kû qua ®· cã rÊt nhiÒu ng êi lµm to¸n,

nghiÖp d còng nh chuyªn nghiÖp, ®· cè g¾ng chøng minh gi¶ thuyÕt nµy.

Tuy nhiªn m·i ®Õn n¨m 1976 hai nhµ tãan häc Mü lµ K.Appel vµ W. Haken

míi chøng minh ® îc gi¶ thuyÕt nµy b»ng m¸y tÝnh ®iÖn tö. TÊt nhiªn mét

chøng minh víi sù gióp ®ì cña m¸y tÝnh ®iÖn tö kh«ng thùc sù tho¶ m·n

® îc nhu cÇu cña c«ng chóng muèn kiÓm tra tÝnh ®óng ®¾n cña c¸ch chøng

minh. V× vËy, chÝnh hai t¸c gi¶ trªn vµo cuèi nh÷ng n¨m 1990 ®· cã c«ng bè

mét cuèn s¸ch tr×nh bµy vÒ ph ¬ng ph¸p chøng minh cña m×nh (cuèn s¸ch

dµy trªn 800 trang). Còng vµo nh÷ng n¨m cuèi cña thÕ kû 20, mét nhãm c¸c

nhµ to¸n häc Mü ®· ® a ra mét chøng minh cã thÓ kiÓm tra b»ng tay! RÊt

tiÕc lµ chøng minh nµy còng kh«ng ph¶i lµ ®¬n gi¶n. Cho ®Õn nay c¸c nhµ

to¸n häc vÉn ®ang nç lùc nghiªn cøu ®Ó t×m ra mét c¸ch chøng minh dÔ hiÓu

nh b¶n th©n néi dung cña bµi to¸n.

11

Khoa C«ng NghÖ Th«ng Tin

Tr êng Cao §¼ng C¬ §iÖn Hµ Néi

1.3.1.3. H×nh lôc gi¸c thÇn bÝ

N¨m 1910 Clifford Adams ®Ò ra bµi to¸n h×nh lôc gi¸c thÇn bÝ sau:

trªn 19 « lôc gi¸c (xem h×nh vÏ ë d íi) h·y ®iÒn vµo c¸c sè tõ 1 ®Õn 19 sao

cho tæng theo 6 h íng cña lôc gi¸c lµ b»ng nhau (vµ ®Òu b»ng 38).

Sau 47 n¨m trêi kiªn nhÉn cuèi cïng «ng ta ®· t×m ® îc lêi gi¶i. Sau

®ã v× s¬ ý ®¸nh mÊt b¶n th¶o «ng ta ®· tèn thªm 5 n¨m ®Ó kh«i phôc l¹i.

N¨m 1962 Adams ®· c«ng bè lêi gi¶i ®ã.

ThËt kh«ng thÓ ngê lµ ®ã lµ lêi gi¶i duy nhÊt (nÕu kh«ng tÝnh ®Õn c¸c

lêi gi¶i sai kh¸c nhau bëi phÐp biÕn h×nh ®¬n gi¶n).

1.3.1.4. Bµi to¸n chän 2n ®iÓm trªn l íi n x n ®iÓm

Cho mét l íi « vu«ng gåm n x n ®iÓm. Hái cã thÓ chän trong sè

chóng 2n, ®iÓm, sao cho kh«ng cã 3 ®iÓm ® îc chän nµo lµ th¼ng hµng hay

kh«ng? HiÖn nay ng êi ta míi biÕt ® îc rÊt Ýt vÒ lêi gi¶i cña bµi to¸n trong

nh÷ng t×nh huèng kh«ng tÇm th êng. C©u hái vÒ sù tån t¹i cña lêi gi¶i cña

bµi to¸n víi nh÷ng gi¸ trÞ lín cña n vÉn cßn ®Ó ngá.

1.3.1.5. 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.

VÝ dô 1. Cho 7 ®o¹n th¼ng cã ®é dµi lín h¬n 10 vµ nhá h¬n 100.

Chøng minh r»ng lu«n t×m ® îc 3 ®o¹n ®Ó cã thÓ ghÐp thµnh mét tam gi¸c.

Gi¶i: Chó ý r»ng, cÇn vµ ®ñ ®Ó 3 ®o¹n cã thÓ ghÐp thµnh mét tam gi¸c

lµ tæng ®é dµi cña 2 ®o¹n nhá ph¶i lín h¬n ®é dµi cña ®o¹n lín, ta s¾p c¸c

®o¹n ®· cho theo thø tù t¨ng dÇn cña ®é dµi a₁, a₂,…, a₇vµ chøng minh r»ng

trong ®¸y ®· xÕp lu«n t×m ® îc 3 ®o¹n liªn tiÕp sao cho tæng cña 2 ®o¹n ®Çu

lín h¬n ®o¹n cuèi. Gi¶ thiÕt ®iÒu nµy kh«ng x¶y ra, nghÜa lµ ®ång thêi x¶y ra

c¸c bÊt ®¼ng thøc:

a₁ a₂ a₃,

a₂ a₃ a₄,

a₃ a₄ a₅,

12

Khoa C«ng NghÖ Th«ng Tin

Tr êng Cao §¼ng C¬ §iÖn Hµ Néi

a₄ a₅ a₆,

a₅ a₆ a₇,

Tõ gi¶ thiÕt a₁, a₂cã gi¸ trÞ lín h¬n 10, ta nhËn ® îc a₃> 20. Tõ a₂>

10 vµ a₃> 20, ta nhËn ® îc a₄> 30, … , cø nh- vËy ta nhËn ®-îc a₅> 50, a₆

> 80 vµ a₇> 130. BÊt ®¼ng thøc cuèi cïng m©u thuÉn víi gi¶ thiÕt c¸c ®é dµi

nhá h¬n 100 vµ ®iÒu ®ã chøng minh kÕt luËn cña bµi to¸n.

VÝ dô 2. C¸c ®Ønh cña mét thËp gi¸c ®Òu ® îc ®¸nh sè bëi c¸c sè

nguyªn 0,1, … , 9 mét c¸ch tuú ý. Chøng minh r»ng lu«n t×m ®-îc ba ®Ønh

liªn tiÕp cã tæng c¸c sè lµ lín h¬n 13.

Gi¶i: Gäi x₁, x_2,… , x₁₀lµ c¸c sè g¸n cho c¸c ®Ønh cña 1,2, … , 10 cña

thËp gi¸c. Gi¶ sö ng îc l¹i lµ kh«ng t×m ® îc ba ®Ønh nµo tho¶ m·n kh¼ng

®Þnh cña thÝ dô. Khi ®ã ta cã

k₁ x₁ x₂ x₃13

,

k₂ x₂ x₃ x₄13

,

………

k₉ x₉ x₁₀ x₁13

,

k₁₀ x₁₀ x₁ x₂13

,

Tõ ®ã suy ra

k₁ k₂... k₁₀130.

MÆt kh¸c do

k₁ k₂... k₁₀ 3(x₁ x₂... x₁₀

 3(0 1 2 ...9)

135

,

Suy ra

135  k₁ k₂... k₁₀130

.

M©u thuÉn thu ® îc ®· chøng tá kh¼ng ®Þnh trong vÝ dô lµ ®óng.

VÝ dô 3. Chøng minh r»ng kh«ng thÓ nèi 31 m¸y vi tÝnh thµnh mét

m¹ng sao cho mçi m¸y ® îc nèi víi ®óng 5 m¸y kh¸c.

13

Khoa C«ng NghÖ Th«ng Tin

Tr êng Cao §¼ng C¬ §iÖn Hµ Néi

Gi¶i: Gi¶ sö ng îc l¹i lµ t×m ® îc c¸ch nèi 31 m¸y sao cho mçi m¸y

® îc nèi víi ®óng 5 m¸y kh¸c. Khi ®ã sè l îng kªnh nèi lµ 5x31/2= 75,5 ?!

M©u thuÉn thu ® îc ®· chøng minh kh¼ng ®Þnh trong thÝ dô lµ ®óng.

1.3.2. Nguyªn lý Dirichlet

Trong rÊt nhiÒu bµi to¸n tæ hîp, ®Ó chøng minh sù tån t¹i cña mét cÊu

h×nh víi nh÷ng tÝnh chÊt cho tr íc, ng êi ta sö dông nguyªn lý ®¬n gi¶n sau,

gäi lµ nguyªn lý Dirchlet:

Nguyªn lý Direchlet. NÕu ®em xÕp nhiÒu h¬n n ®èi t îng vµo n c¸i

hép, th× lu«n t×m ® îc c¸i hép chøa kh«ng Ýt h¬n 2 ®èi t îng.

Chøng minh. ViÖc chøng minh nguyªn lý trªn chØ lµ mét lËp luËn ph¶n

chøng ®¬n gi¶n. Gi¶ sö ng îc l¹i lµ kh«ng t×m ® îc c¸i hép nµo ch÷a kh«ng

Ýt h¬n 2 ®èi t îng. §iÒu ®ã cã nghÜa lµ mçi c¸i hép chøa kh«ng qu¸ mét ®èi

t îng. Tõ ®ã suy ra tæng sè ®èi t îng xÕp trong n c¸i hép lµ kh«ng v ît qu¸

n, tr¸i víi gi¶ thiÕt lµ cã nhiÒu h¬n n ®èi t îng ® îc xÕp trong chóng.

LËp luËn hoµn toµn t ¬ng tù, cã thÓ chøng minh Nguyªn lý Dirichlet

tæng qu¸t sau.

Nguyªn lý Dirichlet tæng qu¸t. NÕu ®em xÕp n ®èi t îng vµo k c¸i hép, th×

lu«n t×m ® îc mét c¸i hép chøa kh«ng Ýt h¬n n/k ®èi t îng.

Nguyªn lý trªn ® îc nhµ to¸n häc næi tiÕng ng êi §øc lµ Dirichlet ®Ò

xuÊt tõ thÕ kû 19 vµ «ng ®· ¸p dông nã ®Ó gi¶i nhiÒu bµi to¸n tån t¹i tæ hîp.

C¸c thÝ dô d íi ®©y cho ta thÊy nguyªn lý ® îc sö dông nh thÕ nµo.

VÝ dô 1. Trong sè 367 ng êi bao giê còng t×m ® îc hai ng êi cã ngµy

sinh nhËt gièng nhau bëi v× chØ cã tÊt c¶ 366 ngµy sinh nhËt kh¸c nhau.

VÝ dô 2. Trong kú thi häc sinh giái ®iÓm bµi thi ® îc ®¸nh gi¸ bëi mét

sè nguyªn trong kho¶ng tö 0 ®Õn 100. Hái r»ng Ýt nhÊt ph¶i cã bao nhiªu häc

sinh dù thi ®Ó cho ch¾c ch¾n t×m ® îc hai hä sinh cã kÕt qu¶ thi nh nhau?

Gi¶i. Theo nguyªn lý Dirichlet, sè häc sinh cÇn t×m lµ 102, v× ta cã

101 kÕt qu¶ ®iÓm thi kh¸c nhau.

14

Khoa C«ng NghÖ Th«ng Tin

Tr êng Cao §¼ng C¬ §iÖn Hµ Néi

VÝ dô 3. Trong sè nhøng ng êi cã mÆt trªn tr¸i ®Êt lu«n t×m ® îc hai

ng êi cã hµn r¨ng gièng nhau, bëi v× chØ cã tÊt c¶

2³²= 4 294 967 296

Hµm r¨ng kh¸c nhau mµ sè ng êi trªn hµnh tinh chóng ta hiÖn nay ®·

v ît qu¸ 5 tû.

VÝ dô 4. Trong 100 ng êi cã Ýt nhÊt 9 ng êi sinh cïng mét th¸ng.

Gi¶i: XÕp nh÷ng ng êi cïng sinh mét th¸ng vµo mét nhãm. Cã 12

th¸ng tÊt c¶. VËy theo nguyªn lý Dirichlet, tån t¹i Ýt nhÊt mét nhãm cã

kh«ng Ýt h¬n 100/12 = 8,3… nghÜa lµ 9 ng-êi.

VÝ dô 5. Cã n¨m lo¹i häc bæng kh¸c nhau. Hái r»ng ph¶i cã Ýt nhÊt bao

nhiªu sinh viªn ®Ó ch¾c ch¾n r»ng cã Ýt ra lµ s¸u ng êi cïng nhËn häc bæng

nh nhau?

Gi¶i: Sè sinh viªn Ýt nhÊt cÇn cã ®Ó ®¶m b¶o ch¾c ch¾n cã 6 sinh viªn

cïng nhËn häc bæng nh nhau lµ sè nguyªn nhá nhÊt n sao cho n/5 > 5. Sè

nguyªn nhá nhÊt ®ã lµ n = 5x5+1=26. VËy 26 lµ sè l îng sinh viªn nhá nhÊt

®¶m b¶o ch¾c ch¾n lµ cã s¸u sinh viªn cïng h ëng mét lo¹i häc bæng.

NN- NNN - XX,

Trong ®ã hai ký tù ®Çu lµ m· sè ®Þa danh, ba ký tù tiÕp theo lµ sè hiÖu

xe, mçi ký tù lµ mét sè tõ 0 ®Õn 9, hai ký tù cuèi lµ m· ®¨ng ký gåm hai ch÷

c¸i lÊy trong b¶ng ch÷ c¸i la tinh gåm 26 ch÷ c¸i. Hái r»ng, ®Ó cã 2 triÖu

biÓn sè xe m¸y kh¸c nhau th× cÇn ph¶i cã Ýt nhÊt bao nhiªu m· ®Þa danh kh¸c

nhau?

Gi¶i: Víi mçi mét m· ®Þa danh ta cã 10³.26²= 676.10³biÓn sè xe

m¸y kh¸c nhau. V× vËy ®Ó cã 2 triÖu biÓn sè xe m¸y kh¸c nhau, cÇn cã Ýt

nhÊt nghÜa lµ m· ®Þa danh kh¸c nhau.

2.10⁶/(676.10³),

Trong nhiÒu øng dông thó vÞ cña nguyªn lý Dirichlet, kh¸i niÖm ®èi

t îng vµ c¸i hép cÇn ph¶i ® îc lùa chän mét c¸ch kh«n khÐo h¬n. TiÕp theo,

ta sÏ dÉn ra mét vµi thÝ dô nh vËy.

15

Khoa C«ng NghÖ Th«ng Tin

Tr êng Cao §¼ng C¬ §iÖn Hµ Néi

VÝ dô 7. Trong mét phßng häp bao giê còng t×m ® îc hai ng êi cã sè

ng êi quen trong sè nh÷ng ng êi dù häp lµ b»ng nhau.

Gi¶i: Gäi sè ng êi dù häp lµ n, khi ®ã sè ng êi quen cña mét ng êi

nµo ®ã trong phßng häp chØ cã thÓ nhËn c¸c gi¸ trÞ tõ 0 ®Õn n-1. Râ rµng

trong phßng kh«ng thÓ ®ång thêi cã ng êi cã sè ng êi quen lµ 0 (tøc lµ

kh«ng quen ai c¶) vµ cã ng êi cã sè ng êi quen lµ n-1 (tøc lµ quen tÊt c¶).

nhãm. Theo nguyªn lý Dirichlet suy ra cã Ýt nhÊt mét nhãm ph¶i cã kh«ng Ýt

h¬n hai ng êi, tøc lµ lu«n t×m ® îc Ýt ra lµ hai ng êi cã sè ng êi quen lµ

b»ng nhau.

Bµi to¸n nµy cã thÓ ph¸t biÓu d íi d¹ng ng«n ng÷ h×nh häc nh sau:

trªn mÆt ph¼ng cho n ®iÓm, gi÷a chóng cã mét sè ®iÓm ® îc nèi víi nhau

bëi c¸c ®o¹n th¼ng. Khi ®ã bao giê còng t×m ® îc hai ®iÓm cã cïng mét sè

c¹nh nèi ph¸t ra tõ chóng.

VÝ dô 8. Trong mét th¸ng gåm 30 ngµy mét ®éi bãng chuyÒn thi ®Êu

mçi ngµy Ýt nhÊt mét trËn, nh ng kh«ng ch¬i qu¸ 45 trËn. H·y chøng minh

r»ng ph¶i t×m ® îc mét gi¶i ®o¹n gåm mét sè ngµy liªn tôc nµo ®ã trong

th¸ng sao cho trong giai ®o¹n ®ã ®éi ch¬i ®óng 14 trËn.

Gi¶i: Gi¶ sö a_jlµ tæng sè trËn thi ®Êu cho ®Õn hÕt ngµy thø j cña ®éi.

Khi ®ã

a₁, a₂, …, a₃₀

Lµ d·y t¨ng c¸c sè nguyªn d ¬ng vµ ®ång thêi 1 a_J 45. Suy ra d·y

Còng lµ d·y t¨ng c¸c sè nguyªn d ¬ng vµ 15 a_J+14 59.

TÊt c¶ cã 60 sè nguyªn d ¬ng

a₁, a₂, ..., a₃₀, a₁+14, a₂+14, ..., a₃₀+ 14,

trong ®ã tÊt c¶ ®Òu nhá h¬n hoÆc b»ng 59. V× vËy theo nguyªn lý Dirichlet,

hai trong sè c¸c sè nguyªn nµy ph¶i lµ b»ng nhau. V× c¸c sè a₁, …, a₃₀lµ ®«i

16

Khoa C«ng NghÖ Th«ng Tin

Tr êng Cao §¼ng C¬ §iÖn Hµ Néi

mét kh¸c nhau vµ c¸c sè a₁+ 14, …, a₃₀+ 14 còng lµ ®«i mét kh¸c nhau, nªn

suy ra ph¶i t×m ® îc chØ sè i vµ j sao cho a_i= a_j+ 14. §iÒu ®ã cã nghÜa lµ cã

®óng 14 trËn ®Êu trong giai ®o¹n tõ ngµy j + 1 ®Õn ngµy i.

VÝ dô 9. Chøng minh r»ng, trong sè n + 1 sè nguyªn d ¬ng, mçi sè

kh«ng lín h¬n 2n, bao giê còng t×m ® îc hai sè sao cho sè nµy chia hÕt cho

sè kia.

Gi¶i: Gäi c¸c sè ®· cho lµ

a₁,a₂, …, a_n+1.

ViÕt mçi mét sè a_jtrong n + 1 sè trªn d íi d¹ng:

a_j= 2^k_jq_j, j = 1,2, …, n + 1

nguyªn lÎ mçi sè kh«ng lín h¬n 2n. Do trong ®o¹n tõ 1 ®Õn 2n chØ cã n sè

lÎ, nªn tõ nguyªn lý Dirichlet suy ra lµ hai trong sè c¸c sè q₁, q₂, …, q_n+1lµ

b»ng nhau, tøc lµ t×m ® îc hai chØ sè i vµ j sao cho q_i= q_j= q. Khi ®ã a_i=

2^kjq. Suy ra nÕu k_i< k_jth× a_jchia hÕt cho a_i, cßn nÕu k_i



k_jth× a_ichia hÕt cho

a_j.

VÝ dô 10. Trong mÆt ph¼ng cho 6 ®iÓm ® îc nèi víi nhau tõng ®«i mét

bëi c¸c cung mµu xanh hoÆc mµu ®á. Chøng minh r»ng lu«n t×m ® îc 3

®iÓm sao cho c¸c cung nèi chóng cã cïng mét mµu (ta sÏ nãi lµ chóng t¹o

thµnh tam gi¸c xanh hoÆc ®á).

Gi¶i: Chän ®iÓm P nµo ®ã. Tõ nã cã 5 cung nèi víi 5 ®iÓm cßn l¹i.

Theo nguyªn lý Dirichlet, cã 3 trong sè 5 cung ®ã ph¶i cã cïng mét mµu,

ch¼ng h¹n lµ mµu xanh. Gi¶ sö ®ã lµ c¸c cung PA, PB, PC. NÕu nh mét

trong sè 3 cung AB, AC, BC cã mµu xanh th× nã cïng víi hai trong sè ba

cung PA, PB, PC t¹o thµnh mét tam gi¸c xanh. NÕu ng îc l¹i th× tam gi¸c

ABC lµ mét tam gi¸c ®á.

VÝ dô 11. Trªn mÆt ph¼ng cho 9 ®iÓm ® îc nèi víi nhau ®«i mét bëi

c¸c ®o¹n nèi cã mÇu xanh hoÆc ®á sao cho trong sè 3 ®iÓm bÊt kú bao giê

còng t×m ® îc hai ®iÓm ® îc nèi víi nhau bëi ®o¹n nèi mµu ®á. Chøng minh

17

Khoa C«ng NghÖ Th«ng Tin

Tr êng Cao §¼ng C¬ §iÖn Hµ Néi

r»ng trong sè c¸c ®iÓm ®· cho lu«n t×m ® îc 4 ®iÓm mµ c¸c ®o¹n th¼ng nèi

chóng ®Òu cã mµu ®á.

Gi¶i: Gäi 9 ®iÓm ®· cho lµ A, B, C, D, E, F, G, H, I. XÐt 2 tr êng hîp:

a) T×m ® îc mét ®iÓm lµ ®Çu mót cña Ýt nhÊt 4 ®o¹n nèi mµu xanh

ch¼ng h¹n ®iÓm ®ã lµ A vµ c¸c ®o¹n mµu xanh ®ã lµ AB, AC, AD, AE. Theo

gi¶ thiÕt, trong sè c¸c ®o¹n nèi bÊt kú 3 ®iÓm nµo còng cã Ýt nhÊt mét ®o¹n

mµu ®á, suy ra c¸c ®o¹n BC, Be, BD, CD, CE, ED lµ mµu ®á. VËy B, C, D, E

lµ bèn ®iÓm cÇn t×m.

b) Mçi ®iÓm ®Òu lµ ®Çu mót cña nhiÒu nhÊt lµ 3 ®o¹n nèi mµu xanh.

Trong tr êng hîp nµy, kh«ng thÓ tÊt c¶ 9 ®iÓm ®Òu lµ ®Çu mót cña ®óng 3

®o¹n nèi mµu xanh (chøng minh t ¬ng tù nh trong thÝ dô 3, môc 3.2), tõ ®ã

suy ra ph¶i t×m ® îc ®iÓm (I ch¼ng h¹n) lµ ®Çu mót cña nhiÒu nhÊt lµ 2 ®o¹n

nèi mµu xanh. Khi ®ã I lµ ®Çu mót cña Ýt nhÊt 6 ®o¹n mµu ®á, ch¼ng h¹n IA,

IB, IC, ID, IE, IF. Theo kÕt qu¶ cña thÝ dô 10, trong sè 6 ®iÓm A, B, C, D, E,

F ph¶i cã Ýt nhÊt 3 ®iÓm, ch¼ng h¹n A, B, C, sao cho c¸c ®o¹n nèi chóng cã

cïng mµu, vµ tõ gi¶ thiÕt suy ra mµu ®ã ph¶i lµ mµu ®á. VËy I, A, B, C lµ

bèn ®iÓm cÇn t×m.

Trong nhiÒu t×nh huèng, sù tån t¹i cña cÊu h×nh tæ hîp phô thuéc vµo

mét sè ®iÒu kiÖn rµng buéc c¸c tham sè ban ®Çu. Mét trong nh÷ng h íng

gi¶i quyÕt lµ ng êi ta cè g¾ng ph¸t hiÖn ra c¸c ®iÒu kiÖn ®ã. Bµi to¸n hÖ ®¹i

Gi¶ sö S₁, S₂,…, S_mlµ mét hä c¸c tËp con cña mét tËp hîp S (c¸c S_i

kh«ng nhÊt thiÕt kh¸c nhau). Ta gäi mét bé cã thø tù a₁, a₂, …, a_mlµ mét hÖ



biÖt ® îc viÕt t¾t lµ TRAN (transversal) vµ thµnh phÇn a_icña hÖ ® îc gäi lµ

®¹i diÖn cña tËp con S₁(i = 1, … , m).

VÝ dô 12. S =



1,2,3,4,5



,S₁



2,5



,S₂



2,5



,S₃



1,2,3,4



,S₄



1,2,5

cã



TRAN lµ (2,5,3,1). Mét TRAN kh¸c cña hä nµy lµ (5,2,4,1).

18

Khoa C«ng NghÖ Th«ng Tin

Tr êng Cao §¼ng C¬ §iÖn Hµ Néi

Kh«ng ph¶i lóc nµo còng t×m ® îc TRAN. Mét ®iÒu dÔ nhËn thÊy lµ

nÕu hä ®ang xÐt cã TRAN, th× mäi hîp cña k tËp bÊt kú trong hä ph¶i cã Ýt

nhÊt k phÇn tö (v× lu«n t×m ® îc k ®¹i diÖn kh¸c nhau cña k tËp ®ã). Nãi kh¸c

®i, nÕu t×m ® îc k tËp nµo ®ã cña hä, mµ hîp cña chóng cã Ýt h¬n k phÇn tö,

th× ch¾c ch¾n hä ®ang xÐt sÏ kh«ng cã TRAN. Ch¼ng h¹n trong thÝ dô trªn,

nÕu thay tËp S₄cña hä ®ang xÐt bëi tËp



2,5

, th× hä nµy sÏ kh«ng tån t¹i



TRAN, v× cã Ýt h¬n 3 phÇn tö.

S₁ S₂ S₄

2,5

 

P. Hall ®· chøng minh ® îc ®iÒu kiÖn cÇn võa nªu, còng ®ång thêi lµ

®ñ cho sù tån t¹i TRAN, qua ®Þnh lý ®¸nh gi¸ cËn d íi cña sè TRAN d íi

®©y:

§Þnh lý Hall. Gi¶ sö c¸c tËp con S₁, S₂, …, S_mtho¶ m·n ®iÒu kiÖn:

N(S_i S_i... S_i)  k

(1)

1

2

1

Víi mäi 1 k  m,1 i₁ i_k mvµ mçi tËp con nµy chøa Ýt nhÊt t phÇn

tö.

Khi ®ã:

. nÕu t m th× hä ®ang xÐt cã Ýt nhÊt t! TRAN

. nÕu t m th× hä ®ang xÐt cã Ýt nhÊt t!/(t-m) ! TRAN.

§iÒu kiÖn (1) ® îc gäi lµ ®iÒu kiÖn Hall vµ ta gäi mét hä con cña hä

S₁, S₂, …, S_mlµ tíi h¹n nÕu ®èi víi nã bÊt ®¼ng thøc (1) trë thµnh ®¼ng thøc.

Chøng minh. Quy n¹p theo m, víi m = 1, ta cã t = t !/(t-1) ! TRAN, ®Þnh lý

®óng. Gi¶ sö ®Þnh lý ®óng cho mäi hä tËp con cña S cã Ýt h¬n m tËp, ta cÇn

chøng minh ®Þnh lý ®óng cho hä tËp con gåm m tËp. Chia lµm 2 tr êng hîp :

. Kh«ng cã hä con tíi h¹n. Chän a₁lµ mét phÇn tö cña S₁. Lo¹i nã ra

khái S₁, S₂, …, S_m(bÕu cã mÆt) vµ gäi hä nhËn ® îc lµ S₂’,S₃’, …, S_m’ . DÔ

dµng thö l¹i hä nµy tho¶ m·n ®iÒu kiÖn Hall vµ mçi tËp thuéc hä cã Ýt nhÊt t-

1 phÇn tö. Theo gi¶ thiÕt quy n¹p hä nµy cã Ýt nhÊt (t-1)! TRAN khi t-1

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 S₂’,S₃’, …, S_m’ cïng víi a₁. x¸c ®Þnh mét TRAN cña S₁, S₂,



m-



19

Khoa C«ng NghÖ Th«ng Tin

Tr êng Cao §¼ng C¬ §iÖn Hµ Néi

…, S_m(a₁®¹i diÖn cho S₁). §iÒu nµy ®óng cho mçi c¸ch chän a₁trong sè Ýt

nhÊt t c¸ch chän nã tõ S₁. Tõ ®ã nhËn ® îc ®¸nh gi¸ cÇn chøng minh.

. Cã mét hä con tíi h¹n. Kh«ng mÊt tÝnh tæng qu¸, cã thÓ gi¶ thiÕt hä

®ã lµ S₁, S₂, …, S_k(k < m). Tõ sù tån t¹i cña hä con tíi h¹n suy ra t



k, v×

vËy theo gi¶ thiÕt quy n¹p, hä S₁, S₂, …, S_kcã Ýt nhÊt t! TRAN. Gäi T’ =

(a₁,a₂, …, a_k) lµ mét TRAN nh thÕ. Bá c¸c phÇn tö cña T’, nÕu cã mÆt, ra

khái c¸c tËp S_k+1, …, s_mvµ gäi c¸c tËp thu ® îc lµ S’_k+1,…, S’_m. Khi ®ã hä

S’_k+1,…, S’_msÏ tho¶ m·n ®iÒu kiªn Hall. ThËt vËy, nÕu cã mét hä con gåm k’

k’ tËp cña hä S₁, S₂, …, S_m, nhËn ® îc b»ng c¸ch ghÐp hä con nµy víi hä S₁,

thiÕt cña ®Þnh lý. Nh vËy hä S’_k+1, …, S’_mcã Ýt nhÊt mét TRAN. LÊy Ýt nhÊt

t! TRAN cña hä S₁, S₂, …, S_kghÐp víi TRAN nµy, ta ® îc Ýt nhÊt t! TRAN

cña hä S₁, S₂, …, S_m. §Þnh lý ® îc chøng minh.

x©y dùng TRAN.

Bµi to¸n ng êi thi hµnh. 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 S_ilµ tËp hîp c¸c c«ng viÖc mµ ng êi ®ã

Lêi gi¶i cña bµi to¸n ® îc dÉn vÒ viÖc xÐt sù tån t¹i TRAN cña hä

Si

 

Bµi to¸n chuyÓn m¹ch. XÐt mét hÖ thèng chuyÓn m¹ch ®¬n gi¶n

gåm 2 nhãm c¸c cùc: ®Çu vµo vµ ®Çu ra. T¹i ®Çu vµo sÏ xuÊt hiÖn ®ßi hái vÒ

nèi m¹ch. §ßi hái nµy cã thÓ ® îc tho¶ m·n b»ng c¸ch nèi nã víi mét ®Çu

ra nµo ®ã. TËp hîp c¸c ®Çu vµo cã ®ßi hái nèi m¹ch ® îc gäi lµ danh môc

®ßi hái. §Çu vµo nèi víi ®Çu ra qua mét m¹ch nèi vµ m¹ch nèi nµy cÇn ph¶i

kh«ng ® îc bËn nghÜa lµ nã ch a phôc vô cho ®Çu vµo nµo. C¸c m¹ch nèi

nh vËy gäi lµ danh môc tù do. Kh«ng gi¶m tæng qu¸t, ta cã thÓ coi r»ng

20

Khoa C«ng NghÖ Th«ng Tin