Su dung cỏc khỏi niắm cơ ban
Quy tac c®ng, quy tac nhân
Nội dung quy tắc: Nếu có m1 cách chọn đối tượng a1, m2 cách chọn đối tượng a2, , mn cách chọn đối tượng an, trong đó cách chọn đối tượng ai (1 ≤ i ≤ n) không phụ thuộc vào bất kỳ cách chọn đối tượng aj nào.
1 m k cỏch cHQN đoi tưong a 1, hoắc a 2, ,
Nội dung quy tắc: Cho n đối tượng a1, a2, , an Nếu có m1 cách chọn đối tượng a1 và với mỗi cách chọn a1 có m2 cách chọn a2, sau đó với mỗi cách chọn a1, a2 có m3 cách chọn a3, và tiếp tục như vậy Cuối cùng, với mỗi cách chọn a1, a2, a3, , an-1 có mn cách chọn an Như vậy, tổng số cách chọn các đối tượng a1, a2, a3, , an sẽ là m1 * m2 * * mn.
Sau đây ta xét m®t so bài toán minh HQA:
Bài 1.Vúi sỏu chu so 0, 1, 2, 3, 4, 5 cú the lắp đưoc bao nhiờu so gom bon chu so khác nhau và trong moi so nhat thiet phai có chu so 1.
GQI so can lắp là abcd Xột cỏc trưũng hop:
Trưòng hop 1: a = 1 có 1 cách cHQN a, có
A 3 cách cHQN các chu so b, c, d.
Trưòng hop 2: a ƒ= 1 Có 4 cách cHQN a ( vì a ƒ= 0).
- Neu b = 1 thì có 1 cách cHQN b và có A 2
- Neu c = 1 thì có 1 cách cHQN c và có A 2
- Neu d = 1 thì có 1 cách cHQN d và có A 2 cách cHQN c, d; cách cHQN b, d; cách cHQN b, c;
Vắy theo quy tac cđng cú the lắp đưoc 1.A 3 + 4.A 2 + 4.A 2 + 4.A 2 204
Bài 2 Tù thành pho A đen thành pho B có 3 con đưòng, tù thành pho A đen thành pho C có 2 con đưòng, tù thành pho B đen thành pho D có 2 con đưòng, tù thành pho C đen thành pho D có 4 con đưòng Không có con đưòng nào noi thành pho B vói thành pho C. Hoi có tat ca bao nhiêu con đưòng noi tù thành pho A đen thành pho D.
Trong trường hợp 1, có 3 cách để đi từ A đen đến B và 2 cách để đi từ B đen đến D Theo quy tắc nhân, số cách đi từ A đen đến D qua B là 3 nhân 2, tức là 6 cách.
Trong trường hợp 2, có 2 cách để đi từ A đen đến C và 4 cách để đi từ C đen đến D Theo quy tắc nhân, số cách đi từ A đen đến D qua C là 2 nhân với 4, kết quả là 8.
Vì cách cHQN đưòng tù A sang D qua B và cách cHQN đưòng tù A sang
D qua C không phu thu®c lan nhau, nên theo quy tac c®ng, ta có so con đưòng đe đi tù A sang D là 6 + 8 = 14 (cách).
Bài 3 Tự cỏc chu so 1, 2, 3, 4, 5, 6, 7, 8, 9 cú the lắp đưoc bao nhiờu so gom 4 chu so khác nhau? Tìm tőng cna tat ca các so này.
GQI so can lắp cú dang abcd
Vắy theo quy tac nhõn thỡ so cỏc so cú the lắp đưoc là 9.8.7.6 3024
So lón nhat, so nho nhat trong các so dang n ày lan lưot là 987 6 v à 1234 có tőng bang 11110, nên đoi vói so bat kì abcd đeu ton tai so a J b J c J d J , mà
Khi đó, ta có đang thúc: abcd + a J b J c J d J = 11110
Từ đó, ta có các biểu thức a + aJ = b + bJ = c + cJ = d + dJ = 10a, với điều kiện aJ, bJ, cJ, dJ có các chữ số khác nhau Nếu abcd có các chữ số không trùng nhau, thì aJ, bJ, cJ, dJ cũng sẽ có các chữ số không trùng nhau Do đó, có 1.9.8.7.6 cách sắp xếp cho abcd, và aJ, bJ, cJ, dJ sẽ bao gồm 4 chữ số khác nhau thuộc tập {1, 2, 3, 4, 5, 6, 7, 8, 9}.
Vắy tőng tat ca cỏc so dang trờn là :
Bài 4 M®t con ngna trên bàn cò vua 8x8 Hoi có bao cách di chuyen con ngna trên bàn cò.
Các ô cờ bàn cũ có thể di chuyển theo quy tắc như sau: ô a11 có 2 cách di chuyển, ô a12 có 3 cách di chuyển, các ô a13, a14 và a22 có 4 cách di chuyển, ô a23 và a24 có 6 cách di chuyển, trong khi các ô a33, a34 và a44 có 8 cách di chuyển.
Lay đoi xúng các v% trí trên qua 4 truc đoi xúng cna bàn cò, ta có tőng so cách là: n = 4.2 + 8.3 + 20.4 + 16.6 + 16.8 = 336.
Bài 5 Cho bàn cò vua 8x8.
Có bao nhiêu cách cHQN ra 1 ô trang và 1 ô đen?
Có bao cách cHQN 1 ô trang, 1 ô đen cùng nam trên 1 hàng hay 1 c®t?
Trên bàn cò có 32 ô trang, 32 ô đen Có 32 cách cHQN ra m®t ô đen, 32 cỏch cHQN mđt ụ trang Vắy so cỏch cHQN n 12.3224 (cỏch).
Có 32 cách cHQN m®t ô trang So ô đen cùng hàng, cùng c®t vói ô trang đã cHQN ra là 8.
Vắy so cỏch cHQN n 22.8%6 (cỏch).
Bài 6 Có 28 quân domino o 2 đau có x,y cham 0 x, y 6 Có bao nhiêu cách cHQN ra 2 quân domino có the noi vói nhau (so cham o m®t đau cna quân này bang so cham o m®t đau quân khác).
Lay m®t quân domino bat kỳ nó thu®c m®t trong 2 loai:
Loai 2 (21 quân): có so cham 2 đau khác nhau.
- Neu quân domino cHQN ra là loai 1 (se có 7 cách chon) se đưoc noi vói
6 quân khác Ví du như (1,1) se đưoc noi vói (1,0), (1,2), (1,3),(1,4), (1,5),(1,6) Vắy so cắp noi đưoc trong trưũng hop này là: n 1 = 7.6 = 42.
- Neu quân domino cHQN ra là loai 2 (se có 21 cách cHQN), se đưoc noi vói
12 quân khác Ví du (2,3) se đưoc noi vói (2,0), (2,1), (2,4), (2,2), (2,5), (2,6),(3,0),(3,1),(3,2),(3,4),(3,5),(3,6).
Vắy so cắp noi đươc trong trưũng hop này là n 2 = 21.12 = 252 Theo quy tac c®ng thì so cách noi đươc là 252+42)4 (ke ca thú
Vỡ thỳ tn giua 2 đau cna quõn domini đưoc xỏc đ%nh, và moi cắp 2 tn). quân 294 domino noi đưoc đen 2 lan, ta suy ra so cắp noi đưoc là n 2 = 147.
Hoán v%
Hoán vị là một khái niệm quan trọng trong toán học, định nghĩa là việc sắp xếp một tập hợp gồm n phần tử theo một thứ tự nhất định Mỗi cách sắp xếp n phần tử này được gọi là một hoán vị Để hiểu rõ hơn về hoán vị, chúng ta có thể so sánh nó với các phép toán khác trong lý thuyết tập hợp.
Sau đây ta xét m®t so bài oán minh HQA:
Bài 7.Vúi năm chu so 1, 2, 3, 4, 5 cú the lắp đưoc bao nhiờu so gom năm chu so khác nhau?
Moi so can lắp là mđt hoỏn v% cna năm chu so đó cho.
Vắy so cỏc so lắp đưoc bang so hoỏn v% cna năm phan tu bang
Bài 8 Trong m®t h®i ngh% có 5 báo cáo viên A, B, C, D, E moi ngưòi báo cáo m®t lan?
1 Có bao nhiêu cách xep thú tn cho báo cáo viên.
2 Có bao nhiêu cách xep thú tn cho báo cáo viên neu yêu cau báo cáo viên B báo cáo ngay sau báo cáo viên A?
3 Có bao nhiêu cách xep thú tn cho báo cáo viên neu B không báo cáo trưóc A?
1 So cách xep thú tn cho báo cáo viên bang 5! = 120
2 B bỏo cỏo ngay sau A ta thay the bang mđt cắp bỏo cỏo viờn XAB Khi đó, xem X như là m®t báo cáo viên.
3 Trong MQI cách sap xep kha năng A đúng trưóc B hay đúng sau B là như nhau.
Vắy so cỏch sap xep B khụng bỏo cỏo trưúc A là
Bài 9 Có bao nhiêu cách xep 5 ngưòi đàn ông, 5 ngưòi đàn bà xung quanh mđt bàn trũn 10 ghe sao cho khụng cú 2 ngưũi đàn ụng hoắc
2 ngưòi đàn bà nào ngoi canh nhau.
Sắp xếp 1 người đàn ông thì tiếp theo là 1 người phụ nữ Số cách sắp xếp 5 đàn ông vào vị trí có sẵn là 5!, và số cách sắp xếp 5 phụ nữ vào vị trí là 5! Do đó, tổng số cách sắp xếp theo vị trí này là 5! x 5!.
Neu xep 1 ngưòi đàn bà thì so cách xep tương tn bang 5!5!. Đáp so:: 2.(5!) 2
Hoỏn v% cú lắp Đ%nh nghĩa: Hoỏn v% trong đú moi phan tu xuat hiắn ớt nhat mđt lan đưoc gQI là hoỏn v% cú lắp.
So hoỏn v% lắp cna n phan tu thuđc k loai, mà cỏc phan tu loai i
(1 i k) xuat hiắn n i lan đưoc kớ hiắu là P (n 1 , n 2 , , n k ) và đưoc tính bang công thúc
Sau đây ta xét m®t so bài toán minh HQA:
Bài 10 Vúi cỏc chu so 1, 2, 3, 4, 5, 6 cú the lắp đưoc bao nhiờu so gom chớn chu so, trong đú moi chu so 1, 2, 3, 4 xuat hiắn đỳng mđt lan, chu so 5 xuat hiắn đỳng hai lan và chu so 6 xuat hiắn đỳng ba lan.
Xột mđt số tự ý x = 154626356 và kớ hiắu các v% trớ cna x mđt cách hình thức, ta có x = a1 a2 a3 a4 a5 a6 a7 a8 a9 Mỗi số x tương ứng với một hoá n% lắp cna các phần tử a1, a2, a3, a4, a5, a6, a7, a8, a9.
So các hoán v% khác nhau cna chín phan tu a i (1 i 9) là 9! song do a 2 = a 8 = 5 nên khi đői cho a 2 và a 8 cho nhau thì hoán v
% x = a 1 a 2 a 3 a 4 a 5 a 6 a 7 a 8 a 9 van chi cho ta so x.
Tương tu đői cho hai trong ba phan tu a 4 , a 6 , a 9 cho nhau van chi cho so x.
Như vắy, khi thnc hiắn 2! hoỏn v% a 2 , a 8 và 3! hoỏn v% a 4 , a 6 , a 9, ta chi đưoc m®t so can tìm x.
Vắy so cỏc so cú the lắp đưoc là
Bài 11 Vúi sỏu chu so 0, 1, 2, 3, 4, 5 cú the lắp đưoc bao nhiờu so chia het cho 5 gom 11 chu so, trong đú chu so 1 cú mắt 4 lan, chu so
2 cú mắt 3 lan, chu so 3 cú mắt 2 lan chu so 4 cú mắt 1 lan và tőng so lan xuat hiắn cna chu so 0 và chu so 5 là 1.
Bài giai Đe so can lắp x = a 1 a 2 a 3 a 4 a 5 a 6 a 7 a 8 a 9 a 10 a 11 chia het cho 5, thỡ x phai tắn cựng bang chu so 0 hoắc chu so 5.
Trong khoảng từ 0 đến 5, nếu x lớn hơn hoặc bằng 0 thì số 5 không xuất hiện, và ngược lại, nếu x lớn hơn hoặc bằng 5 thì số 0 không xuất hiện Do đó, các số (1 đến 10) chỉ có thể là một trong các chữ số 1, 2, 3, 4 Vì vậy, khả năng lắp ghép dãy dài 10 chữ số từ a1 đến a10, trong đó x là số hoàn hảo, sẽ có 10 phần tử thuộc 4 loại chữ số: 1, 2, 3, 4 với 1 xuất hiện 4 lần, 2 xuất hiện 3 lần.
3 xuat hiắn 2 lan và 4 xuat hiắn 1 lan se bang P (1, 2, 3, 4) Ngoài ra a 11 lai cú the nhắn 0 hoắc 5 nờn cú the lắp đưoc
Bài 12 Có bao nhiêu cách đao tù PARABOLA sao cho các phu âm và nguyên ân đưoc xep xen ke.
Vì có 4 phu âm và 4 nguyên âm nên ta xep 4 phu âm (có 4! cách xep) và xep vào 4 v% trí xem ke 4 nguyên âm là4!.
V% trớ ban đau cú the là phu õm hoắc nguyờn õm đoi vúi moi hoỏn v
% 4! cna phu âm Suy ra so cách xep: n 2.4!.
Bài 13 Tìm so cách đao tù ROKOKO sao cho 3 chu O không đúng lien nhau.
Tat ca các cách đao tù bang n 1 = 6!
So cách đao tù mà 3 chu O đúng canh nhau (coi như là m®t chu) bang n 2 4!
Ta xét m®t ví du đơn gian sau:
Xột tắp A = a, b , ta lắp tắp B = a, a, b, b, b Khi đú B = (A, α)
,α(a) = 2, a xuat hiắn 2 lan, α(b) = 3 GQI là tắp bđi so lan xuat hiắn α Khi đó, so cách xep thành m®t hàng ngang cna B bang:
Mo rđng, xột tắp A = {x 1 , x 2 , , x n } gom n phan tu riờng biắt.
Xột tắp bđi B trong đú x i xuat hiắn α(x i ) = α i lan Khi đú, so cỏch xep thành m®t hàng ngang cna B bang
Ví dn dan dat Mòi sáu ngưòi khách ngoi xung quanh m®t bàn tròn
Hoi có bao nhiêu cách sap xep cho ngoi.
Neu ta mòi m®t ngưòi nào đó ngoi vào m®t v% trí bat kì, thì so cách sap xep 5 ngưòi còn lai vào 5 v% trí giành cho HQ se là 5! = 120.
Vắy cú tat ca 120 cỏch sap xep 6 ngưũi ngoi xung quanh mđt bàn tròn.
So hoán v% vòng quanh cna n phan tu khác nhau (Q n ) đưoc tính bang công thúc
Sau đây ta xét m®t so bài toán minh HQA
Bài 14 M®t h®i ngh% bàn tròn có năm nưóc tham gia Anh có 3 đai bieu,
Có 5 đại biểu Phỏp, 2 đại biểu Đỳc, 3 đại biểu Nhắt và 4 đại biểu My Hỏi có bao nhiêu cách sắp xếp cho ngồi cho MQI đại biểu sao cho hai người cùng quốc tịch đều ngồi cạnh nhau.
Để sắp xếp khu vực VNC cho đại biểu các nước, chúng ta cần xác định cách sắp xếp các phái đoàn Có 4! cách sắp xếp các phái đoàn vào vị trí đầu tiên Đối với mỗi cách sắp xếp phái đoàn, số cách sắp xếp đại biểu trong từng phái đoàn là: 3! cho phái đoàn Anh, 5! cho phái đoàn Pháp, 2! cho phái đoàn Đức, 3! cho phái đoàn Nhật và 4! cho phái đoàn Mỹ.
Boi vắy, so cỏch sap xep cho ngoi cho tat ca cỏc đai bieu đe nhung ngưòi cùng quoc t%ch ngoi canh nhau se bang
Bài 15 Có bao nhiêu cách sap xep 5 nam A 1 , A 2 , A 3 , A 4 , A 5 và 3 nu
B 1 , B 2 , B 3 vào m®t bàn tròn sao cho: a) Khụng cú đieu kiắn gỡ?; b) Nam A 1 không ngoi canh nu B 1? c) Nu không ngoi canh nhau?
Mỗi cách sắp xếp bất kỳ là một hoán vị vòng quanh 8 phần tử, do đó số cách sắp xếp bằng số hoán vị vòng quanh 8 phần tử là Q8 = 7! = 5040 Đối với năm nam và hai nữ không kề B1, có (7 - 1)! = 6! cách sắp xếp Trong một số phương án sắp xếp năm nam và hai nữ không kề B1, B1 có thể được xếp vào giữa A2, B2 hoặc giữa B2, A4.
A 4 , B 3, giua A 5 , B 3, giua A 3 , A 5 Như vắy cú 7 2 = 5 cỏch sap xep B 1
6!.5 = 720 cách sap xep. c) Trưóc het ta xep 5 nam ngoi xung quanh bàn tròn So cách sap xep này bang so hoán v% vòng quanh cna 5 phan tu, bang (5 − 1)! = 4!
= 24 Có 5 cách sap xep nu B 1, 4 cách sap xep nu B 2 và 3 cách sap xep nu B 3 Vắy so cỏch sap xep can tỡm là 4!.5.4.3 = 1440.
Chinh hop
Tập hợp A hữu hạn là một tập hợp chứa n phần tử, trong đó n có thể bằng 0 hoặc n lớn hơn 0 Mỗi tập hợp con của A được gọi là tập hợp con, và tập hợp con này có thể chứa k phần tử thuộc A.
Ta ký hiắu so chinh hop chắp k cna n phan tu bang A k
So chinh hop chắp k cna n phan tu đưoc tớnh boi cụng thỳc k n ! n = n(n − 1) (n − k + 1) (n − k)!.
ChÉng minh Đe cú mđt hoỏn v% chắp k ta làm như sau:
Có n cách lay ra phan tu thú 1
Có n-1 cách lay ra phan tu thú 2
Có n-k+1 cách cHQN ra phan tu thú k
Theo quy tac nhân, so hoán v% cna k phan tu bang n(n-1) (n-k+1)
Sau đây ta xét m®t so bài toán minh HQA:
Bài 16 Tự cỏc chu so 0, 1, 2, 3, 4, 5 cú the lắp đưoc bao nhiờu so tn nhiên mà trong moi so này các chu so khác nhau?
Ta xét các trưòng hop sau:
Trưũng hop 1: Lắp so cú 1 chu so cú 6 so;
Trưũng hop 2: Lắp so cú 2 chu so cú 5.5 25 so;
Trưũng hop 3: Lắp so cú 3 chu so cú 5.A 2 = 100 so;
Trưũng hop 4: Lắp so cú 4 chu so cú 5.A 3 = 300 so; Trưũng hop 5: Lắp so cú 5 chu so cú 5.A 4 600 so; Trưũng hop 6: Lắp so cú 6 chu so cú
Vắy so cỏc so tn nhiờn cú the lắp là 6 + 25 + 100 + 300 + 600 +
Bài 17 M®t cu®c khiêu vũ có 10 nam và 6 nu tham gia Đao dien cHQN cú thỳ tn 4 nam và 4 nu đe ghộp thành 4 cắp Hoi cú bao nhiêu cách cHQN?
Moi cỏch cHQN cú thỳ tn 4 nam trong 10 nam là mđt chinh hop chắp 4 cna 10 So chinh hop này là
= 5040 Vắy cú 5040 cách cHQN 4 nam.
Moi cỏch cHQN cú thỳ tn 4 nũ trong 6 nũ là mđt chinh hop chắp 4 cna
6 So chinh hop này là A 4 6!
= 360 Vắy cú 360 cỏch cHQN 4 nu.
Có 5040 cách chọn 4 nam và 360 cách chọn 4 nữ, do đó tổng số cách chọn 4 nam và 4 nữ trong một hội diễn là 1.814.400 cách.
Bài 18 Có 7 thành viên úng cu vào h®i đong trưòng Hoi có bao nhiêu cách cHQN ra m®t chn t%ch, m®t phó chn t%ch, m®t thư ký, m®t thn quy trong so HQ.
Có 7 cách cHQN 1 ngưòi làm chn t%ch.
Có 6 cách cHQN 1 ngưòi làm phó chn t%ch trong so còn lai
Có 5 cách cHQN 1 ngưòi làm thư ký.
Có 4 cách cHQN 1 ngưòi làm thn quy.
Theo quy tac nhân, so cách cHQN bang n=7.6.5.40.
Từ tập A = {0, 1, 2, 3, 4, 5}, câu hỏi đặt ra là có bao nhiêu số gồm 4 chữ số phân biệt được tạo thành từ các chữ số trong A Ngoài ra, cần xác định số lượng số chẵn có 4 chữ số phân biệt cũng được hình thành từ các chữ số trong A.
Ta chia tat ca các so chan thành 2 loai:
Loai 1: So 0 đúng cuoi cùng.
Loai 2: So 2 hoắc so 4 đỳng cuoi cựng.
So cỏc so gom 4 chu so phõn biắt mà so 0 đỳng cuoi bang S 1 A 3 ` So cỏc so mà so 2 hoắc 4 đỳng cuoi cựng (theo quy tac nhân) bang
Bài 20 Cho tắp A = 0, 1, 2, 3, 4, 5 cú bao nhiờu so gom 4 chu so phõn biắt cna A chia het cho 5.
- Xét các so mà chu so 0 đúng cuoi cùng Trong trưòng hop này so các so thoa mãn yêu cau cna bài toán bang n 1 = A 3 = 60.
- Xét các so có so 5 đúng cuoi cùng, ta can cHQN thêm 3 chu so phân biắt (so cú 3 chu so phõn biắt) xep phớa trờn so 5.
Cú 5.4.3 bđ 3 so phõn biắt.
Cú 4.3 so phõn biắt mà so 0 đỳng đau.
Suy ra so các so thoa mãn yêu cau cna bài toán trong trưòng hop này bang n 2 = 5.4.3 4.3 = 48. Đáp so n = n 1 + n 2 = 60 + 48 = 108.
Chỉnh hợp lặp định nghĩa là cách sắp xếp các phần tử trong tập hợp X, trong đó mỗi phần tử có thể được lặp lại nhiều lần Mỗi dãy được tạo ra có độ dài cố định và không chứa các phần tử không thuộc tập X Định nghĩa này cho thấy rằng chỉnh hợp lặp là một phương pháp sắp xếp các phần tử theo một trật tự nhất định, không phụ thuộc vào các phần tử trong tập X.
Số chỉnh hợp lắp chắp không chứa phần tử k có thể hiểu là A không bằng số ánh xạ tự tập không phần tử đen tắp n phần tử và bằng n k, tức k = n k Dưới đây, chúng ta sẽ xem xét một số bài toán minh họa.
Bài 21.Tự bon chu so 1, 2, 3, 5 cú the lắp đưoc bao nhiờu so chan gom 4 chu so?
GQI so can lắp cú dang x = abcd Vỡ x là so chan nờn d = 2
Moi cỏch cHQN bđ ba chu so a, b, c là mđt chinh hop lắp chắp 3 cna
Vắy so cỏc so chan cú the lắp đưoc bang A 3 = 4 3 = 64.
Bài 22.Cú the lắp đưoc bao nhiờu bien so xe vúi hai chu cỏi đau thuđc tắp {A, B, C, D, E}, tiep theo là mđt so nguyờn dương gom năm chu so chia het cho 5?
Gia su bien so xe can lắp cú dang XY abcde.
Vỡ X, Y cú the trựng nhau nờn XY là chinh hop lắp chắp 2 cna 5 phan tu A, B, C, D, E, nên so cách cHQN XY bang
Do a = 0 nên có 9 cách cHQN a
Khi giải phương trình vỡ abcde chia hết cho 5, ta có hai trường hợp là e = 0 hoặc e = 5 Do b, c, d có thể trùng nhau, nên mọi bậc b, c, d đều là một tổ hợp chính hợp lắp chắp 3 trong 10 Vì vậy, số cách chọn bậc b, c, d sẽ được tính bằng công thức tổ hợp.
3 = 10 3 = 1000 Vắy so bien so xe cú the lắp đưoc theo yờu cau là:25.2.1000 50000.
To hap khụng lắp Đ%nh nghĩa Cho tắp A gom n phan tu Moi tắp con gom k (0 k n) phan tu thuđc A đưoc gQI là tő hop chắp k cna n phan tu đó cho. n
Hai tő hop đưoc coi là khác nhau khi và chi khi có ít nhat m®t phan tu khác nhau.
So tő hop chắp k (0 ≤ k ≤ n) cna n phan tu đưoc kớ hiắu là C k và đưoc tính theo công thúc
Sau đây ta xét m®t so bài toán minh HQA:
Bài 23 Có bao nhiêu cách chia m®t lóp 40 HQc sinh thành 4 tő, sao cho moi tő có đúng 10 HQc sinh.
Bài giai Đau tiờn lắp tő 1 bang cỏch cHQN tựy ý 10 HQc sinh trong 40 HQc sinh cna lúp So cỏch cHQN bang so cỏc tő hop chắp 10 cna 40, bang
Tő 2 có the cHQN 10 em tùy ý trong 30 em còn lai, so cách cHQN bang so cỏc tő hop chắp 10 cna 30, bang
Tő 3 có the cHQN 10 em tùy ý trong 20 em còn lai, so cách cHQN bang so cỏc tő hop chắp 10 cna 20, bang
Tő 4 gom 10 em còn lai nên chi có 1 cách cHQN.
Vắy so cỏch chia se là
Bài 24 M®t lóp HQc sinh có 40 em gom 25 nam và 15 nu Giáo viên chn nhiắm đ%nh cHQN mđt ban cỏn sn gom 4 ngưũi Hoi cú bao nhiờu cỏch cHQN neu: a) So nam hoắc nu trong ban là tựy ý? b) Ban cán sn có 1 nam và 3 nu ? c) Ban cán sn có 2 nam và 2 nu? n d) Ban cán sn có ít nhat 1 nam? e) Ban cán sn có ít nhat 1 nam và m®t nu?
Bài giai a) Neu so nam (nu) là tựy ý, thỡ so cỏch cHQN là so cỏc tő hop chắp 4 cna 40 phan tu, bang
= 91390 (cách) b) Neu trong ban cán sn có 1 nam và 3 nu, thì so cách cHQN 1 nam trong
25 nam là C 1 cũn so cỏch cHQN 3 nu trong so 15 nu là C 3 Vắy so cỏch cHQN theo yêu cau là
3!12! c) Tương tn như trên, so cách cHQN 2 nam và 2 nu là
2!13! d) Neu trong ban cán sn có ít nhat 1 nam thì có 4 kha năng xay ra:
4 nam và không nu có
25 15 25 e) Neu ban cỏn sn gom toàn nam (nu) cú C 4 (C 4 ) cỏch cHQN Vắy so
25 15 cách cHQN đe ban cán sn có ít nhat 1 nam và ít nhat 1 nu là
Bài 25 Cho 6 điem trờn mắt phang sao cho khụng cú 3 điem nào thang hàng Hoi có bao nhiêu đưòng thang đi qua 2 điem trong 6 điem này.
Theo gia thiet, tự mđt cắp 2 điem xỏc đ%nh duy nhat mđt đưũng thang Vắy so đưũng thang bang so cắp 2 điem tự 6 điem: n = C 2 15.
Bài 26 Tù 7 HQc sinh nam, 4 HQc sinh nu Hoi có bao nhiêu cách chQn m®t đ®i bóng chuyen cho 6 em sao cho trong đ®i có ít nhat 2 nu.
Ký hiắu S 2 là tắp cỏc đđi búng cú 2 nu, S 3 là tắp cỏc đđi búng cú 3 nu,
S 4 là các đ®i bóng có 4 nu.
Có C 2 cách cHQN 2 nu, C 4 cách cHQN 4 nam Suy ra, |S 2 | = C 2 C 4
Vắy so cỏch cHQN bang n = |S 2 | + |S 3 | + |S 4 | = 6.35 + 4.35 + 1.21 371
Bài 27 Cú 12 nam, 15 nu Hoi cú bao nhiờu cỏch cHQN ra 4 cắp nhay (moi cắp 1 nam, mđt nu).
Cách sắp xếp 4 em nam và 4 em nữ thành một hàng là một bài toán thú vị trong tổ hợp Khi sắp xếp, chúng ta có thể tạo ra các cặp nhảy từ 2 em đứng cạnh nhau Số cách sắp xếp này được tính bằng công thức n = C(4,4) * C(4,4) * 4!.
Khi chọn 1 em nam trong 4 em, có 4 cách để chọn 1 em nữ Nếu chọn 1 em nam trong 3 em còn lại, sẽ có 3 cách chọn 1 em nữ từ 3 em nữ còn lại Tiếp tục, nếu chọn 1 em nam trong 2 em còn lại, có 2 cách chọn 1 em nữ Do đó, tổng số cách sắp xếp cho 4 em nam và 4 em nữ là 4!
To hap lắp Đ%nh nghĩa Cho tắp hop A = a 1 , a 2 , , a n Mđt tő hop lắp chắp m
(m không nhat thiet phai nho hơn n) cna n phan tu thu®c A là m®t b® gom m phan tu mà moi phan tu này là m®t trong nhung phan tu cna
Ta su dung C m đó đe kớ hiắu so tő hop lắp chắp m cna n phan tu Khi
Sau đây ta xét m®t so bài toán minh HQA:
Bài 28 Gia su có 4 loai bóng màu: Xanh, Đo, Tím, Vàng vói so lưong moi loai không han che Hai b® bóng đưoc xem là khác nhau neu có ít nhat m®t màu vói so lưong thu®c hai b® khác nhau Hoi có bao nhiêu cách cHQN ra các b® 6 (qua bóng) khác nhau?
Trong mỗi bộ sáu quả bóng, có thể xuất hiện các quả bóng cùng màu mà không phân biệt thứ tự, do đó cách chọn khác nhau sẽ được tính bằng số tổ hợp lắp chắp 6 chọn 4 phần tử Tổ hợp bóng cùng màu được coi là một phần tử và được tính theo công thức tổ hợp.
Bài 29.Tien giay cna Ngõn hàng quoc gia Viắt nam ban hành phő bien trên th% trưòng có 10 loai 200đ, 500đ, 1000đ, 2000đ, 5000đ, 10000đ, 20000đ, 50000đ, 100000đ, 500000đ Hãy xác đ%nh so b® khác nhau gom 15 tũ giay bac cna Ngõn hàng quoc gia Viắt Nam.
Phép tương úng 1- 1
Mô ta phan tu đem
Ky năng này gom 2 bưóc:
2 Sap xep vào v% trí đã chQn.
Sau đây chúng ta xét m®t so bài toán minh HQA:
Bài 1 Tìm các so nguyên dương có 6 chu so bao gom 3 chu so chan và 3 chu so le.
Ta cú C 3 cỏch lay ra 3 v% trớ đe đắt 3 chu so chan và 3 v% trớ cũn lai đắt
Trong bài viết này, chúng ta sẽ khám phá quy tắc về việc sử dụng 3 chữ số lẻ và 5 cách quản lý 1 chữ số chẵn hoặc lẻ Theo quy tắc, chúng ta có thể có 6 chữ số, trong đó bao gồm 3 chữ số chẵn và 3 chữ số lẻ.
Nếu chữ số 0 không đúng, chỉ có 5 chữ số hợp lệ, vì vậy cần loại bỏ các chữ số này Có 2 cách để đạt được chữ số chẵn, do chữ số 0 không chính xác Do đó, chữ số bắt buộc phải là 2, 5 hoặc 5.
Bài 2 Cho tắp A = 1, 2, 3 Cú bao nhiờu so nguyờn dương gom 10 chu so lắp đưoc tự tắp A, trong đú chu so 3 xuat hiắn đỳng 2 lan.
Hoi có bao nhiêu so trong các so này chia het cho 9.
Cú C 2 cỏch chQn 2 v% trớ trong 10 v% trớ đe đắt so 3 Tai moi v% trớ trong 8 v% trớ cũn lai cú 2 cỏch sap xep (1 hoắc 2) Vắy đỏp so d = C 2 2 8 11520.
Ký hiắu S(n) là tőng cỏc chu so cna so n (vúi n là so thoa món yờu cau cna bài toán) Ta suy ra: 14 = 6 + 8.1 S(n) 6 + 8.2 = 22
S(n) chia hết cho 9, do đó S(n) = 18 Với hai số 3, tổng 8 chữ số còn lại là 12, chỉ có thể có bốn số 2 và bốn số 1 Vì vậy, số các số thỏa mãn yêu cầu bài toán và chia hết cho 9 là d2 = P(2, 4, 4) = 10!.
Bài 3 Có bao nhiêu so gom 4 chu so đưoc cau tao tù nhung chu so cna so 123124.
Trong khả năng mô tả các phần tử trong những bài toán phức tạp, bước đầu tiên là phân loại các phần tử có tính chất giống nhau, thường được gọi là GQI Các cấu trúc được mô tả trong những trường hợp cụ thể này sẽ giúp hiểu rõ hơn về các mối quan hệ và đặc điểm của chúng.
1 Cú 4 chu so phõn biắt d 1 = 4! (vỡ chi cú 4 chu so phõn biắt 1,2,3,4).
2 Cú 2 cắp chu so giong nhau (2,2,1,1): d 2 4!
3 Cú 1 cắp chu so giong nhau, cũn 2 chu so cũn lai là phõn biắt Cú 2 cỏch cHQN mđt cắp 2 chu so giong nhau và C 2 cỏch cHQN 2 chu so phõn biắt tự 3 chu so phõn biắt cũn lai Suy ra d 3 = 2.C 2 P (2, 1, 1) = 72 Đáp so: 24+6+72 2.
Bài 4 Cho tắp A = 1, 2, 3, 4, 5 Hoi cú bao nhiờu so gom 6 chu so cna A trong đó có 3 so a, 2 so b và 1 so c, vói a, b, c là các so đôi m®t phõm biắt thuđc A.
Cú C 3 cỏch lay 3 so phõn biắt đụi mđt a, b, c cna tắp A Cú 3 cỏch chi đ%nh so nào xuat hiắn 3 lan, so nào xuat hiắn 2 lan se cú 2 cỏch chi đ
%nh, hien nhiờn so cũn lai xuat hiắn 1 lan và ta cú đỏp so d = C 3 3.2 6!
Bài 5 Cho tắp A = 0, 1, 2, 3, 4, 5 Hoi cú bao nhiờu so gom 5 chu so cna A sao cho moi so có đúng 3 chu so giong nhau.
Trưóc het ta tìm so b® 5 chu so thoa mãn yêu cau cna bài toán, sau đó bót đi các b® so có so 0 đúng đau.
Có C 3 cách cHQN 3 v% trí trong 5 v% trí đe xep 3 chu so giong nhau, có
6 cỏch cHQN 1 trong 6 so đe viet vào 3 v% trớ đó cHQN (ký hiắu là a), cú 5 cách cHQN b ƒ= a, 5 cách chQn c ƒ= a (b, c có the giong nhau).
Xét trưòng hop so 0 đúng đau:5
- Trưòng hop 1 (có 3 so giong nhau khác 0).
Cú C 3 cỏch cHQN 3 v% trớ đe đắt 3 so giong nhau a ∈ A, cú 5 cỏch cHQN a = 0, a A, cú 5 cỏch cHQN b A, b = a đắt vào v% trớ cũn lai Vắy so b® trong trưòng hop này bang d 2 = C 3 5.5
- Trưòng hop 2 (3 so giong nhau là 3 so 0).
Có C 2 cách cHQN 2 v% trí đe viet thêm 2 so 0, có 5 cách cHQN a ∈ A, a ƒ 0, 5 cỏch cHQN c ∈ A, c ƒ= 0 đe đắt vào 2 v% trớ cũn lai, Vắy so bđ cna trưòng
Bài 6 Tìm so các so nguyên có 4 chu so đưoc cau tao boi đúng 2 chu so phõn biắt.
Có C(2, 2) = 45 cách chọn 2 chữ số từ 10 chữ số Từ 2 chữ số đó, chúng ta có thể tạo thành 24 số có 4 chữ số, nhưng cần trừ đi 2 trường hợp khi số đó chỉ gồm 1 chữ số (a, a, a, a) hoặc (b, b, b, b) Vậy số bắt đầu thỏa mãn yêu cầu bài toán là C(2, 2) * (24 - 2).
Sau đây ta trù đi các b® so có so 0 đúng đau Có C 1 cách cHQN thêm
1 so khác 0, có 2 3 cách tao thành b® 3 so xep sau so 0 (trù 1 trưòng hop 0000) Ta có d 2 = C 1 (2 3 − 1). Đáp so: d = d 1 − d 2 = 630 − 63 = 567.
Mã hóa 0, 1 phan tu đem
Khi bài toán liên quan đến việc phân chia các phần tử theo quy tắc hoặc trò chơi, người ta thường mô tả các phần tử bằng cách sử dụng các giá trị nhị phân 0 và 1 để đơn giản hóa quá trình giải quyết.
Sau đây ta xét m®t so bài toán minh HQA:
Bài 7 e mđt cua hiắu cú 12 loai bưu thiep, hoi cú bao nhiờu cỏch mua 8 bưu thiep đe gui đen các đ%a chi khác nhau.
Ta viet n 1 so 1 neu n 1 so thiep loai 1 đưoc mua (n 1 = 0 ta không viet so nào), sau đó viet tiep so 0.
Ta lai viet n 2 so 1 neu n 2 so thiep loai 2 đưoc mua, sau đó viet tiep so 0.
Để giải bài toán này, chúng ta cần xác định số cách mua bưu thiếp với 12 số, trong đó có 8 số 1 và 11 số 0 Tổng số lượng số 1 và số 0 là 8, với 8 số 1 và 11 số 0 được sắp xếp theo một thứ tự nhất định Chúng ta có 8 cách để chọn 8 vị trí trong 19 vị trí để điền số 1, trong khi các vị trí còn lại sẽ được điền số 0.
Vắy so cỏch mua bưu thiep cna khỏch du l%ch bang P (8,
Bài 8 Có bao nhiêu cách chia 15 qua bóng như nhau cho 6 em
HQc sinh sao cho moi em HQc sinh đưoc phát ít nhat m®t qua bóng.
Trưóc het ta phát cho moi HQc sinh m®t qua bóng và đưa ve bài toán
"Có bao nhiêu cách phát 9 qua bóng cho 6 HQc sinh".
Viet x 1 so 1 neu phát x 1 bóng cho hQc sinh thú 1, sau đó viet tiep so
0 Viet x 2 so 1 neu phát x 2 bóng cho hQc sinh thú 2, sau đó viet tiep so
0 Tiep tuc như vắy đen bưúc cuoi cựng là viet x 6 so 1 neu phỏt x 6 qua bóng cho HQc sinh thú 6.
Vắy so cỏch phỏt bang so bđ gom x 1 + x 2 + + x 6 = 9 so 1 và 5 so 14!
Bài 9.Tìm so b® 3 so (x, y, z) nguyên dương thoa mãn đang thúc x + y + z = 1000.
Bài toán tìm số nguyên không âm (u, v, t) thỏa mãn điều kiện u + v + t = 997 có thể được biểu diễn dưới dạng các chuỗi số nhị phân Mỗi bộ số (u, v, t) tương ứng với một chuỗi nhị phân gồm các ký tự 0 và 1, trong đó các ký tự 1 đại diện cho số lượng của từng biến Việc tìm kiếm các giá trị này giúp giải quyết bài toán một cách hiệu quả.
Moi b® này gom 997 so 1 và 2 so 0 nên so b® này bang P 999!
(997, 2) Bài 10 Chúng ta phát 15 qua bóng cho 6 HQc sinh.
1 Tìm so n 1 cách phát bóng cho HQc sinh?
2 Tìm so n 2 cách phát bóng cho hQc sinh sao cho moi em có ít nhat m®t qua?
1) Chú ý: Hai cách phát đưoc GQI là khác nhau neu có ít nhat m®t HQc sinh nhắn so búng khỏc nhau trong hai cỏch phỏt Neu phỏt x 1 qua bóng cho HQc sinh thú 1 ta viet x 1 so 1 (neu không phát thì không viet gì) và sau đó viet so 0 Và ta lai viet x 2 so 1 neu phát x 2 bóng cho HQc sinh thú 2, sau đó viet so 0.
Cỳ tiep tuc vắy viet x 6 so 1 neu phỏt x 6 búng cho HQc sinh thỳ 6.
Để phát bàng một bộ số, cần chọn 15 số, bao gồm 1 số 5 và 0 số 0 Để có bộ số như vậy, ta cần sử dụng quy tắc 5% cho số 0 trong tổng 20% số được chọn, còn lại sẽ là số 1.
Vắy so cỏch phỏt bang n 1 = C 5
2) Ta phát cho moi em m®t qua bóng và sau đó phát 9 qua bóng cho 6 em theo cách trên và thu đưoc so cách phát bang n 2 = C 5
Bài 11.Có bao nhiêu cách chia 7 thùng nho, 5 thùng táo như nhau cho 3 HQc sinh (Hai cách chia là khác nhau neu có ít nhat m®t
HQc sinh nhắn đưoc so thựng nho hoắc tỏo khỏc nhau o hai cỏch).
Neu phát x 1 thùng nho cho HQc sinh thú 1 ta viet x 1 so 1 (neu không phát ta viet so 0), sau đó viet so 0.
Neu phát x 2 thùng nho cho HQc sinh thú 2 ta viet x 2 so 1, sau đó viet so 0 Và viet x 3 so 1 neu phát x 3 thùng nho cho HQc sinh thú 3.
Vắy so cỏch phỏt bang so bđ gom 7 so 1 và 2 so 0 đưoc xep theo thú tn bat kỳ Suy ra so cách phát bang: n 1 = C 2
Sau khi phát nho chúng ta lai tiep tuc phát 5 thùng táo cho 3 HQc sinh Tương tn so cách phát bang n 2 = C 2
Theo quy tac nhân so cách phát này là: n = n 1 n 2 = C 2 C 2
Bài 12.Vúi n ∈ N co đ%nh, Tỡm so nghiắn phương trỡnh x 1 + x 2 + + x k = n.
1 Trờn tắp cỏc so nguyờn khụng õm.
2 Trờn tắp cỏc so nguyờn dương.
1 Moi nghiắm (x 1 , x 2 , , x k ) tương ỳng 1-1 vúi mđt bđ cỏc so 0, 1 theo quy tac sau:
Viet x 1 so 1 (neu x 1 = 0 ta không viet so nào) Viet so 0 mô ta dau phay Tiep tuc cho đen x k so 1 cuoi cùng vì b® so thoa mãn x 1 + x 2 +
+ x k = n nên gom n so 1 và k 1 so 0. Đe cú mđt bđ so như vắy chỳng ta can cHQN ra n v% trớ đe viet n so 1 trong n + k − 1 v% trí.
2 Ta đắt y i = x i − 1(i = 1, 2, , k) và moi bđ (x 1 , x 2 , , x k ) tương ỳng 1-1 vói b® (y 1 , y 2 , , y k ) thoa mãn y 1 + y 2 + + y k = n k vói y i không âm.
Giai tương tn phan (1) ta có đáp so n 2 = C n−k+k−1 n−k = C n−1 n−k = C k−1 n−1
Bài 13.Mđt cua hiắu cú bỏn 5 loai cà phờ khỏc nhau Hoi cú bao cách đe 1 ngưòi mua 12 gói? Có bao cách đe 1 ngưòi mua 12 gói trong đó moi loai có ít nhat 2 gói?
1 Neu mua x 1 gói loai 1 ta viet x 1 so 1, sau đó viet so 0 Tương tn viet x 5 so 1 neu mua x 5 gói loai 5 Vì x 1 + x 2 + x 3 + x 4 + x 5 = 12 nên ta thu đưoc m®t b® so gom 12 so 1 và 4 so 0 Moi cách mua tương úng 1-
1 vói m®t cách lay 4 ví trí tù 16 v% trí đe viet 4 so 0 (còn lai viet so 1). Đáp so n 1 = C 4
2 Ta lay moi loai 2 gói, và mua tiep 2 gói theo cách trên se tương úng vói m®t b® 2 so 1 và 4 so 0. Đáp so n 2 = C 2
Bài 14.Có bao nhiêu cách bo 12 đong xu (như nhau) vào 7 phong bì có đánh so sao cho moi phong bì có ít nhat 1 đong xu.
Ta bo vào moi phong bì m®t đong xu, năm đong xu còn lai bo vào 7 phong bì theo quy tac sau:
Neu bo x 1 đong xu vào phong bì thú 1 ta viet x 1 so 1, sau đó ta viet so
0 Tương tn viet x 7 so 1 neu bo x 7 đong xu vào phong bì so 7 Moi cách tương úng vói m®t b® gom 5 so 1 (x 1 + x 2 + + x 7 = 5) và 6 so 0. Vắy đỏp so n = C 6
Bài 15 Có 30 ngưòi bo phieu cho 5 đai bieu, moi ngưòi chi bo phieu cho duy nhat m®t đai bieu Hoi có bao nhiêu cách bo phieu cna 30 ngưòi cho tat ca các đai bieu.
Neu có x 1 ngưòi bo phieu cho đai bieu thú 1 ta viet x 1 so 1 sau đó viet so 0.
Neu có x 2 ngưòi bo phieu cho đai bieu thú 2 ta viet x 2 so 1 sau đó viet so 0.
Khi bầu cử, nếu có 5 người bỏ phiếu cho đại biểu, mỗi cách bỏ phiếu tương ứng với một bộ 30 số 1 và 4 số 0 Do đó, cách bỏ phiếu sẽ được tính bằng C 4.
Bài 16 Có bao nhiêu cách bo 2 qua bóng trang, 7 bóng đen vào 9 lo khác nhau sao cho:
1 Không có lo nào trong.
1 Có C 2 cách cHQN 2 trong 9 lo đe bo bóng trang, còn lai bo bóng đen. Suy ra n 1 = C 2
2 Viet x 1 so 1 neu bo x 1 qua bóng trang vào lo thú 1, sau đó viet 0. Tương tn đen khi viet x 9 so 1 neu bo x 9 qua bóng trang vào lo thú
9 Vắy moi cỏch bo búng trang tương ỳng 1-1 vúi moi bđ 2 so 1 (x 1 +x 2 + +x 9 = 2) và 8 so 0.
Tương tn so cách bo bóng đen tương úng 1-1 vói m®t b® 7 so 1 và 8 so 0 bang n 2 = C 7
Theo quy tac nhân thì so cách bo bóng trang và bóng đen bang n = n 1 n 2 = C 2 C 7
Bài 17 Tìm so b® (x 1 , x 2 , x 3) nguyên không ân thoa mãn x 1 + x 2 + x 3
Moi b® (x 1 , x 2 , x 3) thoa mãn x 1 + x 2 + x 3 ≤ 1000 tương úng 1-1 vói b® (x 1 , x 2 , x 3 , x 4) thoa mãn x 1 + x 2 + x 3 + x 4 = 1000 Moi b® (x 1 , x 2 , x 3 , x 4) tương úng 1-1 vói b®:
4 x 1003! gom 1000 so 1 và 3 so 0 So b® này bang P (1000,
3) Bài 18 Xét bat phương trình x 1 + x 2 + x 3 + x 4 9
1 Tỡm so nghiắm nguyờn khụng õm.
2 Tỡm so nghiắm nguyờn dương.
1 So nghiắm khi x 1 + x 2 + x 3 + x 4 = 9 bang C 3 (3 so 0, 9 so 1). Khi x 1 + x 2 + x 3 + x 4 = 8 bang C 3
Tiep tuc như vắy, khi x 1 + x 2 + x 3 + x 4 = 1 bang C 3
Tiep tuc như vắy, khi x 1 + x 2 + x 3 + x 4 = 0 bang C 3 Đáp so: n = C 3 + C 3 + C 3 + + C 3
Phương pháp đánh so
Để cải thiện khả năng giải quyết bài toán phức tạp, chúng ta cần xây dựng phương pháp đánh giá hiệu quả Việc đánh giá các vị trí sẽ giúp sắp xếp các thành phần cần thiết theo thứ tự ưu tiên, từ đó xác định cách thức phù hợp với một bài toán nguyên dương, đáp ứng các yêu cầu cụ thể của bài toán.
Sau đây ta xét m®t so bài toán minh HQA:
Bài 19 M®t tő có 7 HQc sinh nam, 3 HQc sinh nu Hoi có bao nhiêu cách xep tő thành m®t hàng ngang mà không có 2 hQc sinh nu nào ngoi canh nhau.
Chúng ta đánh giá các vị trí từ 1 đến 10, trong đó có 3 vị trí không kề nhau tương ứng với các số a < b < c Điều kiện cần thỏa mãn là 3a + 2 < b + 1 < c 10 Để xác định các số a, b, c, chúng ta cần chọn ra 3 số phân biệt trong 8 số tự nhiên từ 1 đến 10.
C 3 cách cHQN ra 3 v% trí trong 10 v% trí đe xep các em nu.
Vắy so cỏch xep bang n = C 3 3!.7!
Bài 20 Có bao nhiêu cách xep 7 nam, 3 nu ngoi xung quanh m®t bàn tròn 10 ghe sao cho không có 2 em nu nào ngoi canh nhau.
Ta lay m®t chiec ghe bat kỳ và xep tiep theo m®t chiec.
- Trưòng hop 1: Xep em nu thì ghe thú 10 không the là nu:
Vắy ta can cHQN 2 v% trớ ỳng vúi cỏc so a, b đe xep 2 em nu Khi đó
(Vỡ ghe thỳ 2 khụng the xep nu) Vắy so cỏch cHQN thờm 2 v% trớ bang
2 (cHQN 2 so phõn biắt trong 6 so).
- Trưòng hop 2: Ghe đã cHQN xep em nam:
Khi đó 3 v% trí xep nu úng vói 3 so a < b < c thoa mãn 4 ≤ a + 2 < b + 1 < c ≤ 10
So cách cHQN 3 v% trí bang C 3 7
Sau khi chQn v% trí ta có 3! cách xep nu và 7! cách xep nam.
Vắy so cỏch xep bang: n = (C 2 + C 3 ).3!7!
Bài 21 Xột tắp A = 0, 1, 2, 3, 4, 5 Hoi cú the lắp đưoc bao nhiờu so cú bay chu so gom 5 chu so phõn biắt khỏc khụng cna A và 2 so
0 sao cho giua 2 so 0 có ít nhat 2 so khác 0.
Ta có 7 vị trí để xếp các chữ số cho một số Đánh số thứ tự các vị trí từ 1 đến 7 Ta chọn ra 2 vị trí để viết số 0 tương ứng với 2 số a, b thỏa mãn điều kiện 4a + 2 < b ≤ 7 (với a ≥ 2 vì số 0 không được đứng đầu) Vậy số cách chọn 2 vị trí bằng số cách chọn 2 số phân biệt trong 4 số từ 4 đến 7 Số cách chọn được tính bằng C(2) và tại các vị trí này ta viết số 0 Còn lại 5 vị trí có 5! cách xếp các số.
Bài 22.Xét đa giác đeu n đinh (n 12), hoi có bao nhiêu tam giác có 3 canh là 3 đưòng chéo Hoi có bao nhiêu tú giác có 2 canh là canh đa giác, 2 canh còn lai là 2 đưòng chéo.
- Xuat phát tù 1 đinh bat kỳ ta đánh so các đinh theo thú tn A 1 , A 2 , ,
A n Ta can cHQN thêm 2 đinh úng vói các so a, b thoa mãn 4 ≤ a + 1
Suy ra so cỏch cHQN 2 đinh bang so cỏch lay ra 2 so phõn biắt tự n − 4 so (tù 4 đen n − 1).
Suy ra so tam giác đinh A 1 thoa mãn yêu cau cna bài toán bang C 2
Vỡ cú n đinh và moi tam giỏc đưoc đem lắp lai 3 lan nờn so tam giỏc thoa nC 2 mãn yêu cau cna bài toán bang d n 3 − 4
Trong trường hợp của một tứ giác có hai cạnh là hai cạnh kề nhau của đa giác, với mỗi cặp hai cạnh kề nhau, chúng ta cần xác định thêm một đỉnh nhằm đảm bảo tính đồng nhất của hình dạng.
5 a n 1 Suy ra so cách cHQN thêm 1 đinh bang (n 5).
Váy so tỳ giỏc có 2 cạnh là 2 cạnh kề nhau của đa giác và 2 cạnh còn lại là đường chéo, với công thức tính là d = 1 = n(n - 5) Điều này xảy ra do có n cặp 2 cạnh đa giác kề liền nhau.
Trưòng hop có 2 canh là canh đa giác không ke nhau Muon có 2 canh cũn lai là hai đưũng chộo ta thnc hiắn như sau: Xuat phỏt tự m®t canh
M®t so phương pháp giai nâng cao cna bài toán đem
Nguyên lí bao gom và loai trù
Trong cuđc song nhieu khi xuat hiắn nhung bài toỏn phai tớnh so lưong cỏc phan tu cna mđt tắp hop thụng qua nhung tắp hop con cna chúng.
Neu A và B là hai tắp hop rũi nhau thỡ ta de dàng thay rang
Trong trưòng hop A và B có giao khác rong thì đang thúc trên không còn đúng nua.
Khi xột hai tập hợp A và B sao cho A và B không có phần tử chung (A ∩ B = ∅), số phần tử của hợp A ∪ B sẽ bằng tổng số phần tử của A và B Điều này có nghĩa là nếu chúng ta cộng số phần tử của A với số phần tử của B, thì số phần tử của hợp A ∪ B sẽ được tính hai lần.
Nhieu khi, bài toỏn ta gắp tro nờn phỳc tap hơn khi phai tớnh so phan tu cna mđt tắp hop cú nhieu hơn hai tắp hop.
Xột ba tập hợp A, B, C sao cho các giao của chúng là khác rỗng, tức là A ∩ B, A ∩ C, B ∩ C đều có phần tử Khi đó, các phần tử thuộc A ∩ B, A ∩ C, B ∩ C sẽ được tính hai lần, trong khi các phần tử thuộc A ∩ B ∩ C sẽ được tính ba lần Điều này dẫn đến một kết luận quan trọng trong lý thuyết tập hợp.
Trong nhiều trường hợp, chúng ta phải tính số phần tử của một tập hợp gồm nhiều tập hợp con, và việc phân chia các bài toán này thường rất khó khăn với học sinh, đặc biệt là khi họ chưa nắm được công thức tính tổ hợp Kết quả trên dẫn đến một định lý quan trọng: Cho các tập hợp A1, A2, , An, ta có
Sau đay ta xét m®t so bài toán minh HQA:
Bài 1.Trong m®t bài kiem tra Toán có hai bài toán Trong ca lóp có
Trong lớp có tổng cộng 30 học sinh làm được bài thú nhất và 20 học sinh làm được bài thú hai Chỉ có 10 học sinh làm được cả hai bài toán kiểm tra Hãy tính số học sinh trong lớp.
GQI A là tập hợp HQc giải được bài toán thứ nhất, trong khi B là tập hợp HQc giải được bài toán thứ hai Khi kết hợp A và B, ta có tập hợp HQc giải được cả hai bài toán Bài toán đặt ra là phải tính số phần tử của tập hợp A và B.
Vắy so HQc sinh trong lúp bang
Bài 2 Lóp 12A phai làm m®t bài kiem tra Toán gom có ba bài toán.
Biet rang moi em trong lóp đeu giai đưoc ít nhat m®t bài, trong lóp có
Trong lớp HQc, có tổng cộng 20 em giải được bài toán thứ nhất, 14 em giải được bài toán thứ hai, và 10 em giải được bài toán thứ ba Có 6 em giải được cả hai bài toán thứ nhất và thứ ba, 5 em giải được cả hai bài toán thứ hai và thứ ba, 2 em giải được cả hai bài toán thứ nhất và thứ hai, và 1 em đạt điểm 10 vì đã giải được cả ba bài toán Vậy tổng số học sinh trong lớp là bao nhiêu?
GQI A là tập hợp các em học sinh giải được bài toán thứ nhất, B là tập hợp các em học sinh giải được bài toán thứ hai, và C là tập hợp các em.
HQc sinh giai đưoc bài toỏn thỳ ba Ta phai tớnh so phan tu cna tắp hop
Vắy so HQc sinh trong lúp bang
Bài 3.Trong m®t kì thi HQc sinh gioi Toán, Lí, Hóa có m®t so em tham gia Biet rang có 20 em tham gia thi Toán, 14 em tham gia thi Lí, 10 em tham gia thi Hóa, 6 em vùa thi Toán vùa thi Lí, 5 em vùa thi Lí vùa thi Hóa, 2 em vùa thi Toán vùa thi Hóa và có 1 em tham gia tat ca ba môn Toán, Lí và Hóa Hoi rang có bao nhiêu em tham gia kì thi HQc sinh gioi này?
GQI A là tập hợp các em học sinh thi học sinh giỏi môn Toán, B là tập hợp các em học sinh thi học sinh giỏi môn Lý, và C là tập hợp các em học sinh thi học sinh giỏi môn Hóa Chúng ta cần tính số phần tử của các tập hợp A, B và C.
Vắy so HQc sinh tham gia kỡ thi HQc sinh gioi bang
Bài 4 Tính so các hoán v% cna dãy chu "XAXAM " sao cho không có hai chu cái nào giong nhau đúng canh nhau.
Tőng so các hoán v% cna chu "XAXAM" bang
Kớ hiắu M 1 là tắp cỏc hoỏn v% mà hai chu X đỳng canh nhau Khi đú ta coi hai chu X đúng canh nhau là m®t chu và ta có:
Kớ hiắu M 2 là tắp cỏc hoỏn v% mà hai chu A đỳng canh nhau Khi đú ta coi hai chu A đúng canh nhau là m®t chu và ta có:
Ta cú M 1 M 2 là tập hợp các hoán vị mà hai chữ A và hai chữ X đứng cạnh nhau Trong trường hợp này, ta coi hai chữ A là một chữ và hai chữ X là một chữ, từ đó hình thành các hoán vị mới.
Khi đó tőng so các hoán v% bang d − |M 1 ∪ M 2 | = d − (|M 1 | + |M 2 |) + |M 1 ∩ M 2 | = 30 − 24 + 6 = 12
Bài 5 Tính so các hoán v% cna chu "MAYMAN" sao cho không có hai chu cái nào giong nhau đúng canh nhau.
Tőng so các hoán v% cna chu "MAYMAN" bang
Kớ hiắu M 1 là tắp cỏc hoỏn v% mà hai chu M đỳng canh nhau Khi đú ta coi hai chu M đúng canh nhau là m®t chu và ta có:
Kớ hiắu M 2 là tắp cỏc hoỏn v% mà hai chu A đỳng canh nhau Khi đú ta coi hai chu A đúng canh nhau là m®t chu và ta có:
Ta có M1 và M2 là các hoán vị mà hai chữ A và hai chữ M đứng cạnh nhau Khi đó, hai chữ A được coi là một chữ và hai chữ M cũng được coi là một chữ, tạo thành một cấu trúc hoán vị mới.
Khi đó tőng so các hoán v% bang d − |M 1 ∪ M 2 | = d − (|M 1 | + |M 2 |) + |M 1 ∩ M 2 | = 180 − 120 + 24 84
Bài 6 Xét a = 1133322444 Hoi neu thay đői v% trí các chu so cna a thỡ nhắn đưoc bao nhiờu so mà hai so 1, hai so 2 khụng đỳng canh nhau.
Tat ca các cách thay đői v% trí bang d = 10!
Kớ hiắu M 1 là tắp cỏc so mà hai so 1 đỳng canh nhau Khi đú ta coi hai so 1 đúng canh nhau là m®t so và ta có:
Kớ hiắu M 2 là tắp cỏc so mà hai so 2 đỳng canh nhau Khi đú ta coi hai so 2 đúng canh nhau là m®t so và ta có:
Ta có thể hiểu rằng M1 và M2 là hai số mà chúng đứng cạnh nhau Trong trường hợp này, số 1 được coi là một số và số 2 là một số khác, từ đó ta có thể xác định mối quan hệ giữa chúng.
Khi đó so cách xep bang
Phương pháp truy hoi
Trong nhiều trường hợp, việc đem trực tiếp các đối tượng là rất khó khăn Nếu chúng ta thiết lập được mối quan hệ truy hồi giữa số lượng đối tượng cần đem trong nhóm n và số lượng đối tượng cần đem trong nhóm ít hơn n, thì có thể đưa ra so sánh đối tượng trong nhóm lớn với đối tượng nhỏ, mặc dù việc đem trong nhóm đối tượng nhỏ này có thể gặp khó khăn Nội dung cơ bản của phương pháp này là: thay vì đem trực tiếp f(n) theo yêu cầu bài toán, ta sẽ thiết lập mối quan hệ giữa f(n), f(n-1), để từ đó tính được f.
(n) Sau đây ta xét m®t so bài toán minh
Bài 1.Trờn mắt phang cho n đưũng thang d 1 , d 2 , d 3 , , d n (n “ 1) đụi m®t không song song và không có ba đưòng nào đong quy Tìm so mien mà n đưũng thang này đ%nh ra trờn mắt phang.
Gia số S(n) là số miền mà n đường thẳng đó tạo ra trên mặt phẳng Từ gia số ta có d1, d2, d3, , dn−1 tại n điểm Do đó, dn sẽ chia thành n phần còn lại Mỗi phần trong đó sinh ra một miền mới Do đó, S(n) = S(n1) + n.
Bài 2.(Bài toán tháp Hà N®i) Tương truyen rang tai m®t ngôi tháp o Hà Nđi cú mđt tam đe bang đong trờn đú cú đắt ba chiec CQc bang kim cương Lỳc khai thiờn lắp đ%a, trờn CQc so 1, Phắt tő Như Lai đó xep 64 chiec đĩa bang vàng có đưòng kính khác nhau sao cho các đĩa có đưòng kính lón hơn xep o dưói, các đĩa o phía trên càng o trên cao càng nho dan Các nhà sư đưoc yêu cau chuyen tat ca các đĩa o CQc so 1 sang CQc so 2 vói quy tac sau:
- Moi lan chi đưoc chuyen đi 1 chiec đĩa;
Trong quá trình di chuyển, không thể đặt đĩa lún lên đĩa nhỏ, do đó cần thiết phải có thêm chiếc CQc trung gian thứ 3 Giả sử mỗi lần di chuyển một chiếc đĩa mất 1 giây, câu hỏi đặt ra là các nhà sư cần ít nhất bao nhiêu năm để chuyển tất cả các đĩa từ CQc số 1 sang CQc số 2.
Gia sư lúc đau trên CQC số 1 có n chiếc đĩa GQI u n là số lần ít nhất để chuyển tất cả các đĩa từ CQC số 1 sang CQC số 2 Để tính toán một vài giá trị cận u n, với n = 2, ta cần thực hiện 3 phép chuyển.
- Chuyen đĩa bé sang CQc so 3.
- Chuyen đĩa lón sang CQc so 2.
- Chuyen đĩa bé tù CQc so 3 ve CQc so
Vúi n = 3, ta can thnc hiắn theo 3 giai đoan sau:
- Chuyen hai đĩa o phía trên sang CQc so 3 Như đã thay o trưòng hop n = 2, ta can 3 phép chuyen.
- Chuyen đĩa lón nhat sang CQc so 2.
- Chuyen hai đĩa o CQc so 3 ve cQc so 2 Như đã thay o trưòng hop n = 2 ta can 3 phép chuyen.
Vắy ta can 3 + 1 + 3 = 7 phộp chuyen Do đú u 3 = 7.
Để thiết lập hệ thống truy hồi với n = 3, cần đảm bảo rằng các điều kiện (u n) được thỏa mãn Để chuyển được n chiếc đĩa theo quy tắc đã đề ra, cần thực hiện theo ba bước cụ thể.
Trong công đoạn 1, chúng ta chuyển n−1 chiếc đĩa từ đĩa lớn nhất ở cọc số 1 sang cọc số 3 theo quy tắc đã định Quá trình này yêu cầu thực hiện n−1 phép chuyển Đĩa lớn nhất vẫn giữ nguyên vị trí tại cọc số 1 trong khi chúng ta thực hiện việc di chuyển n−1 chiếc đĩa ở trên nó.
- Công đoan 2: Chuyen đĩa lón nhat sang CQc so 2;
Để chuyển n - 1 chiếc đĩa từ CQc số 3 về CQc số 2 và đặt lên chiếc đĩa lớn nhất, cần thực hiện u(n - 1) phép chuyển Do đó, để chuyển n chiếc đĩa từ CQc số 1 sang CQc số 2, ta cần thực hiện tổng cộng u(n - 1) + 1 + u(n - 1) phép chuyển.
= 2u n−1 + 1 phộp chuyen Vắy ta cú hắ thỳc truy hoi sau u n = 2u n−1 + 1
Tự hắ thỳc truy hoi này ta cú the lắp đưoc cụng thỳc cna so hang tőng quát cna dãy Bang quy nap ta chúng minh đưoc u n = 2 n − 1
Khi có 64 đĩa, số lần di chuyển cần thiết để hoàn thành công việc là 2^64 - 1 Nếu mỗi lần di chuyển mất 1 giây, các nhà sư sẽ cần hơn 500 tỷ năm để chuyển 64 chiếc đĩa từ cột số 1 sang cột số 2.
Bài 3.(IMO 1979, bài so 6) Gia su A và E là hai đinh đoi diắn cna m®t bát giác đeu M®t con ech bat đau nhay tù đinh A Tai moi đinh cna bát giác (trù đinh E), moi cú nhay con ech chi có the nhay tói hai đinh ke vói đinh đó Khi con ech nhay vào đinh E, nó se b% ket vĩnh vien o đó Cho trưóc so nguyên dương n Hoi vói n cú nhay, có bao nhiêu cách đe con ech nhay vào đinh E.?
GQI a n là so cách con ech nhay vào đinh E ta thay a 1 = a 2 a 3 = 0; a 4 = 2
Gia su tù A theo chieu kim đong ho, các đinh lan lưot là
Để con ếch đen A nhảy đến E, nó phải vượt qua một số bước lẻ từ B, C, và D Nếu số bước từ A đến E là số chẵn, thì không có cách nào để con ếch nhảy đến E Do đó, khi a_{2k-1} = 0, chúng ta cần tính toán a_{2k}, với k là số nguyên dương.
Xuat phát tù A, vói hai bưóc nhay đau tiên, con ech có the có các cách sau:
Neu theo cách 1) thì so cách tói E là a 2k−2 Neu theo cách 2) thì so cách tói E là a 2k−2.
GQI c n và g n lan lưot được xác định bằng số cách để con ếch xuất phát từ C, G nhảy vào đỉnh E Do đó, ta có c n = g n Nếu sử dụng cách 3), số cách tới E là c 2k−2, trong khi nếu áp dụng cách 4), số cách tới E là g 2k−2.
Vắy theo quy tac cđng ta cú a 2k = a 2k−2 + a 2k−2 + c 2k−2 + g 2k−2 = 2a 2k−2 + 2c 2k−2 (1)
Xuat phát tù C, vói hai bưóc nhay đau tiên, con ech có the có các cách sau:
Neu theo cách 1c) thì so cách tói E là a 2k−2 Neu theo cách 2c) thì so cách tói E là c 2k−2 Neu theo cách 3c) thì so cách tói
E là c 2k−2 Neu theo cách 4c) thì so cách tói E là 0.
Theo quy tac c®ng ta có c 2k = a 2k−2 + 2c 2k−2 (2)
Tù (1) và (2) rút ra c 2k = a 2k a 2k−2 hay c 2k−2 = a 2k−2 a 2k−4 Thay vào (1) ta đưoc Đắt u k = a 2k ta cú a 2k = 4a 2k−2 − 2a 2k−4 u k = 4u k−1 − 2u k−2 , u 1 = a 2 = 0, u 2 = a 4 = 2.
Bang cỏch giai phương trỡnh đắc trưng ta đi đen cụng thỳc sau
M®t so dang bài toán to hap liên quan đen bài toán đem
Nguyên lí bat bien
Bat bien đơn điắu
Đại lượng bất biến trong toán học là một thuộc tính không thay đổi khi hệ thống tác động biến đổi Tuy nhiên, khi hệ thống thay đổi mà có đại lượng biến đổi theo một quy luật nhất định, điều này sẽ ảnh hưởng đến các đại lượng khác Ví dụ, nếu một đại lượng luôn tăng hoặc luôn giảm, thì các đại lượng liên quan cũng sẽ có sự thay đổi tương ứng Trong trường hợp này, đại lượng bất biến đơn điệu sẽ giúp xác định sự tác động của các biến trong bài toán Chính những đại lượng bất biến đơn điệu này dẫn dắt chúng ta đến giải quyết bài toán một cách hiệu quả.
Bài 17 Moi ụ trong bang m x n đưoc viet mđt so thnc Ta thnc hiắn bien đői dau mđt lan cỏc so trờn mđt hàng hoắc mđt cđt bat kỡ Chỳng minh rang bang thao tác như trên, ta có the đưa đen trong MQI hàng và trong MQI c®t tőng các so cna nó là m®t so không âm.
Bài giải đề xuất rằng tổng các số trong bảng sẽ thay đổi tùy thuộc vào các phép toán được thực hiện Nếu tổng các số trong một phép toán là số âm, tổng này sẽ tăng lên; nếu tổng là số dương, tổng sẽ giảm; và tổng sẽ không thay đổi nếu các phép toán không làm thay đổi giá trị Điều này có nghĩa là nếu trong bảng có một phép toán mà tổng các số là một giá trị âm, thì phép toán cho phép trên sẽ làm tăng tổng tất cả các số trong bảng.
Tổng của tất cả các số trong bảng không thể tăng lên vô hạn do những thao tác làm tăng tổng chỉ có giới hạn, tức là chỉ có giới hạn nhất định cho các bảng khác nhau Do đó, mỗi số trong một bảng sẽ là tổng số của các số khác trong bảng đó Vì vậy, số lượng các bảng khác nhau không thể vượt quá 2 m/n, nghĩa là tổng của tất cả các số trong bảng chỉ có thể đạt được giới hạn nhất định với giá trị khác nhau.
Ta xột bảng ban đầu và chọn trong đó những vế có tổng các số là âm Nếu không có vế nào như vậy thì bài toán được giải Ta tiếp tục xác định phép biến đổi trên vế này Trong bảng, nếu tìm thấy những vế có tổng các số là âm, ta lại tiếp tục xác định phép biến đổi trên nó và nhấn được bảng mới Mỗi lần thực hiện phép biến đổi, tổng các số trong bảng tăng lên Tổng này chỉ có thể là hữu hạn, do đó, tại một bước thực hiện nào đó, ta phải nhấn được bảng cân tầm, hoặc là sum hay min, ta cũng nhấn được bằng vế khả năng tổng các số đại Với tính chất như vậy, ta phải tìm được vế vì nếu còn một vế vế tổng âm nào tồn tại trong nó thì ta lại tiếp tục thực hiện một lần nữa phép biến đổi Khi đó, tổng các số trong bảng mới này tăng lên và lớn hơn tổng các số trong bảng cũ, điều này vô lý.
Bài 18 Trờn mđt đưũng trũn ta đắt n so Neu thỳ tn cỏc so a, b, c, d thoa mãn (a d)(b c) > 0, thì hai so b và c đői cho cho nhau Chúng minh rang sau m®t so bưóc thì trên đưòng tròn không còn b® tú nào sap xep như vắy.
Phép biến đổi trong bài toán này liên quan đến việc thay đổi hai số trên đường tròn trong khi giữ nguyên các số khác Chúng ta cần tìm đại lượng bất biến liên quan đến sự thay đổi này Đặt a, b, c, d sao cho (a d)(b c) > 0, tức là ab + cd > ac + bd Nếu thực hiện phép biến đổi đã cho, ta có thể chuyển từ a, b, c, d thành a, c, b, d Kết quả là tổng các tích của các số cạnh nhau sẽ giảm, dẫn đến ab + bc + cd > ac + cb + bd.
Đai lượng bất biến đơn điệu là tổng hợp các số kế nhau liên tiếp trên đường tròn Với phép biến đổi đã cho, đai lượng này giảm thành phần sản, và vì vậy chỉ có giá trị hữu hạn.
% nờn phộp bien đői cna ta chi cú the thnc hiắn huu han lan Vắy sau m®t so bưóc thì trên đưòng tròn không còn b® nào sap xep như vắy.
Bài 19 2000 ngưòi đưoc chia vào các phòng cna m®t tòa nhà 115 buong.
Mỗi phút không ai phai MQI, nhưng có một số người đi vào phòng ít người, trong khi phòng có nhiều người hơn Chúng tôi nhận ra rằng vào những lúc đó, tất cả MQI người đều tập trung tại một phòng.
Bài toán được giải nhằm tìm ra bất biến đơn điệu Vui mời quý vị xem xét biến phương căn số ngũi trong phòng Ký hiệu tổng căn các số bình phương này là S Ta chỉ ra rằng S tăng với mỗi người được chuyển đi Thật vậy, giả sử một người đi từ phòng có n người tới phòng có m người mà m > n Khi đó, những số bình phương căn số người trong các phòng này biến đổi từ n^2 và m^2 thành (n + 1)^2 và (m - 1)^2 tương ứng, và các phòng khác thì không đổi Như vậy, S thay đổi như sau:
Tồn tại một số lượng người là 2000, không thể chia đều vào các phòng khác nhau mãi mãi, dẫn đến khả năng giá trị S không thể tăng liên tục Quy trình này cho thấy rằng giá trị S sẽ tăng lên, nhưng cuối cùng sẽ dừng lại và không tăng nữa, lúc đó tất cả mọi người sẽ tập trung trong một phòng.
Bài 20 Cho bon so a, b, c, d không phai tat ca bang nhau Khoi đau bang bđ (a, b, c, d) và lắp lai viắc thay the (a, b, c, d) bang (a b, b c, c d, d a) Chỳng minh rang khi lắp lai nhieu lan viắc thay the trờn thì ít nhat m®t trong bon so se tro thành vô cùng lón.
Ta có điểm P n = (a n , b n , c n , d n ) là bốn số sau n phép lắp Khi đó, ta có a n + b n + c n + d n = 0 với n ≥ 2 Ta liên tưởng tới hình học, hàm khoảng cách từ điểm P n đến điểm gốc TQA (0, 0, 0, 0) được liên hệ với biểu thức a² + b² + c² + d² Nếu ta chứng minh được biểu thức trên không âm thì bài toán sẽ được giải.
Ta đi tỡm moi liờn hắ giua hai bưúc liờn tiep P n và P n+1.
Bây giò ta su dung a n + b n + c n + d n 0 0 = (a n + b n + c n + d n ) 2
C®ng (1) vói (2) theo ve ta đưoc: a 2 + b 2 + c 2 + d 2 = 2(a 2 + b 2 + c 2 + d 2 )+(a n + c n ) 2 +(b n + d n ) 2 “
Tự moi quan hắ bat bien này ta đưa đen ket luắn vúi n “ 2 a 2 + b 2 + c 2 + d 2 “ 2 n−1 (a 2 + b 2 + c 2 + d 2 )
Khoang cách tù điem P n đen điem goc TQA đ® tăng vô han, nghĩa là ít nhat có m®t thành phan phai tro lên lón bat kì.
Hàm khoang cách tù m®t điem đen điem goc TQA đ® rat quan TRQNG, khi nào có m®t dãy điem ta phai nghĩ ngay tói hàm này.
Bài 21 Moi so trong cỏc so a 1 , a 2 , a 3 , , a n là +1 hoắc −1 và ta cú
Chúng minh rang n chia het cho 4.
Bài toán này có thể giải bằng biến đổi, với điều kiện nếu thay một số trong bốn số hàng cạnh nhau theo vòng tròn, tổng S sẽ không thay đổi Cụ thể, nếu thay đổi đầu vào của a1, bốn số hàng cạnh nhau sẽ là a1, a2, a3, a4, và tiếp tục theo chu kỳ Nếu hai trong số bốn số hàng cạnh nhau là dương và hai là âm, tổng S cũng không thay đổi Tuy nhiên, nếu ba số hàng có cùng dấu, tổng S sẽ tăng hoặc giảm 4, tùy thuộc vào sự phân bố của các số dương và âm.
Nếu tất cả bốn số hạng cùng dấu, thì tổng S sẽ tăng hoặc giảm 8 Cụ thể, nếu tất cả các số hạng đều dương, tổng S sẽ giảm 8, trong khi nếu tất cả các số hạng đều âm, tổng S sẽ tăng lên 8.
M®t so bài toán nâng cao
Bài 22 M®t tò giay đưoc xé thành năm manh, m®t so trong so năm manh nho này lai đưoc xé thành năm manh nho nua, và m®t so trong so năm manh nho này lai đưoc xé tiep thành năm manh , Vắy neu cỳ tiep tuc xộ như vắy thỡ cú khi nào ta đưoc 2002 manh giay hay không? Đưoc 2005 manh giay không?
Khi chia một tờ giấy thành 5 mảnh và tiếp tục chia mỗi mảnh thành 5 mảnh nhỏ hơn, số mảnh giấy sẽ tăng thêm 4 mỗi lần xé Do đó, số mảnh giấy sau mỗi lần xé có dạng 4k + 1, với k là một số nguyên không âm Biểu thức này cho thấy sự biến đổi liên tục trong quá trình xé giấy.
Vì 2002 = 4k + 1, nên không the xé đưoc 2002 manh.
2005 = 501.4+1 nên có the xé đưoc thành 2005 manh sau lan xé thú 501.
Bài 23 Tai đinh A 1 cna m®t đa giác đeu 12 đinh đánh dau trù (-) cũn tat ca cỏc đinh cũn lai đỏnh dau cđng (+) Mđt bưúc thnc hiắn là đői đong thói ba dau tai ba đinh liên tiep thành dau ngưoc lai Chúng minh rang khụng cú kha năng sau mđt so huu han bưúc thnc hiắn như trờn se nhắn đưoc A 2 cú dau trự (-) cũn tat ca cỏc đinh cũn lai mang dau c®ng (+).
Ta chía các đinh cna đa giác đeu 12 canh ra làm ba nhóm
Khi các đỉnh trong đồ thị liên tiếp thay đổi, mỗi đỉnh sẽ thuộc về một nhóm nhất định Sau mỗi lần đổi đầu tại các đỉnh liên tiếp, số lượng đỉnh trù trong mỗi nhóm sẽ tăng hoặc giảm Điều này dẫn đến việc số lượng đỉnh trù trong nhóm hai và nhóm ba luôn có tính chất chẵn lẻ Khi bắt đầu trò chơi, số lượng đỉnh trù bằng không Sau lần đổi đầu tiên, mỗi nhóm sẽ có một đỉnh trù; sau lần đổi thứ hai, mỗi nhóm sẽ có 0 hoặc 2 đỉnh trù; và sau lần đổi thứ ba, số lượng đỉnh trù sẽ là 1 hoặc 3 Do đó, không thể đạt được kết quả cuối cùng là A2 có đỉnh trù, trong khi tất cả các đỉnh còn lại mang đỉnh trù, vì lúc đó số đỉnh trù trong nhóm hai là 1 và trong nhóm ba là 0.
Bài 24 Cho m®t bang hình vuông ke ô 10 x 10 và trong moi ô ta ghi theo thú tn m®t so tn nhiên gom tù so 1 đen so 100 Hàng thú nhat ghi tù 1 đen 10, hàng thú hai ghi tù 11 đen 20, Chúng minh rang tőng S cna 10 so bat kì cna bang trong đó không có bat kì hai so nào thu®c cùng m®t hàng và không có bat kì hai so nào thu®c cùng m®t c®t là m®t so không đői Tìm so S.
Ta kớ hiắu so hang cna tőng S:
Trong đó các so tn nhiên a 1 , a 2 , , a 10 bao gom giua 1 và 10, và nhung so này đôi m®t khác nhau, vì neu ta có a 1 = a 2 thì hai so a 1 và
10 + a 2 phai nam trong cùng m®t c®t cna bang Ta có:
Boi vỡ cỏc số a1, a2, , a10 là những số tự nhiên khác nhau từ 1 đến 10, với mỗi số chỉ xuất hiện một lần trong tổng a1 + a2 + + a10 Tổng các số này là 1 + 2 + + 10 = 55 Do đó, S = 450 + 55 = 505, là đại lượng không biến đổi với MQI qua cách cộng tổng các số trong bảng.
Bài 25 Cho khoi lắp phương tao boi 27 khoi lắp phương nho bang nhau Trong moi khoi lắp phương nho cú chỳa mđt so +1 hoắc
1 (hai khoi nho GQI là canh nhau neu chỳng cú chung mđt mắt) Ta
GQI "mắt cat" là những khối lắp phương nhỏ nằm cạnh nhau và nằm trong mđt "mắt phang" Cụ thể, sự thay đổi đầu đông thũi trong hai mắt cat có chung khối lắp phương nhỏ, nhưng không thay đổi đầu những khối lắp phương nhỏ chung Bản đầu trong tất cả các khối nhỏ có chứa số 1 Hỏi có thể sau một số bước thay đổi đầu như trên thì các khối nhỏ ổn định các khối lắp phương mang 1, còn những khối nhỏ còn lại đều mang +1 được không?
Số lượng các số 1 trong hệ thống lắp phương không thay đổi sau mỗi bước biến đổi Ban đầu, số lượng số 1 là 27, nhưng nếu muốn giảm còn 8 số 1, điều này là không thể xảy ra Trong quá trình biến đổi, nếu có một số 1 trong số 12 số, thì số lượng số 1 sẽ tăng thêm, dẫn đến sự thay đổi không mong muốn trong tổng số.
Bài 26 Cho khoi lắp phương bao gom 27 khoi lắp phương nho bang nhau Trong nhung khoi lắp phương nho cna khoi lắp phương chỳa nhung so +1 M®t bưóc bien đői ta có the thêm cùng m®t so vào hai khoi lắp phương nho bờn canh nhau (hai khoi nho cú chung mắt). Hoi tự khoi lắp phương đó cho cú the nhắn đưoc khoi lắp phương sao cho trong tat ca cỏc khoi lắp phương nho cú 0, cũn khoi nho o TRQNG tõm cú +1;
Ta có khối nhớ màu trắng và khối nhớ màu đen, trong đó khối nhớ trắng bên cạnh sẽ là khối nhớ đen, và ngược lại Khi đó, mỗi khối nhớ sẽ có màu trắng hoặc đen, với khối nhớ trắng luôn kèm theo khối nhớ đen bên cạnh và ngược lại Đặt P_t là tổng các số trong các khối nhớ trắng, và P_d là tổng các số trong các khối nhớ đen Biểu thức P = P_t - P_d không thay đổi với các thao tác đã cho.
Khi ta thêm cùng một mức so vào hai khối nhớ cạnh nhau, cả P t và P d đều gia tăng đồng đều Ban đầu, P = 1; nếu khối nhớ ở tâm là đen, thì P sẽ là 14 13 Khối lắp phương cần được thực hiện theo yêu cầu của bài toán.
P = 0 1 = 1 Đõy là đieu vụ lớ Vắy khụng the nhắn đưoc khoi lắp phương như yêu cau cna bài toán.