Một số bài toán tổ hợp đếm
- 70 trang
ĐẠIHỌCQUỐCGIAHÀNỘI
TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN
------------------
PHẠM THỊ HIÊN
MỘT SỐ BÀI TOÁN TỔ HỢP ĐẾM
LUẬNVĂNTHẠCSĨKHOAHỌC
HàNộiNăm2014
ĐẠIHỌCQUỐCGIAHÀNỘI
TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN
------------------
PHẠM THỊ HIÊN
MỘT SỐ BÀI TOÁN TỔ HỢP ĐẾM
Chuyênngành:Phươngpháptoánsơcấp
Mãsố:60460113
LUẬNVĂNTHẠCSĨKHOAHỌC
NGƯỜIHƯỚNGDẪNKHOAHỌC:
PGS.TS.LêAnhVinh
HàNộiNăm2014
MỤC LỤC
MỞ ĐẦU ........................................................................................ 1
CHƯƠNG 1 - CƠ SỞ LÍ THUYẾT VỀ TỔ HỢP .................... 2
1.1Nhắclạivềtậphợp...........................................................................2
1.2Quytắccộngvàquytắcnhân ........................................................3
1.3Giaithừavàhoánvị..........................................................................5
1.4Chỉnhhợp,tổhợp............................................................................5
1.5Chỉnhhợplặp,hoánvịlặpvàtổhợplặp..........................................6
1.5.1Chỉnhhợplặp...........................................................................6
1.5.2Hoánvịlặp................................................................................7
1.5.3Tổhợplặp.................................................................................8
CHƯƠNG 2 - MỘT SỐ BÀI TOÁN TỔ HỢP CƠ BẢN ........ 9
2.1Mộtsốbàitoánđếmkhônglặp.........................................................9
2.1.1Bàitoánlậpsố..........................................................................9
2.1.2Bàitoánchọnvật,chọnngười,sắpxếp...................................17
2.1.3Bàitoántươngtự.....................................................................26
2.2Mộtsốbàitoánđếmcólặp...........................................................29
2.2.1Bàitoánlậpsố.........................................................................29
2.2.2Bàitoánđếmsửdụngtổhợplặp..............................................33
2.2.3Bàitoánđếmsửdụngchỉnhhợplặp........................................37
2.2.4Bàitoánđếmsửdụnghoánvịlặp............................................37
2.2.5Bàitoánphânbốcácđồvậtvàotronghộp...............................39
2.2.6Bàitoántươngtự.....................................................................40
CHƯƠNG 3 - MỘT SỐ BÀI TOÁN TỔ HỢP SỬ DỤNG
PHÉP ĐẾM NÂNG CAO .......................................................... 42
3.1Mộtsốbàitoánsửdụngnguyênlýbùtrừ......................................42
3.1.1Nguyênlýbùtrừ.....................................................................42
3.1.2Cácbàitoángiảibằngphươngphápbùtrừ.............................43
3.2Mộtsốbàitoángiảibằngphươngphápsongánh..........................49
3.2.1Phươngphápsongánh............................................................49
3.2.2Cácbàitoántổhợpgiảibằngphươngphápsongánh.............50
3.3Mộtsốbàitoángiảibằngphươngpháphàmsinh..........................52
3.3.1Bàitoánchọncácphầntửriêngbiệt........................................52
3.3.2Bàitoánchọncácphầntửcólặp..............................................53
3.4Mộtsốbàitoángiảibằngphươngpháphệthứctruyhồi................57
3.4.1Kháiniệmmởđầuvàmôhìnhhóabằnghệthứctruyhồi........57
3.4.2Cácbàitoántổhợpgiảibằnghệthứctruyhồi.........................57
3.4.3Cácbàitoántươngtự...............................................................60
3.5Bàitoángiảibằngnguyênlícựchạn-khảnăngxảyranhiềunhất,ít
nhất......................................................................................................60
3.6Bàitoángiảibằngphươngphápsắpxếpthứtự.............................61
3.7Bàitoángiảibằngphươngphápliệtkêcáctrườnghợp.................62
KẾT LUẬN ................................................................................. 65
TÀI LIỆU THAM KHẢO ......................................................... 66
MỞ ĐẦU
Toánhọctổhợplàmộttrongnhữnglĩnhvựcđượcnghiêncứutừkhá
sớm. Hiện nay trong giáo dục phổ thông, toán học tổ hợp là một trong
nhữngnộidungquantrọng,nóthườngxuyênxuấthiệntrongcácđềthiđại
họcvàcaođẳngởnướcta.Mặcdùởmứcđộkhôngkhónhưnghọcsinh
vẫn gặp khó khăn khi giải quyết các bài toán này. Còn trong các kỳ thi
QuốcgiavàQuốctế,cácbàitoántổhợpluôncómặtvàlàmộtthửthách
thực sự với các thí sinh, thậm chí quyết định thành tích đối với các đội
tuyểndựthi.
Trongluậnvănnàyđãđềcậpđếnmộtsốbàitoántổhợptrongtoán
họcphổthông,cụthểlàcácbàitoántổhợpsửdụngcácphươngphápđếm
từcơbảnđếnnângcao.Đâycóthểcoilàtàiliệuthamkhảohữuíchcho
giáoviênvàhọcsinhTHPTvềchủđềnày.
Luậnvăngồmbachương:
Chương1-Cơsởlýthuyếtvềtổhợp.
Chương2-Mộtsốbàitoántổhợpcơbản.
Chương3-Mộtsốbàitoántổhợpsửdụngphépđếmnângcao.
Dosựhạnchếvềtrìnhđộkiếnthứcvàthờigiannêncácbàitoántổ
hợptrongluậnvăncònít,chưacónhiềubàitoánkhó.Ngoàirakhoáluận
cũng không thể tránh khỏi những sai sót ở nhiều góc độ, rất mong nhận
đượcsựđónggópýkiếncủaquýthầycôvàcácbạn.
1
CHƯƠNG 1 - CƠ SỞ LÍ THUYẾT VỀ TỔ HỢP
Chươngnàysẽnhắclạimộtsốlýthuyếtvềtậphợpvàhệthốnglý
thuyết cơ bản của toán tổ hợp như: Hoán vị, chỉnh hợp, tổ hợp. Các nội
dungnàycũngđượcgiảngdạychohọcsinhtrunghọcphổthônghệcơbản,
nângcaovàhệchuyênnghànhtoán.
1.1 Nhắc lại về tập hợp
Tập hợp con
Định nghĩa:Chotậphợp A .Tậphợp B gọilàtậpconcủatập A khi
mọiphầntửcủatập B đềuthuộc A .
B A x B x A
Tính chất:
-Mọitậphợp A đềucó2tậpconlà và A .
-Tập A có n phầntửthìsốtậpconcủa A là 2 n .
Tập hợp sắp thứ tự
Mộttậphợphữuhạncó m phầntửđượcgọilàsắpthứtựnếuvớimỗi
phầntửcủatậphợpđótachotươngứngmộtsốtựnhiêntừ1đến m ,sao
chovớinhữngphầntửkhácnhauứngvớinhữngsốkhácnhau.
Khiđóbộsắpthứtự m phầntửlàmộtdãyhữuhạn m phầntửvàhai
bộ sắp thứ tự a1 , a2 ,..., am và b1 , b2 ,..., bm bằng nhau khi mọi phần tử
tươngứngbằngnhau.
a , a ,..., a = b , b ,..., b ai = bi i 1,2,.., m.
1
2
m
1
2
m
Số phần tử của một số tập hợp
Tậphợp A cóhữuhạnphầntửthìsốphầntửcủa A đượckíhiệulà:
A hoặc n A .
A, B, C là3tậphợphữuhạn,khiđó
2
A B A B A B
A B C A B C A B B C C A A B C
Tổng quát:Cho A1 , A2 ,..., An là n tậphợphữuhạn [ n 1] .
Khiđó
n
A1
An =
n
+
n
Ai
i 1
Ai Ak
1i k n
n 1
Ai Ak Al ++ [1] A1 A2 ... An .
1i k l n
1.2 Quy tắc cộng và quy tắc nhân
Quy tắc cộng
Định nghĩa [Tài liệu chuẩn kiến thức 12].
Một công việc được hoàn thành bởi một trong hai hành động. Nếu hành
độngnàycó m cáchthựchiện,hànhđộng kiacó n cáchthựchiệnkhông
trùngvớibấtkìcáchnàocủahànhđộngthứnhấtthìcôngviệcđócóm+n
cáchthựchiện.
Tổng quát
Một công việc được hoàn thành bởi một trong các hành động
T1 , T2 ,..., Tn .
T1cóm1cáchthựchiện.
T2cóm2cáchthựchiện
...
Tncómncáchthựchiện.
Giảsửkhôngcóhaiviệcnàocóthểlàmđồngthờithìcôngviệcđó
có m1 m2 ... mn cáchthựchiện.
Biểu diễn dưới dạng tập hợp:
Nếu X , Y làhaitậphợphữuhạn,khônggiaonhauthì
3
X Y X Y
Nếu X1, X 2 ,..., X n là n tậphữuhạn,từngđôimộtkhônggiaonhau
thì
X1 X 2 ... X n X1 X 2 ... X n
Nếu X , Y làhaitậphữuhạnvà X Y thì
X Y\X Y X
Quy tắc nhân [Tài liệu chuẩn kiến thức 12].
Giảsửđểhoànthành mộtnhiệmvụHcầnthựchiênhaicôngviệc
nhỏlàH1vàH2.Trongđó:
H1 cóthểlàmbằng n1 cách.
H 2 cóthểlàmbằng n2 cách,saukhiđãhoànthànhcôngviệc H1 .
Khiđóđểthựchiệncôngviệc H sẽcó n1.n2 cách.
Tổng quát
Giả sử để hoàn thành một nhiệm vụ H cần thực hiện k công việc
nhỏlà H1 , H 2 ,, H k trongđó:
H1 cóthểlàmbằng n1 cách.
H 2 cóthểlàmbằng n2 cách,saukhiđãhoànthànhcôngviệc H1 .
H k cóthểlàmbằng nk cách,saukhiđãhoànthànhcôngviệc H k 1 .
Khiđóđểthựchiệncôngviệc H sẽcó n1.n2 ...nk cách.
Biểu diễn dưới dạng tập hợp:
Nếu A1, A2 ,..., An là n tậphợphữuhạn n 1 ,khiđósốphầntửcủatích
đềcáccáctậphợpnàybằngtíchcủasốcácphầntửmọitậpthànhphần.
Đểliênhệvớiquytắcnhânhãynhớlàviệcchọnmộtphầntửcủatíchđề
các A1 A2 ... An được tiến hành bằng cách chọn lần lượt một phần tử
4
của A1 ,mộtphầntửcủa A2 ,,mộtphầntửcủa An .Theoquytắcnhânta
nhậnđượcđẳngthức: A1 A2 ... An A1 . A2 ... An .
1.3 Giai thừa và hoán vị
Giai thừa
Định nghĩa: Giaithừa n ,kíhiệulà n !làtíchcủa n sốtựnhiênliên
tiếptừ1đến n .
n! 1.2.3. n 1 . n , n ¥ , n >1.
Quyước:0!=1.
1!=1.
Hoán vị
Định nghĩa
Cho tập hợp A , gồm n phần tử [ n 1] . Một cách sắp thứ tự n
phầntửcủatậphợp A đượcgọilàmộthoánvịcủa n phầntửđó.
Kíhiệu: Pn làsốcáchoánvịcủanphầntử.
Pn n ! 1.2 n 1 .n
1.4 Chỉnh hợp, tổ hợp
Chỉnh hợp
Định nghĩa
Chotậphợp A gồm n phầntử [ n 1] .Kếtquảcủaviệclấy k phần
tửkhácnhautừ n phầntửcủatậphợp A vàsắpxếpchúngtheomộtthứtự
nàođóđượcgọilàmộtchỉnhhợpchập k của n phầntửđãcho.
Kíhiệu: Ank làsốcácchỉnhhợpchập k của n phầntử.
Côngthức: Ank =
n!
= n. n 1 n k 1[với1 k n ].
[n k ]!
Chú ý
5
Mộtchỉnhhợp n chập n đượcgọilàmộthoánvịcủa n phầntử.
Ann Pn n! .
Tổ hợp
Định nghĩa
Giảsửtập A có n phầntử[ n 1].Mỗitậpcongồm k phầntửcủa
A đượcgọilàmộttổhợpchập k của n phầntửđãcho[1 k n ].
Kíhiệu: C kn [1 k n ]làsốcáctổhợpchập k của n phầntử.
Côngthức: C kn =
n!
.
k ![n k ]!
Chú ý
C 0n =1.
C kn C nnk [0 k n].
C kn + C kn 1 = C kn11 [1 k n ].
1.5 Chỉnh hợp lặp, hoán vị lặp và tổ hợp lặp
1.5.1 Chỉnh hợp lặp
Định nghĩa [Phương pháp giải toán tổ hợp]
Một cách sắp xếp có thứ tự r phần tử có thể lặp lại của một tập n
phầntửđượcgọilàmộtchỉnhhợplặpchậprtừtậpnphầntử.NếuAlàtập
gồm n phần tử đó thì mỗi chỉnh hợp như thế là một phần tử của tập Ar.
Ngoài ra, mỗi chỉnh hợp lặp chập r từ tập nphần tử là một hàm từ tậpr
phầntửvàotậpnphầntử.Vìvậysốchỉnhhợplặpchậprtừtậpnphầntử
lànk.
Định lý 1.5.1 Số các chỉnh hợp lặp chập r từ tập n phần tử bằng n r
Chứng minh
6
Rõràngcóncáchchọn mộtphầntửtừtậpnphầntửcho mỗi một
trongrvịtrícủachỉnhhợpkhichophéplặp.Vìvậytheoquytắcnhân,có
n r chỉnhhợplặpchậprtừtậpnphầntử.
Chú ý.
Sốcácchỉnhhợplặpchập p của n phầntửlà n p .
Nhưvậychỉnhhợpcólặplạilàkhigiữacácphầntửyếutốthứtựlà
cốtlõi,cònyếutốkhácbiệtkhôngquantrọng.
1.5.2 Hoán vị lặp
Trongbàitoánđếm,mộtsốphầntửcóthểgiốngnhau.Khiđócần
phảicẩnthận,tránhđếmchúnghơnmộtlần.
Định lý 1.5.2 Số hoán vị của n phần tử trong đó có n1 phần tử như nhau
thuộc loại 1, có n2 phần tử như nhau thuộc loại 2, và có nk phần tử
như nhau thuộc loại k bằng
n!
.
n1 ! n2 !...nk !
Chứng minh
Đểxácđịnhsốhoánvịtrướctiênchúngtanhậnthấycó Cnn cáchgiữ
1
n1sốchon1phầntửloại1,cònlạinn1chỗtrống.
Sauđócó Cnn n cáchđặtn2phầntửloại2vàohoánvị,cònlạinn1 n2
2
1
chỗtrống.
Tiếptụcđặtcácphầntửloại3,loại4,,loạik1vàochỗtrốngtrong
hoánvị.Cuốicùngcó Cnn n n ...n cáchđặtnkphầntửloạikvàohoánvị.
k
1
2
k 1
Theoquytắcnhântấtcảcáchoánvịcóthểlà:
Cnn1 .Cnn2 n1 ...Cnnk n1 ... nk 1
7
n!
n1 ! n2 !...nk !
1.5.3 Tổ hợp lặp
Mộttổhợplặpchậpkcủamộttậphợplàmộtcáchchọnkhôngcó
thứtựkphầntửcóthểlặplạicủatậpđãcho.Nhưvậymộttổhợplặpkiểu
nàylàmộtdãykhôngkểthứtựgồmkthànhphầnlấytừtậpnphầntử.Do
đócóthểlàk>n.
Định lý 1.5.3 Số tổ hợp lặp chập k từ tập n phần tử bằng C nk k 1 .
Chứng minh
Mỗitổhợplặpchậpktừtậpnphầntửcóthểbiểudiễnbằng một
dãyn1thanhđứngvàkngôisao.Tadùngn1thanhđứngđểphâncách
cácngăn.Ngănthứichứathêmmộtngôisaomỗilầnkhiphầntửthứicủa
tậpxuấthiệntrongtổhợp.
Mỗidãyn1thanhvàkngôisaoứngvớimộttổhợplặpchậpkcủa
nphầntử.Dođómỗidãyứngvớimộtcáchchọnkchỗchokngôisaotừ
n k 1 chỗchứan1thanhvàkngôisao.Đólàđiềucầnchứngminh.
Chú ý.
Sốtổhợpcólặpchập p của n là C np = C np p 1 = C nn1p 1 .
Tổhợpcólặplạikhimộtphầntửcóthểxuấthiệnnhiềulầnvàthứtự
củacácphầntửkhôngcầnđểý.
8
CHƯƠNG 2 - MỘT SỐ BÀI TOÁN TỔ HỢP CƠ BẢN
Chương1đãtrìnhbàylýthuyếtcơbảncủatoántổhợp.Dựatrêncơ
sởlýthuyếtđótrongchươngnàykhóaluậnsẽtậptrungtrìnhbàymộtsố
bàitoántổhợpcơbản,phùhợpvớihọcsinhTHPTkhithamgiacáckìthi
tốtnghiệp,caođẳng,đạihọc.
2.1 Một số bài toán đếm không lặp
Trongcácbàitoánvềphépđếmkhônglặp,mỗiphầntửcầnđếmchỉ
cóthểxuấthiệntốiđamộtlần.Đểgiảicácbàitoánđếmkhônglặpngười
tasửdụnghaiquytắcchínhcủaphépđếmlàquytắccộngvàquytắcnhân,
cũngnhưsửdụnghaiphươngphápđếmtrựctiếphoặcđếmgiántiếp.
2.1.1 Bài toán lập số
Bài 1:
Cho tập hợp các chữ số X 1, 2,,9 . Từ tập hợp X có thể lập
được bao nhiêu số chẵn có 6 chữ số khác nhau từng đôi một.
Giải:
Gọisốcầnlậplà n = a1a2a3a4a5a6 , ai X .
Vì n làsốchẵnnên a6 2;4;6;8 có4cáchchọn.Còn a1 , a2 , a3 , a4 , a5
làmộtbộphânbiệtcóthứtựđượcchọntừXdođónólàmộtchỉnhhợp
chập5của8[Trừđisốa6đãchọn].Có A85 cáchchọn.
Vậycó 4. A85 224 sốthỏamãnbàitoán.
Bài 2:
Cho tập hợp các chữ số X 0, 1, 2,,7 . Từ tập hợp X có thể lập
được bao nhiêu số tự nhiên có năm chữ số khác nhau từng đôi một thỏa
mãn :
a. Là số chẵn.
9
b. Là số tiến [chữ số sau lớn hơn chữ số đứng trước nó].
Giải:
Gọisốcầnlậplà n = a1a2 a3a4 a5 , ai X , a1 0 .
Vì n làsốchẵnnên a5 0, 2, 4, 6 .
Trườnghợp1:Nếu a5 0 thì a5 có1cáchchọn.
Khiđó a1 , a2 , a3 , a4 làmộtbộphânbiệtcóthứtựđượcchọntừX\{0}
dođónólàmộtchỉnhhợpchập4của7.Có A74 cáchchọn.
Vậycó A74 =840sốthỏamãnbàitoán.
Trườnghợp2:Nếu a5 đượcchọntừ{2,4,6}thì a5 có3cáchchọn.
a1 đượcchọntừtậpX\{0, a5 }nên a1 có6cáchchọn.
a2 , a3 , a4 làmộtbộphânbiệtthứtựđượcchọntừX\{ a1 , a5 }dođó
nólàmộtchỉnhhợp6chập3.Có A63 cáchchọn.
Vậycó3.6. A63 =2160sốthỏamãnbàitoán.
Vậysốcácsốchẵngồm5chữsốphânbiệthìnhthànhtừ X là:
840+2160=3000số.
b]Vì n làsốtiếnnên a1 a2 ... a5 vàdo a1 0
nên1 a1 a2 ... a5 .
Mỗicáchchọnra5chữsốthìchỉcó1cáchsắpxếptừnhỏđếnlớn.
Vậysốcácsốcầntìmlàsốcáchchọnra5chữsốtừtập X \ {0} .
Vậycó C75 =21sốthỏamãnđiềukiện.
Bài 3:
Cho A 0, 1, , 5 , có bao nhiêu số có 6 chữ số khác nhau và
chữ số 2 đứng cạnh chữ số 3.
Giải:
10
Ta dán hai chữsố2và3thành một chữsốkép.Cóhai cáchdán23
hoặc32.Bàitoántrởthành:TừnămchữsốthuộcB={ 0;1; 4;5; sốkép}có
thểlậpđượcbaonhiêusốtựnhiêncónămchữsốkhácnhau
GọisốcónămchữsốđượclậptừBlà n = a1a2 a3a4 a5 , ai B , a1 0 .
a1 đượcchọntừtập B \ 0 nên a1 có4cáchchọn.
a2 , a3 , a4 , a5 là mộtbộphânbiệtthứtựđượcchọntừ X \{a1} dođó
nólàmộthoánvịcủa4.Có4!cáchchọn.
Vậycó2.4.4!=192sốthỏamãnbàitoán.
Bài 4:
Từ tập A 0, 1, , 5 có thể lập được bao nhiêu số có 6 chữ số
sao cho mỗi chữ số xuất hiện nhiều nhất một lần. Tính tổng tất cả các số
đó.
Giải:
Xéttrườnghợpcácsốlậpđượctừ A có6chữsố[cảtrườnghợpsố0
đứngđầu].
Có P6 6! 720 số.
Ta thấy các số trong tập A đều xuất hiện 120 lần trên các hàng trăm
nghìn,hàngchụcnghìn,hàngnghìn,hàngtrămhàngchụcvàhàngđơnvị.
Vậytổngtấtcảcácsốlậpđượctrongtrườnghợpnàylà:
T 120 0 1 2 3 4 5 105 120 0 1 2 3 4 5 104
106 1
120 0 1 2 3 4 5 120.15.
10 1
Xéttrườnghợpsố0đứngđầu 0a2 a3a4 a5 a6 , ai A \ {0}, i 2,6 .
Có P5 =5!=120số.
Tathấycácsố1,2,3,4,5đềuxuấthiện24lầntrêncáchàngchụcnghìn,
hàngnghìn,hàngtrămhàngchụcvàhàngđơnvị.
11
Vậytổngcácsốlậpđượctrongtrườnghợpnàylà:
K 24.15
105 1
.
10 1
Tổngcácsốlậpđượccó6chữsốlà: P6 P5 600 số.
Tổngtấtcảcácsốđólà:
S T K 120.15
106 1
105 1
24.15
195999840 .
10 1
10 1
Bài 5:
Có bao nhiêu số tự nhiên có 7 chữ số khác mhau và lớn hơn
685000 lập từ A 0, 1, , 9 .
Giải:
Gọisốcầntìmlà:
n a1a2 ...a7 , n 685000, ai A, a1 0, i 1,7 .
Trườnghợp1:Sốcódạng 68a3a4 ...a7 [ a3 5, a3 6,8 ].
a3 cóthểnhận3giátrị5,7,9nêncó3cáchchọn.
a4 , a5 , a6 , a7 làmộtbộ4sốcóthứtựlậptừ A \ {6,8,a 3} .
Có A74 cáchchọnbộ4sốcókểthứtự.
Vậycó3. A74 sốthỏamãnbàitoán.
Trườnghợp2:Sốcódạng 69a3a4 ...a7 .
a3 , a4 , a5 , a6 , a7 làmộtbộ5phầntửtừ A \ {6, 9} vàcókểthứtựcác
phầntử.
Có A85 số.
Trườnghợp3:sốcódạng a1a2 ...a7 với a1 6 .
a1 có3cáchchọnlà7,8,9.
12
a2, a3 , a4 , a5 , a6 , a7 làmộtbộ6phầntửtừ A \ {a1} vàcókểthứtựcác
phầntử.
Có A96 số.
Vậycó 3.A74 A85 3. A74 A85 A96 69720 sốthỏamãnbàitoán.
Bài 6:
Có bao nhiêu số tự nhiên có 6 chữ số khác nhau trong đó mỗi số
có tổng của ba chữ số đầu nhỏ hơn tổng của ba chữ số cuối một đơn vị.
Giải:
Gọisốcầntìmlà:
n a1a2 ...a6 , a1 0 .
Tacó 1 2 3 4 5 6 21.Vậytổngcủabachữsốđầulà10.
Dễthấy 1 3 6 1 4 5 2 3 5 .
Vậycó3cáchchọn3nhóm3chữsốđầu[1,3,6hoặc1,4,5hoặc2,3,5].
Với1cáchchọnnhóm3chữsốthìcó3!cáchđểlậprasố a1a2a3 .
Với3sốcònlạithìcó3!cáchđểlậprasố a4a5a6 .
Vậycó3.3!.3!=108sốcầntìm.
Bài 7:
Từ các chữ số 1, 2,3, 4, 5, 6, 7,8,9 có thể lập được bao nhiêu số tự
nhiên gồm 6 chữ số khác nhau và tổng các chữ số hàng chục, hàng
trăm, hàng nghìn bằng 8.
Giải:
Gọisốcầntìmlà:
n a1a2 ...a6 , a1 0, ai 1,2,...,9 , i 1,6 .
Theobàira a3 a4 a5 8 .
13
Tacó 1 2 5 1 3 4 8 .Vậycóhaicáchchọnnhóm3sốđểtổngcácchữ
sốhàngchục,hàngtrăm,hàngnghìnbằng8.
Vớimỗinhómcó3!=6cáchlậprasố a3 , a4 , a5 .
Với 3 chữ số còn lại a1 , a2 , a6 là 1 bộ số có thứ tự được chọn từ
tập 1, 2,...,9 \ a3 , a4 , a5 .Có A36 cách.
3
Vậycó 2.3! A6 1440 sốthỏamãnbàitoán.
Bài 8:
Từ tập A 1, 2,3, 4,5, 6, 7 có thể lập được bao nhiêu số tự nhiên gồm
5 chữ số khác nhau và nhất thiết phải có hai chữ số 1 và 5.
Giải:
Trong5chữsốthìcó2chữsốlà1và5.Tachỉcầnchọnrabasốthuộctập
hợp 2,3, 4,6, 7 .Sốcáchchọnlà C 35 10 .
Với5sốđượcchọnracó5!cáchthànhlậpsốthỏamãn.
Vậycó 5!C53 1200.
Bài 9:
Từ tập A 0,1, 2,3, 4,5, 6 có thể lập được bao nhiêu số chẵn gồm 5
chữ số khác nhau trong đó có đúng hai chữ số lẻ và hai chữ số lẻ này
đứng cạnh nhau.
Giải:
Vìcó3sốlẻnêncó6sốképsau13,31,15,51,35,53.Bàitoántrởthành
cóbaonhiêusốchẵncó4chữsốkhácnhauđượclậptừtập B { 0, 2, 4, 6, số
kép}.
Gọi A1 , A2 , A3 lầnlượtlàtậphợpcácsốchẵncó4chữsốkhácnhauđượclập
từtập B trongđósốképđứngởvịtríthứnhất,thứhai,thứba.
Trườnghợp1:sốképđứngởvịtríthứnhất.
Bachữsốcònlạiđượcchọntừtập 0, 2, 4, 6 :Có A43 cáchchọn
14
n A1 A43 24
Trườnghợp2:sốképđứngởvịtríthứhaihoặcthứba.
Sốđứngđầuđượcchọntừtập 2, 4, 6 :có3cáchchọn
Hai chữ số cònlại được chọntừ tập 0, 2, 4, 6 \{chữ số đầu}: Có A32 cách
chọn.
Vậy n A2 n A3 3. A32 18
Vậycó 6 24 18 18 360 sốthỏamãnbàitoán.
Bài 10:
Số 360 có bao nhiêu ước tự nhiên ?
Giải:
Phântích360rathừasốnguyêntố: 360 23.32.5
Sốdlàướccủa360phảicódạng d 2m.3n.5 p với 0 m 3, 0 n 2, 0 p 1.
Vậytheoquytắcnhân,tacó 3 1 2 11 1 24 ướctựnhiêncủa360.
Tổng quát hóa
ĐểtìmsốcácướccủasốAtathựchiệntheocácbướcsau:
Bước1:PhântíchArathànhthừasốnguyêntố.
A p1n1 . p2n2 . p3n3 ... pknk . với pi 1, i 1, k vàđôimộtkhácnhau.
Bước2:SốdlàướccủaAphảicódạng
d p1a1 . p2a2 . p3a3 ... pkak . với 0 a1 n1 , 0 a2 n2 , 0 a3 n3 ,..., 0 ak nk .
Bước3:SốcácướctựnhiêncủaAlà n1 1 n2 1 n3 1 ... nk 1 .
Bài 11:
Có bao nhiêu số nguyên dương là ước của ít nhất một trong hai số
5400 và 18000?
Giải:
Đặt A x ¥ , x 5400 ; B x ¥ , x 18000 .
Yêucầubàitoánlàtìm A B
15
Trướchếttatìm A , B , A B
Tacó
5400 23.33.52
18000 2 4.32.53
Vậndụngkếtquảtổngquátcủabài10tacó
A 3 1 3 1 2 1 48
B 4 1 2 1 3 1 60
Mặtkháctậphợp A B làtậpcácướcnguyêndươngcủa5400và18000,
vìthế A B cũnglàtậphợpcủacácướcdươngcủaướcchunglớnnhấtcủa
5400và18000.
Mà 5400,18000 23.32.52 .
Vậytacó
A B 3 1 2 1 2 1 36 .
Cuốicùngtacó
A B A B A B 48 60 36 72
Bài 12:
Có bao nhiêu số nguyên của tập hợp 1;2;...;1000 mà chia hết cho 3
hoặc 5?
Giải:
Đặt S 1;2;...;1000 ; A x S xM3 ; B x S xM5
Yêucầubàitoánlàtìm A B
Tacó
1000
A
333
3
1000
B
200
5
16
Tải về bản full