Đếm số cách sắp xếp 9 viên bi gồm 2 bi xanh, 3 bi đỏ và 4 bi vàng vào 3 túi a, b,c
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây [5.03 MB, 104 trang ]
ĐẠI HỌC QUẢNG NGÃI
BỘ ĐỀ
TOÁN RỜI RẠC
Dùng cho sinh viên khoa Công nghệ thông tin
và cho thí sinh luyện thi cao học ngành Khoa học máy tính
Biên soạn: BÙI TẤN NGỌC
- 10/2011 -
Toán rời rạc - Tài liệu dùng để luyện thi cao học ngành Khoa học máy tính
ấn Ngọc 1
Bài toán đếm
Bài 1. Đếm số n gồm 2 chữ số, nếu:
a. n chẵn
Gọi AB là số thỏa mãn yêu cầu
Vậy A có 9 cách chọn {1, 2, 3, 4, 5, 6, 7, 8, 9}
[không chọn 0, vì chọn 0 thì số này có 1 chữ số]
B có 5 cách chọn {0, 2, 4, 6, 8}
Theo nguyên lý nhân, ta có : 9 x 5 = 45 số
b. n lẻ gồm 2 chữ số khác nhau
Gọi AB là số thỏa mãn yêu cầu
Vì là số lẻ, nên B có 5 cách chọn {1, 3, 5, 7, 9}
Sau khi ta chọn B, thì A có 8 cách chọn
Theo nguyên lý nhân, ta có : 5 x 8 = 40 số
c. n chẵn gồm 2 chữ số khác nhau
Gọi AB là số thỏa mãn yêu cầu
Khi B = {0}. A có 9 cách chọn {1, 2, 3, 4, 5, 6, 7, 8, 9}
Số cách chọn trong trường hợp này là : 9 cách
Khi B = {2, 4, 6, 8}. A có 8 cách chọn
Số cách chọn trong trường hợp này là : 4 x 8 = 32 cách
Theo nguyên lý cộng, ta có : 9 + 32 = 41 số
Cách khác:
Theo câu a ta có 45 số n chẵn. Ta có 4 chữ số chẵn gồm 2 chữ số giống
nhau: 22, 44, 66, 88. => 45 – 4 = 41 số n chẵn gồm 2 chữ số khác nhau.
: {0, 1, 2, 3, 4, 5}
a.
abc
a {1, 2, 3, 4, 5}.
Toán rời rạc - Tài liệu dùng để luyện thi cao học ngành Khoa học máy tính
ấn Ngọc 2
a xong, b a]
Sau k a, b c a, b]
b.
abc
c : {0, 2, 4}.
+ Khi c a b như sau:
c =0, a {1, 2, 3, 4, 5}.
a, c b
+ Khi c c a b như sau:
c, a c
a, c b c a]
Bài 3. Có bao nhiêu xâu khác nhau có thể lập được từ các chữ cái trong từ
MISSISSIPI, COMPUTER yêu cầu phải dùng tất cả các chữ?
Từ MISSISSIPI có chứa : 1 từ M, 4 từ I, 4 từ S và 1 từ P
Số xâu khác nhau là :
!1!.4!.4!.1
!10
Xâu COMPUTER , nên lập được 8! xâu.
Toán rời rạc - Tài liệu dùng để luyện thi cao học ngành Khoa học máy tính
ấn Ngọc 3
Bài 4. Có bao nhiêu xâu nhị phân độ dài 8 không chứa 6 số 0 liền?
Gọi A là số xâu nhị phân độ dài 8 có chứa 6 số 0 liền nhau.
B là số xâu nhị phân độ dài 8.
=> Số xâu cần đếm là :
][][][ ANBNAN
N[B] = 2.2.2.2.2.2.2.2 =2
8
= 256.
N[A] = 10
[00x, 11x, 1x1, x11, x10 ,1x0, 10x, x01,0x1, 01x : x=000000]
Vậy số xâu cần đếm là : 256 – 10 = 246
Bài 5. Đếm số byte
a. Bất kỳ
Số byte là một dãy số có dạng: xxxxxxxx, x có 2 cách chọn 0 hoặc 1.
Theo nguyên lý nhân ta có : 2.2.2.2.2.2.2.2 = 2
8
= 256
b. Có đúng hai bít 0.
Có nghĩa là chuỗi luôn có 2 bit 0 và các bit còn lại là 1.
Bài toán này tương đương với tính số cách sắp xếp các xâu từ: 00111111
Đây là hoán vị lặp của 8 phần tử với 2 loại: 2 số 0 và 6 số 1.
8!/2!.6! = 7.8/2 = 28 xâu
c. Có ít nhất 2 bit 0
= Số xâu bất kỳ [a] – Số xâu không có bit 0 - Số xâu có 1 bit 0
Số xâu không có bit 0 = 1 trường hợp [11111111]
Số xâu có 1 bit 0 = 8!/1!7!= 8
256 – 1 – 8 = 247
d. Bắt đầu 00 và kết thúc 00
Xâu này có dạng : 00xxxx00
Theo nguyên lí nhân, ta có : 1. 2.2.2.2 = 2
4
= 16
e. Bắt đầu 11 và kết thúc không phải 11
Tốn rời rạc - Tài liệu dùng để luyện thi cao học ngành Khoa học máy tính
ấn Ngọc 4
Gọi A là số xâu bắt đầu 11, có dạng 11xxxxxx
Theo ngun lý nhân, ta có : A= 1.1.2.2.2.2.2.2 = 2
6
= 64
Gọi B là số xâu bắt đầu là 11 và kết thúc là 11, có dạng 11xxxx11
Theo ngun lý nhân, ta có : B= 1.1.2.2.2.2.1.1 = 2
4
= 16
Gọi C là số xâu bắt đầu 11 và kết thúc khơng phải 11
=> C = A – B = 64 – 16 = 48
Bài 6.
a. Mật khẩu máy tính gồm 1 chữ cái và 3 hoặc 4 chữ số. Tính số mật khẩu tối đa
có thể.
Dãy gồm 1 chữ cái và 3 chữ số có dạng: LNNN, NLNN, NNLN, NNNL
Trong đó L là chữ cái có 26 cách chọn và mỗi N là chữ số có 10 cách chọn.
Vì vậy theo ngun lý nhân, ta có : 4 × 26 × 10 × 10 × 10 = 104000.
Tương tự dãy có 1 chữ cái và 4 chữ số : 5 × 26 × 10 × 10 × 10 × 10 = 1300000.
Theo ngun lý cộng, ta có: 104000+ 1300000 = 1404000 [mật khẩu].
b. Như trên nhưng khơng lặp chữ số
Số mật khẩu gồm 1 chữ cái và 3 chữ số = 4 × 26 × 10 × 9 × 8 = 74880
Số mật khẩu gồm 1 chữ cái và 4 chữ số = 5 × 26 × 10 × 9 × 8 × 7 = 655200
Theo ngun lý cộng, ta có: 74880 + 655200 = 730080 [mật khẩu].
Bài 7.
Đội bóng đá ACB có 20 cầu thủ. Cần chọn ra 11 cầu thủ, phân vào 11 vò trí trên
sân để thi đấu chính thức. Hỏi có mấy cách chọn nếu :
a. Ai cũng có thể chơi ở bất cứ vò trí nào ?
Chọn ra 11 cầu thủ trong 20 cầu thủ , xếp vào 11 vò trí trên sân. Số cách
chọn bằng chỉnh hợp không lặp chập 11 của 20 phần tử :
0006704425728
!9
!20
]!1120[
!20
]![
!
kn
n
A
k
n
cách.
b. Chỉ có một cầu thủ được chỉ đònh làm thủ môn, các cầu thủ khác chơi ở vò trí
nào cũng được ?
Tốn rời rạc - Tài liệu dùng để luyện thi cao học ngành Khoa học máy tính
ấn Ngọc 5
Một cầu thủ đã chỉ đònh làm thủ môn, vậy ta cần chọn ra 10 cầu thủ trong 19 cầu
thủ còn lại xếp vào 10 vò trí. Số cách chọn bằng chỉnh hợp không lặp chập 10
của 19 phần tử :
003352212864
!9
!19
]!1019[
!19
]![
!
kn
n
A
k
n
cách.
c. Có 3 cầu thủ chỉ có thể làm thủ môn được, các cầu thủ khác chơi ở vò trí nào
cũng được ?
Có 3 cách chọn 1 cầu thủ để làm thủ môn từ 3 cầu thủ. Sau khi ta chọn thủ môn
xong, kế đến chọn 10 cầu thủ trong 17 cầu thủ còn lại để xếp vào 10 vò trí, có:
07057290240
!7
!17
]!1017[
!17
]![
!
kn
n
A
k
n
cách
Theo nguyên lý nhân, ta có: 3
07057290240
= 211718707200 cách.
Bài 8. Có 8 người đi vào 1 thang máy của một tòa nhà 13 tầng. Hỏi có bao nhiêu
cách để :
a. Mỗi người đi vào 1 tầng khác nhau.
Số cách đi vào 8 tầng khác nhau của 8 người này là số cách chọn 8 trong số 13
tầng khác nhau [mỗi tầng được đánh số từ 1 đến 13]. Đó là số chỉnh hợp không
lặp chập 8 của 13 phần tử:
51891840
!5
!13
]!813[
!13
]![
!
kn
n
A
k
n
b. 8 người này, mỗi người đi vào 1 tầng bất kì nào đó.
Mỗi người có 13 cách lựa chọn từ tầng 1 đến 13. Mà có 8 người. Vậy số cách
chọn là 8
13
.
Bài 9. Có bao nhiêu xâu có độ dài 10 được tạo từ tập {a, b, c} thỏa mãn ít nhất 1
trong 2 điều kiện:
- Chứa đúng 3 chữ a & chúng phải đứng cạnh nhau
- Chứa đúng 4 chữ b & chúng phải đứng cạnh nhau
Gọi A là số xâu có độ dài 10 có chứa đúng 3 chữ a đứng cạnh nhau.
B là số xâu có độ dài 10 có chứa đúng 4 chữ b đứng cạnh nhau.
Như vậy: A B là số xâu mà ta phải tìm.
Toán rời rạc - Tài liệu dùng để luyện thi cao học ngành Khoa học máy tính
ấn Ngọc 6
Theo nguyên lý bù trừ, ta có: N[AUB] = N[A] + N[B] - N[A∩B]
Ta tính N[A] như sau:
Xét trường hợp aaa ở đầu: aaaX
1
X
2
X
3
X
4
X
5
X
6
X
7.
- X
i
[i=1 7] chỉ có 2 giá trị là b, c, vậy số trường hợp đối với 7 ký tự này
giống như xâu nhị phân có độ dài 7, hay bằng 2
7
trường hợp.
- Xâu aaa, có thể được xếp vào 8 vị trí [aaaX
1
X
2
X
3
X
4
X
5
X
6
X
7,
X
1
aaaX
2
X
3
X
4
X
5
X
6
X
7
, X
1
X
2
aaaX
3
X
4
X
5
X
6
X
7
, X
1
X
2
X
3
aaaX
4
X
5
X
6
X
7
,
X
1
X
2
X
3
X
4
aaaX
5
X
6
X
7
X
1
X
2
X
3
X
4
X
5
aaaX
6
X
7
, X
1
X
2
X
3
X
4
X
5
X
6
aaaX
7
,
X
1
X
2
X
3
X
4
X
5
X
6
X
7
aaa]. Vì vậy: N[A] = 8.2
7
+ Tương tự, số lượng xâu có 4 chữ b đứng cạnh nhau, N[B] = 7.2
6
+ N[A∩B] được tính bằng cách gộp aaa = X, bbbb = Y, còn lại là 3 chữ c.
Ta tính số xâu từ dãy: XcccY có: 5!/1!3!1! = 4.5 = 20 trường hợp.
Vậy số xâu cần tính là: 8.2
7
+ 7.2
6
- 20 = 2476.
Bài 10. [Đề thi cao học ĐH CNTT TP HCM-2010]
Xét biển số xe: A
1
A
2
A
3
N
1
N
2
N
3
N
4
N
5
N
6
A
i
[i=1 3]: A->Z; N
j
[j=1 6]: 0->9
a. Hỏi có bao nhiêu biển số khác nhau?
b. Hỏi có bao nhiêu biển số thỏa điều kiện: ba mẫu tự khác nhau đôi một và
trong biển số có đúng 1 chữ số 3 và 1 chữ số 5?
c. Hỏi có bao nhiêu biển số thỏa điều kiện: trong biển số có ít nhất 1 chữ số 3 và
1 chữ số 5?
a. A
i
[i=1 3] có 26 cách chọn từ 26 chữ cái tiếng Anh từ A Z
N
j
[j=1 6] có 10 cách chọn từ 10 chữ số từ 0 9
Theo nguyên lý nhân ta có: 26.26.26.10.10.10.10.10.10 = 26
3
.10
6
biển số.
b. Số cách chọn 3 mẫu tự A
1
A
2
A
3
khác nhau: A1 có 26, A2 có 25, A3 có 24
cách.
Số cách chọn 4 chữ số N
1
N
2
N
3
N
4
không có số 3 và số 5: 8.8.8.8 = 8
4
cách.
Số cách đặt số 3 vào dãy 4 chữ số N
1
N
2
N
3
N
4
là 5 cách, đó là: 3N
1
N
2
N
3
N
4
,
N
1
3N
2
N
3
N
4
, N
1
N
2
3N
3
N
4
, N
1
N
2
N
3
3N
4
, N
1
N
2
N
3
N
4
3.
Toán rời rạc - Tài liệu dùng để luyện thi cao học ngành Khoa học máy tính
ấn Ngọc 7
Tương tự số cách đặt số 5 vào 5 dãy có 5 chữ số đã liệt kê ở trên là : 5.6=30
Theo nguyên lý nhân, ta có : 24. 8
4
.30 cách.
c. Gọi A là số biển số không có chứa chữ số 3 và chữ số 5.
N
A
= 26
3
.8
6
biển số
Gọi B là số là số biển số có chứa chữ số 3 và không có chứa chữ số 5.
N
B
= 26
3
.9
6
biển số
Gọi C là số là số biển số có không chứa chữ số 3 và có chứa chữ số 5.
N
C
= 26
3
.9
6
biển số
Gọi D số biển số có ít nhất 1 chữ số 3 và 1 chữ số 5
N
D
= N – N
A
– N
B
- N
C
Theo câu a: N= 26
3
.10
6
= 26
3
.10
6
- 26
3
.9
6
- 26
3
.9
6
- 26
3
.8
6
= 26
3
[10
6
– 2.9
6
- 8
6
].
Bài 11.
a. Có bao nhiêu số có n chữ số mà có m chữ số đầu và m chữ số cuối tương ứng
giống nhau. [n>2m>2, n,m N].
Gọi A dãy số cần tìm, A có dạng:
Số cách chọn m chữ số đầu tiên và m chữ số cuối tương ứng giống nhau bằng
chỉnh hợp lặp chập m của 10 phần tử [0 9]: 9.10
m-1
[Chữ số đầu có 9 cách chọn, vì
bỏ số 0 đứng đầu].
Số cách chọn dãy số ở giữa:
Dãy này gồm có n-2m chữ số. Số cách chọn là: 10
n-2m
.
Theo nguyên lý nhân, ta có: 9. 10
m-1
.10
n-2m
chữ số.
b. Ứng dụng tính số chữ số có 10 chữ số mà 3 chữ số đầu và 3 chữ số cuối
tương ứng giống nhau.
Số chữ số thỏa mãn đề bài bằng: 9.10
2
.10
10-6
= 9.10
2
.10
4
= 9000000.
xx…xbb…bxx…x
n
m
Toán rời rạc - Tài liệu dùng để luyện thi cao học ngành Khoa học máy tính
ấn Ngọc 8
Bài 12. [Đề thi cao học Đà Nẵng - 8/2008]
a. Trong một lớp học có 30 người. Cho biết có bao nhiêu cách cử một ban đại
diện gồm 1 lớp trưởng, 1 lớp phó và 1 thủ quỹ.
Có 30 cách chọn 1 lớp trưởng.
Sau khi chọn 1 lớp trưởng xong, có 29 cách chọn 1 lớp phó.
Sau khi chọn 1 lớp trưởng, 1 lớp phó xong, có 28 cách chọn 1thủ quĩ.
Theo nguyên lý nhân, ta có : 30.29.28 = 24360 cách chọn.
Cách khác:
Số cách chọn chính bằng số chỉnh hợp không lặp chập 3 của 30 phần tử :
A[30,3] = 30!/[30-3]!= 24360.
b. Cho biết có thể nhận bao nhiêu xâu ký tự khác nhau bằng cách sắp xếp lại
các chữ cái của từ SUCCESS.
Từ SUCCESS có: 3 chữ S, 2 chữ C, 1 chữ U và 1 chữ E.
Vậy có :
4207.6.5.2
2
7.6.5.4
!1!.2!.1!.3
!7
xâu khác nhau.
Bài 13. [Đề thi cao học Đà Nẵng - 2/2009]
a. Giả sử chúng ta có 5 viên bi giống nhau và 3 chiếc túi khác màu là xanh,
vàng và đỏ. Cho biết có bao nhiêu cách bỏ bi vào các túi? Ví dụ: cách 1 -> túi
xanh 5 viên, túi vàng và túi đỏ không có bi; cách 2 -> túi xanh 3 viên, túi vàng
và túi đỏ mỗi túi 1 viên, …
Số cách bỏ bi tương ứng chính bằng số tổ hợp lặp chập 5 từ tập có 3 phần tử là:
21
2
7.6
!2]!.27[
!7
2
7
13
153
1
1
CCC
n
kn
b. Giả sử chúng ta có 5 viên bi [2 bi sắt, 2 bi chai và 1 bi đất] và 3 chiếc túi màu
xanh, vàng và đỏ. Cho biết có bao nhiêu cách bỏ bi vào các túi? Ví dụ: Cách 1
túi xanh chứa 2 bi sắt, túi vàng 2 bi chai và túi đỏ 1 bi đất; cách 2 -> túi xanh 1
bi sắt, túi vàng 2 bi chai + 1 bi sắt và túi đỏ 1 bi đất, …
Ta bỏ lần lượt từng loại vào 3 cái túi:
+ Bỏ 2 viên bi sắt vào 3 cái túi, có
6
2
4.3
!2]!.2[
!4
2
4
13
123
1
1
CCC
n
kn
cách bỏ
Toán rời rạc - Tài liệu dùng để luyện thi cao học ngành Khoa học máy tính
ấn Ngọc 9
+ Bỏ 2 viên bi chai vào 3 cái túi, có
6
2
4.3
!2]!.2[
!4
2
4
13
123
1
1
CCC
n
kn
cách bỏ bi
+ Bỏ 1 viên bi chai vào 3 cái túi, có
3
!2!.1
!3
2
3
13
113
1
1
CCC
n
kn
cách bỏ bi
Theo nguyên lý nhân, ta có: 6.6.3 = 108 cách bỏ bi.
c. Giả sử chúng ta có 5 viên bi [2 bi sắt, 2 bi chai và 1 bi đất. Cho biết có bao
nhiêu cách sắp chúng thành hàng? Ví dụ: sắt sắt chai chai đất, sắt chai sắt chai
đất,…
Cách sắp các viên bi thành hàng chính bằng hoán vị lặp của 5 phần tử, trong đó 2
bi sắt, 2 bi chai và 1 bi đất, vậy có:
30
2
5.4.3
!1!.2!.2
!5
cách sắp bi.
14. [Đề thi cao học ĐH CNTT TPHCM -5/2001]
a. Tìm số các chuỗi 8 bits thỏa mãn điều kiện: bit đầu tiên là 1 hay 2 bit cuối là 0
Gọi A là số chuỗi 8bits có bit đầu tiên là 1
B là số chuỗi 8bits có 2 bit cuối là 0.
Theo nguyên lý bù trừ, ta có N[A B] = N[A] + N[B] – N[A B]
Tính N[A]: Gọi S=s
1
s
2
s
3
s
4
s
5
s
6
s
7
s
8
là chuỗi 8bits có bit đầu tiên là 1. Vậy s
1
có 1
trường hợp, s
i
[i=2 8] có 2 trường hợp 0 và 1. Theo nguyên lý nhân, ta có:
N[A] = 1.2.2.2.2.2.2.2 = 2
7
Tương tự: N[B] = 2
6
.
N[A B] = 2
5
Vậy: N[A B] = 2
7
+ 2
6
– 2
5
= 160
b. Mỗi người sử dụng một hệ thống máy tính của một công ty X phải sử dụng
một password dài từ 6 đến 8 ký tự, trong đó mỗi ký tự là một chữ cái hoặc là một
chữ s Mỗi password phải có ít nhất một chữ số. Hỏi có thể lập được bao nhiêu
password khác nhau?
n
.
Toán rời rạc - Tài liệu dùng để luyện thi cao học ngành Khoa học máy tính
ấn Ngọc 10
n
.
n
- 52
n
6
- 52
6
7
- 52
7
8
- 52
8
6
- 52
6
] + [62
7
- 52
7
]
+ [62
8
- 52
8
]
6
– 26
6
] + [36
7
– 26
7
]
+ [36
8
– 26
8
]
15. [Đề thi cao học ĐH KHTN-1999]
Xét 3 chuỗi ký tự trên tập mẫu tự {a, b, c} [ với a < b < c] : s1 = ac, s2 = aacb, s3
= aba.
a. Hãy sắp xếp chúng theo thứ tự tăng đối với thứ tự từ điển.
a < b < c, nên s2 < s3 < s1]
b. Cho biết giữa s1 và s3 có bao nhiêu chuỗi ký tự có chiều dài 6.
s3 = aba < ab * * * * < s1 = ac
Bài 16. Cho trước một đa giác lồi P có 10 đỉnh lần lượt là A, B, C, D, E, F, G, H,
I, J. Giả sử rằng trong đa giác không có 3 đường chéo nào cắt nhau tại một
điểm. Hãy cho biết đa giác có tổng bao nhiêu đường chéo.
Vì đa giác lồi P có 10 đỉnh, nên tổng số các đường nối 2 đỉnh bất kỳ của P chính
bằng tổ hợp chập 2 [đỉnh] của 10 [đỉnh].
45
2
10.9
!2]!.210[
!10
2
10
C
cạnh.
Theo đề bài đa giác lồi P có 10 cạnh, vậy số đường chéo của đa giác P là:
45 -10 =35
Toán rời rạc - Tài liệu dùng để luyện thi cao học ngành Khoa học máy tính
ấn Ngọc 11
Bài 17. Tìm số nghiệm nguyên không âm của:
a. Phương trình
20
4321
xxxx
với x
1
0 ; x
2
0; x
3
0; x
4
0
Ta nhận thấy mỗi nghiệm của phương trình ứng với một cách chọn 20 phần tử từ
một tập có 4 loại, sao cho có x1 phần tử loại 1, x2 phần tử loại 2, x3 phần tử loại 3,
x4 phần tử loại 4 được chọn. Vậy số nghiệm bằng số tổ hợp lặp chập 20 từ tập có 4
phần tử là:
177123.11.7
3.2
23.22.21
!3!.20
!23
!3]!.323[
!23
3
23
14
1204
1
1
CCC
n
kn
b. Phương trình
20
4321
xxxx
với x
1
6 ; x
2
3; x
3
9; x
4
-2
x
1
> 6 x
1
– 6 0 Đặt : a = x
1
- 6 => x
1
= a + 6
x
2
> 3 x
2
– 3 0 b = x
2
- 3 => x
2
= b + 3
x
3
> 9 x
3
– 9 0 c = x
3
- 9 => x
3
= c + 9
x
4
>-2 x
4
+ 2 0 d = x
4
+ 2 => x
4
= d - 2
20
4321
xxxx
a + 6 + b + 3 + c + 9 + d – 3 = 20
a + b + c + d = 5 với a 0; b 0; c 0; d 0
Vậy có :
56
3.2
8.7.6
!3!.5
!8
!3]!.38[
!8
3
8
14
154
1
1
CCC
n
kn
nghiệm
c. Bất phương trình x
1
+ x
2
+ x
3
≤ 11 với x
1
0; x
2
0; x
3
0.
Thêm ẩn phụ x4 0.
ương đương x
1
+ x
2
+ x
3
+ x
4
= 11 với x
1
0; x
2
0;
x
3
0; x
4
0.
364
3.2
14.13.12
!3!.11
!14
3
14
14
1114
1
1
CCC
n
kn
.
d. Phương trình x + y + z = 10 với 0 x 2, 0 y 4, 0 z 6.
Gọi U là tập tất cả các nghiệm nguyên không âm của phương trình x + y + z = 10,
ta có:
66
2
12.11
!2!.10
!12
2
12
13
1103
1
1
CCCUN
n
kn
.
Gọi: A là tập nghiệm với x 3, y 0, z 0.
Toán rời rạc - Tài liệu dùng để luyện thi cao học ngành Khoa học máy tính
ấn Ngọc 12
B là tập nghiệm với x 0, y 5, z 0.
C là tập nghiệm với x 0, y 0, z 7.
Theo nguyên lý bù trừ, số nghiệm nguyên của phương trình là:
N* = N – A B C
A B C = A + B + C + A B + A C + B C - A B C
A là tập nghiệm với x 3, y 0, z 0, đặt x’=x-3, y’=y, z’=z, phương trình đã
cho tương đương với x’ + y’ + z’ = 7 với x’ 0, y’ 0, z’ 0.
=> A = C[9,2] = 9!/7!.2! = 8.9/2 = 36.
Tương tự : B = C[7,2] = 7!/5!.2! = 6.7/2 = 21.
C = C[5,2] = 5!/3!.2! = 4.5/2 = 10.
A B : x 3, y 5, z 0 : => x’ + y’ + z’ = 2 với x’ 0, y’ 0, z’ 0.
A B =C[4,2] = 4!/2!2!= 3.4/2 = 6.
A C : x 3, y 0, z 7 : => x’ + y’ + z’ = 0 với x’ 0, y’ 0, z’ 0.
A C =C[2,2] = 2!/0!2! = 1.
B C : x 0, y 5, z 7 : => x’ + y’ + z’ = -2 với x’ 0, y’ 0, z’ 0.
=> B C =0.
A B C : x 3, y 5, z 7 : => x’ + y’ + z’ = -5 với x’ 0, y’ 0, z’ 0.
=> A B C =0.
Vậy : A B C = 28 + 21 + 10 + 6 + 1 + 0 – 0 = 60
=> N* = 66 – 60 = 8.
Đó là các nghiệm: [0,4,6]; [1,3,6]; [1,4,5]; [2,2,6]; [2,3,5]; [2,4,4];
N [x 0, y 0, z 0]
A
x 3
B
y 5
C
z 7
N*
Toán rời rạc - Tài liệu dùng để luyện thi cao học ngành Khoa học máy tính
ấn Ngọc 13
e. Phương trình
20
4321
xxxx
[1] thỏa mãn x1 ≤ 3; x2 ≥ 2; x3 > 4
Vì các biến nhận giá trị nguyên. Nên điều kiện x1 ≤ 3; x2 ≥ 2; x3 > 4 được viết lại
là: x1 ≤ 3; x2 ≥ 2; x3 ≥ 5 [*]. Xét các điều kiện sau:
x2 ≥ 2; x3 ≥ 5 [**]
x1 ≥ 4; x2 ≥ 2; x3 ≥ 5 [***]
Ta gọi p, q, r lần lượt là các số nghiệm nguyên không âm của phương trình thỏa
mãn [*], [**], [***].
Ta có: p = q – r
Trước hết, ta tìm q như sau:
Đặt: x
1
’= x
1
, x
2
’ = x
2
– 2, x
3
’ = x
3
– 5, x
4
’ = x
4
.
Phương trình [1] trở thành: x
1
’ + x
2
’ + x
3
’ + x
4
’ = 13 [2]
Số nghiệm nguyên không âm của [2] chính bằng số nghiệm của [1] thỏa mãn [**].
Mà số nghiệm của [2] là
.56016.5.7
3.2
16.15.14
!3!.13
!16
3
16
14
1134
1
1
CCC
n
kn
Ta tìm r như sau:
Đặt: x
1
’= x
1
- 4, x
2
’ = x
2
– 2, x
3
’ = x
3
– 5, x
4
’ = x
4
.
Phương trình [1] trở thành: x
1
’ + x
2
’ + x
3
’ + x
4
’ = 9 [3]
Số nghiệm nguyên không âm của [3] chính bằng số nghiệm của [1] thỏa mãn
[***]. Mà số nghiệm của [3] là:
2204.11.5
3.2
12.11.10
!3!.9
!12
3
12
14
194
1
1
CCC
n
kn
=> P = q – r = 560 – 220 = 340.
Vậy số nghiệm nguyên nguyên không âm của phương trình [1] thỏa điều kiện [*]
là 340.
. [Đề thi cao học ĐH Đà Nẵng – 10/2010].
[1]
:
Toán rời rạc - Tài liệu dùng để luyện thi cao học ngành Khoa học máy tính
ấn Ngọc 14
12650
4.3.2
25.24.23.22
!4!.21
!25
!4]!.425[
!25
4
25
15
1215
1
1
CCC
n
kn
b.
x51].
Gọi X là số từ có độ dài n chỉ có chữ số: X= 4
n
Y là số từ có độ dài n chỉ có ký tự: Y= 7
n
Vậy số từ thỏa mãn đề bài là: 11
n
– 4
n
– 7
n
Toán rời rạc - Tài liệu dùng để luyện thi cao học ngành Khoa học máy tính
ấn Ngọc 18
Bài 23. [Đề thi cao học Đà Nẵng – 10/2010]
Cho X={0 15}. Chứng tỏ rằng nếu S là một tập con gồm 9 phần tử của X thì có
ít nhất 2 phần tử của S có tổng bằng 15.
Phân hoạch X thành 8 tập con, mỗi tập con đều có tổng bằng 15, như sau:
{0,15}, {1,14}, {2,13}, {3,12}, {4,11}, {5,10}, {6,9}, {7,8}
Phân 9 phần tử của S vào 8 tập con trên. Theo nguyên lý Dirichlet, có 2 phần tử
của S thuộc một tập nào đó, mà tổng 2 phần tử này sẽ bằng 15.
Bài 24. [Đề thi cao học Đà Nẵng – 3/2011]
Trong mặt phẳng cho 6 điểm phân biệt nối nhau từng đôi một bởi các đoạn
thẳng màu xanh hoặc đỏ. Chứng tỏ rằng có 3 điểm nối nhau bởi các đoạn thẳng
cùng màu.
Gọi A, B, C, D, E, F là 6 điểm phân biệt nằm trong một mặt phẳng.
Giả sử ta chọn điểm A, nối điểm A với 5 điểm còn lại B, C, D, E, F bởi các đoạn
thẳng màu xanh hoặc đỏ.
+ Ngược lại, tam giác BCD không có cạnh màu đỏ, thì tam giác này phải màu
xanh.
Vậy luôn luôn tồn tại 3 điểm nối với nhau từng đôi 1 bởi các đoạn thẳng cùng màu
A
B
C
D
E
F
Giả sử ta chọn điểm A, nối điểm A với 5 điểm
còn lại B, C, D, E, F bởi các đoạn thẳng màu
xanh hoặc đỏ.
Theo nguyên lý Dirichlet phải có 3 đoạn thẳng
cùng màu xanh hoặc đỏ. Giả sử là 3 đoạn
thẳng AB, AC và AD có màu đỏ [như hình
vẽ].
+ Nếu trong tam giác BCD có cạnh màu đỏ,
giả sử là cạnh BC, thì tam giác ABC là tam
giác có các cạnh màu đỏ [hay 3 điểm nối nhau
cùng màu].
Toán rời rạc - Tài liệu dùng để luyện thi cao học ngành Khoa học máy tính
ấn Ngọc 19
Bài 25. Một võ sĩ quyền anh thi đấu giành chức vô địch trong 75 giờ. Mỗi giờ
đấu ít nhất một trận, nhưng toàn bộ không quá 125 trận. Chứng tỏ rằng có
những giờ liên tiếp đã đấu 24 trận.
Gọi a
i
là số trận đấu cho đến hết giờ thứ i [i=1 75] của võ sĩ quyền anh.
Ta có : 1 a
1
< a
2
…< a
75
125. [1]
25 a
1
+24 < a
2
+24 …< a
75
+24 149. [2]
Như vậy ta có 150 số trong 2 dãy [1] và [2] nhận giá trị trong {1 149}.
Theo nguyên lý Dirichlet phải có 2 hai số bằng nhau. Vì 2 dãy trên là dãy tăng, nên
hai số bằng nhau thuộc 2 dãy khác nhau. Hay, ta có: a
i
+24 = a
j
a
j
– a
i
=24. Như
vậy, từ giờ i đến hết giờ j võ sĩ đã thi đấu 24 trận.
Bài 26. [Đề thi cao học Đà Nẵng – 8/2009]
a. Một mạng máy tính có n [n>1] máy tính. Mỗi máy tính được nối trực tiếp
hoặc không nối với các máy khác. CMR có ít nhất hai máy tính mà số các máy
tính khác nối với chúng là bằng nhau.
Gọi q1, q2, q3, … qn là số máy tính kết nối với máy 1, 2, 3 n.
Như vậy ta có: 0 qi n-1 i=1 n
Tuy nhiên, không thể xảy ra đồng thời: có 1 máy không kết nối với máy nào cả, tức
là q
i
=0 và có một máy kết nối với tất cả các máy còn lại [q
j
=n-1]. Vậy chỉ xảy ra 1
trong hai trường hợp sau:
0 qi n-2 i=1 n
1 qi n-1 i=1 n
Cả hai trường hợp trên n có q
i
nhận n-1 giá trị. Theo nguyên lý Dirichlet, có i j sao
cho q
i
=q
j
. Hay có ít nhất 2 trong số n máy tính có số máy kết nối với chúng bằng
nhau.
b. Trong một mặt phẳng có 17 điểm phân biệt được nối với nhau từng đôi một
bởi các đoạn thẳng màu xanh, hoặc màu đỏ, hoặc màu vàng. CMR luôn tồn tại
ba điểm nối với nhau bởi các đoạn thẳng cùng màu
Chọn 1 điểm bất kỳ, giả sử là P, từ P ta nối với 16 điểm còn lại bởi các đoạn thẳng
là màu xanh, hoặc màu đỏ, hoặc màu vàng.
Theo nguyên lý Dirichlet, trong 16 đoạn thẳng này sẽ có 6 đoạn thẳng có cùng
màu. Giả sử 6 đoạn thẳng đó nối P với 6 điểm A, B, C, D, E, F có 2 trường hợp:
Toán rời rạc - Tài liệu dùng để luyện thi cao học ngành Khoa học máy tính
ấn Ngọc 20
+ Sáu điểm A, B, C, D, E, F được nối với nhau từng đôi một bởi các đoạn thẳng,
trong đó có ít nhất 1 đoạn thẳng có màu đỏ. Khi đó, đoạn thẳng màu đỏ này cùng
với điểm P tạo thành 3 điểm nối với nhau bởi các đoạn thẳng có màu đỏ.
+ Sáu điểm A, B, C, D, E, F được nối với nhau từng đôi một bởi các đoạn thẳng
không có màu đỏ, tức là các đoạn thẳng này có màu xanh hoặc vàng. Khi đó, chọn
điểm bất kỳ [chẳng hạn điểm A] nối với 5 điểm còn lại bởi các đoạn thẳng màu
xanh hoặc vàng. Theo nguyên lý Dirichlet, tồn tại ít nhất 3 trong 5 đoạn thẳng có
cùng màu, giả sử đó là màu xanh. Giả sử đó là các cạnh AB, AC và AD. Nếu có ít
nhất một trong 3 đoạn thẳng BC, CD và DB có màu xanh thì cùng với điểm A tạo
thành 3 điểm được nối với bởi màu xanh. Ngược lại, thì B, C, D là điểm được nối
với nhau bởi màu vàng.
Như vậy, luôn tồn tại ba điểm nối với nhau bởi các đoạn thẳng cùng màu
Bài 27. Trong mặt phẳng xOy lấy ngẫu nhiên 5 điểm tọa độ nguyên. Chứng tỏ
rằng có ít nhất một trung điểm của các đoạn nối chúng có tọa độ nguyên.
Giả sử trong mặt phẳng xOy có A[x1,y1], B[x2,y2]. Vậy trung điểm của đoạn
thẳng AB sẽ là:
2
21
,
2
21 yyxx
. Các tọa độ này nguyên khi:
[x1,x2] đều chẵn hoặc đều lẻ, [y1,y2] đều chẵn hoặc đều lẻ.
Vì có 4 bộ bao gồm 2 phần tử có tính chẵn lẻ với nhau. Nên theo nguyên lý
Dirichlet thì trong 5 điểm sẽ có ít nhất 2 điểm có tính chẵn lẻ như nhau. Do dó,
trung điểm của 2 điểm này sẽ có tọa độ nguyên.
Bài 28. Cho trước các tập hợp gồm các phần tử xác định nào đó.
a. Hãy cho biết các cách mô tả, hay biểu diễn một tập hợp? Cho ví dụ.
+ Nếu A là một tập hợp gồm một số hữu hạn phần tử, để biểu diễn tập A, ta có thể
liệt kê hết các phần tử của A.
- Ví dụ biểu diễn A là tập hợp 4 chữ cái hoa đầu tiên: A={‘A’,’B’,’C’,’D’}
+ Nếu A là một tập hợp vô hạn các phần tử, để biểu diễn tập A, ta dùng cách biểu
diễn tính chất của các phần tử, có dạng:
A={x P[x]} là tập hợp các phần tử x, sao cho x thỏa mãn tính chất P
Toán rời rạc - Tài liệu dùng để luyện thi cao học ngành Khoa học máy tính
ấn Ngọc 21
- Ví dụ biểu diễn A là tập hợp các số thực: A={x x R}
b. Hãy cho biết thế nào là một tập hợp đếm được, một tập hợp không đếm được?
Cho ví dụ.
+ Nếu A là một tập hợp có hữu hạn phần tử, thì tập A được gọi là tập đếm được.
Ví dụ: A={1, 2, 3, 4, 5, 6, 7, 8, 9}, A là tập đếm được vì nó có 9 phần tử, từ 1 đến 9
+ Nếu A là một tập hợp có vô hạn phần tử, thì tập A có thể là tập đếm được hoặc
không đếm được. Để xác định A có đếm được hay không ta chỉ cần xây dựng song
ánh giữa tập A với tập các số tự nhiên N.
Ví dụ: Cho A là tập hợp các số phức. A là tập vô hạn không đếm được.
c. Cho A là tập không đếm được, B là tập đếm được. Hãy cho biết tập hợp A-B
[hiệu] có đếm được hay không?
Giả sử A-B là tập đếm được, khi đó A=[A-B] B cũng là tập hợp đếm được, vì:
[A-B] : là tập đếm được theo giả thiết.
B : là tập đếm được theo đề bài.
Mâu thuẩn với đề bài đã cho là A là tập không đếm được. Vậy A-B là tập không
đếm được.
d. CMR tích Decac của hai tập hợp vô hạn đếm được cũng là một tập vô hạn
đếm được?
Tích Decac AxB là tập tất cả các cặp phần tử có trật tự sắp xếp [a,b] được tạo ra
bởi một phần tử a A với các phần tử đứng kế tiếp b B.
Giả sử A={a
i
, i=1 n}; B={b
j
, j=1 n}
Ta xây dựng một [bảng] ma trận hai chiều, đầu mỗi hàng là một phần tử của A, đầu
mỗi cột là phần tử của B. Khi đó, các phần tử của tích Decac AxB là các phần tử
của ma trận.
Toán rời rạc - Tài liệu dùng để luyện thi cao học ngành Khoa học máy tính
ấn Ngọc 22
b
1
b
2
…
b
n
a
1
a
1
b
1
a
1
b
2
a
1
b
n
a
2
a
2
b
1
a
2
b
2
…
a
1
b
n
…
a
n
a
n
b
1
a
n
b
2
…
a
n
b
n
Từ ma trận trên ta suy ra AxB là đếm được.
Bài 29. [Đề thi cao học Đà Nẵng – 5/2007]
Cho dãy u = trong đó a
i
là các ký tự tùy ý, i 1 n, n là độ dài của
dãy u đã cho. Một dãy v = được gọi là dãy con của dãy u nếu tìm
được dãy các chỉ số 1 i
1
< i
2
< … < im n và b
k
=a
ik
với mọi k 1 m.
Chẳng hạn dãy v = < B, C, D, B> là dãy con của dãy u = < A, B, C, B, D, A, B>
với dãy chỉ số là .
Một dãy w được gọi là dãy con chung của hai dãy u và v đã cho, nếu w vừa là dãy
con của u và vừa là dãy con của v. Một dãy con chung được gọi là lớn nhất nếu có
độ dài lớn nhất trong số các dãy con của các dãy đã cho.
Chẳng hạn, các dãy và đều là dãy con chung lớn nhất
của hai dãy và .
Gọi C[i,j] là độ dài của một dãy con chung lớn nhất của hai dãy X= và Y= [0 i n, 0 j m]. Người ta tìm được công thức đệ quy
tính C[i,j] như sau:
Toán rời rạc - Tài liệu dùng để luyện thi cao học ngành Khoa học máy tính
ấn Ngọc 23
a, Hãy giải thích công thức đệ quy trên:
- Nếu i=0 hoặc j=0 thì C[i,j] = 0.
- Nếu i>0, j>0:
+ Nếu X
i
= Y
j
thì dãy con chung dài nhất của X
i
và Y
j
sẽ thu được bằng việc
bổ sung X
i
vào dãy con chung dài nhất của hai dãy X
i-1
và Y
j-1
+ Nếu X
i
Y
j
thì dãy con chung dài nhất của X
i
và Y
j
sẽ là dãy con dài nhất
trong hai dãy con chung dài nhất của [X
i
và Y
i-1
] và của [X
i-1
và Y
j
].
b, Viết hàm RecMaxSubSeq dùng phương pháp lặp tính độ dài dãy con chung
lớn nhất của hai dãy trên.
Type Mang= array[1 50,1 50] of byte;
Function RecMaxSubSeq [X,Y,m,n]: Mang;
Var i,j: Byte; C: Mang;
Begin
for i :=1 to n do c[i,0]:=0;
for j: =1 to m do c[0,j]:=0;
for i: =1 to n do
for j: = 1to m do
if x[i] = y[i] then
c[i,j]:=c[i-1,j-1]+1
else if c [i-1,j] c[i,j-1] then
c[i,j]:=c[i-1,j]
else c[i,j]:=c[i,j-1];
RecMaxSubSeq :=C;
End;
Toán rời rạc - Tài liệu dùng để luyện thi cao học ngành Khoa học máy tính
ấn Ngọc 24
Kỹ thuật đếm nâng cao
Bài 1. Cho dãy số {a
n
} thỏa mãn hệ thức truy hồi:
a
n
= 5a
n-1
– 6a
n-2
; a
0
=0 và a
1
=1.
a. Giải hệ thức truy hồi trên.
Ta có phương trình đặt trưng : x
2
= 5x – 6 x
2
– 5x + 6 =0
có 2 nghiệm phân biệt : x
1
= 3 và x
2
= 2
Hệ thức truy hồi có dạng: a
n
= b3
n
+ d2
n
[1]
Với a
0
=0, a
1
=1thay lần lượt vào [1], ta có hệ phương trình sau:
b + d =0
3b + 2d = 1
=> b = 1, d = -1
Vậy hệ thức truy hồi là : a
n
= 3
n
- 2
n
b. Viết hàm A[n] để tính a
n
Function A[n: integer]: Integer;
Begin
If n=0 then A:=0
Else if n=1 then A:=1
Else
A:=5*A[n-1] – 6*A[n-2];
End;
Bài 2. Giải hệ thức truy hồi a
n
= 6a
n-1
- 9a
n-2
; a
0
=1, a
1
=6
Ta có phương trình đặt trưng : x
2
= 6x – 9 x
2
– 6x + 9 =0
PT có nghiệm kép : x = 3
Hệ thức truy hồi có dạng: a
n
= b3
n
+ d.n.3
n
Thay a
0
=1 và a
1
=6, ta có hệ phương trình :
633
1
db
b
=> b = 1, d = 1
Vậy hệ thức truy hồi là : a
n
= 3
n
+ n3
n
= [1+n] 3
n
Bài Tập Trắc Nghiệm Hoán Vị Chỉnh Hợp Tổ Hợp Có Đáp Án Và Lời Giải
Bởi
Baitaptracnghiem.net-
0
13838
Bài Tập Trắc Nghiệm Và Tự Luận Chương Tổ Hợp Xác Suất Có Đáp Án Và Lời Giải
- Bài Tập Trắc Nghiệm Quy Tắc Đếm Có Đáp Án Và Lời Giải
- Bài Tập Trắc Nghiệm Hoán Vị Chỉnh Hợp Tổ Hợp Có Đáp Án Và Lời Giải
- Bài Tập Trắc Nghiệm Xác Suất Có Đáp Án Và Lời Giải
- Trắc Nghiệm Nhị Thức Niu-Tơn Có Đáp Án Và Lời Giải Chi Tiết
Bài tập trắc nghiệm hoán vị chỉnh hợp tổ hợp có đáp án và lời giải rất hay gồm 90 câu trắc nghiệm. Các bạn xem ở dưới để ôn tập và cũng cố thêm kiến thức nhé.
BÀI TẬP HOÁN VỊ CHỈNH HỢP TỔ HỢP CÓ ĐÁP ÁN
Vấn đề 1. HOÁN VỊ
Câu 1:Có bao nhiêu khả năng có thể xảy ra đối với thứ tự giữa các đội trong một giải bóng có 5 đội bóng? [giả sử rằng không có hai đội nào có điểm trùng nhau]
A.120. B.100. C.80. D.60.
Câu 2:Có bao nhiêu cách xếp khác nhau cho 5 người ngồi vào một bàn dài?
A.120 B.5 C.20 D.25
Câu 3:Số cách sắp xếp 6 nam sinh và 4 nữ sinh vào một dãy ghế hàng ngang có 10 chỗ ngồi là:
A.6!4!. B.10!. C.6!−4!. D.6!+4!.
Câu 4:Sắp xếp năm bạn học sinh An, Bình, Chi, Dũng, Lệ vào một chiếc ghế dài có 5 chỗ ngồi. Số cách sắp xếp sao cho bạn Chi luôn ngồi chính giữa là
A.24. B.120. C.60. D.16.
Câu 5:Sắp xếp năm bạn học sinh An, Bình, Chi, Dũng, Lệ vào một chiếc ghế dài có 5 chỗ ngồi. Hỏi có bao nhiêu cách sắp xếp sao cho bạn An và bạn Dũng luôn ngồi ở hai đầu ghế?
A.120. B.16 C.12. D.24.
Câu 6:Sắp xếp năm bạn học sinh An, Bình, Chi, Dũng, Lệ vào một chiếc ghế dài có 5 chỗ ngồi. Hỏi có bao nhiêu cách sắp xếp sao cho bạn An và bạn Dũng không ngồi cạnh nhau?
A.24. B.48. C.72. D.12.
Câu 7:Có 3 viên bi đen khác nhau, 4 viên bi đỏ khác nhau, 5 viên bi xanh khác nhau. Hỏi có bao nhiêu cách sắp xếp các viên bi trên thành một dãy sao cho các viên bi cùng màu ở cạnh nhau?
A.345600. B.725760. C.103680. D.518400.
Câu 8:Cô dâu và chú rể mời6người ra chụp ảnh kỉ niệm, người thợ chụp hình có bao nhiêu cách sắp xếp sao cho cô dâu, chú rể đứng cạnh nhau.
A.8!−7!. B.2.7!. C.6.7!. D.2!+6!.
Câu 9:Trên giá sách muốn xếp20cuốn sách khác nhau. Có bao nhiêu cách sắp xếp sao cho tập1và tập2đặt cạnh nhau.
A.20!−18!. B.20!−19!. C.20!−18!.2!. D.19!.18.
Câu 10:Có bao nhiêu cách sắp xếp 4 người vào 4 ghế ngồi được bố trí quanh một bàn tròn?
A.12. B.24. C.4. D.6.
Câu 11:Có 4 nữ sinh tên là Huệ, Hồng, Lan, Hương và 4 nam sinh tên là An, Bình, Hùng, Dũng cùng ngồi quanh một bàn tròn có 8 chỗ ngồi. Hỏi có bao nhiêu cách sắp xếp biết nam và nữ ngồi xen kẽ nhau?
A.576. B.144. C.2880. D.1152.
Câu 12:Từ các số tự nhiên 1, 2, 3, 4 có thể lập được bao nhiêu số tự nhiên có 4 chữ số khác nhau?
A.44. B.24. C.1. D.42.
Vấn đề 2. CHỈNH HỢP
Câu 13:Có bao nhiêu cách xếp khác nhau cho 6 người ngồi vào 4 chỗ trên một bàn dài?
A.15. B.720. C.30. D.360.
Câu 14:Giả sử có bảy bông hoa khác nhau và ba lọ hoa khác nhau. Hỏi có bao nhiêu cách cắm ba bông hoa vào ba lọ đã cho [mội lọ cắm một bông]?
A.35. B.30240. C.210. D.21.
Câu 15:Có bao nhiêu cách cắm 3 bông hoa vào 5 lọ khác nhau [mội lọ cắm không quá một một bông]?
A.60. B.10. C.15. D.720.
Câu 16:Có bao nhiêu cách mắc nối tiếp 4 bóng đèn được chọn từ 6 bóng đèn khác nhau?
A.15. B.360. C.24. D.17280.
Câu 17:Trong mặt phẳng cho một tập hợp gồm 6 điểm phân biệt. Có bao nhiêu vectơ khác vectơ0→có điểm đầu và điểm cuối thuộc tập hợp điểm này?
A.15. B.12. C.1440. D.30.
Câu 18:Trong trận chung kết bóng đá phải phân định thắng thua bằng đá luân lưu 11 mét. Huấn luyện viên mỗi đội cần trình với trọng tài một danh sách sắp thứ tự 5 cầu thủ trong số 11 cầu thủ để đá luân lưu 5 quả 11 mét. Hãy tính xem huấn luyện viên của mỗi đội có bao nhiêu cách lập danh sách gồm 5 cầu thủ.
A.462. B.55. C.55440. D.11!.5!
Câu 19:Giả sử có 8 vận động viên tham gia chạy thi. Nếu không kể trường hợp có hai vận động viên về đích cùng lúc thì có bao nhiêu kết quả có thể xảy ra đối với các vị trí nhất, nhì, ba?
A.336. B.56. C.24. D.120.
Câu 20:Trong một ban chấp hành đoàn gồm 7 người, cần chọn ra 3 người vào ban thường vụ. Nếu cần chọn ban thường vụ gồm ba chức vụ Bí thư, Phó bí thư, Ủy viên thường vụ thì có bao nhiêu cách chọn?
A.210. B.200. C.180. D.150.
Câu 21:Một cuộc thi có 15 người tham dự, giả thiết rằng không có hai người nào có điểm bằng nhau. Nếu kết quả của cuộc thi là việc chọn ra các giải nhất, nhì, ba thì có bao nhiêu kết quả có thể?
A.2730. B.2703. C.2073. D.2370.
Câu 22:Trong một dạ hội cuối năm ở một cơ quan, ban tổ chức phát ra 100 vé xổ số đánh số từ 1 đến 100 cho 100 người. Xổ số có 4 giải: 1 giải nhất, 1 giải nhì, 1 giải ba, 1 giải tư. Kết quả là việc công bố ai trúng giải nhất, giải nhì, giải ba, giải tư. Hỏi có bao nhiêu kết quả có thể?
A.94109040. B.94109400. C.94104900. D.94410900.
Câu 23:Trong một dạ hội cuối năm ở một cơ quan, ban tổ chức phát ra 100 vé xổ số đánh số từ 1 đến 100 cho 100 người. Xổ số có 4 giải: 1 giải nhất, 1 giải nhì, 1 giải ba, 1 giải tư. Kết quả là việc công bố ai trúng giải nhất, giải nhì, giải ba, giải tư. Hỏi có bao nhiêu kết quả có thể nếu biết rằng người giữ vé số 47 được giải nhất?
A.944109. B.941409. C.941094. D.941049.
Câu 24:Trong một dạ hội cuối năm ở một cơ quan, ban tổ chức phát ra 100 vé xổ số đánh số từ 1 đến 100 cho 100 người. Xổ số có 4 giải: 1 giải nhất, 1 giải nhì, 1 giải ba, 1 giải tư. Kết quả là việc công bố ai trúng giải nhất, giải nhì, giải ba, giải tư. Hỏi có bao nhiêu kết quả có thể nếu biết rằng người giữ vé số 47 trúng một trong bốn giải?
A.3766437. B.3764637. C.3764367. D.3764376.
Câu 25:Có bao nhiêu số tự nhiên gồm5chữ số khác nhau được lập từ các số
1, 2, …, 9?
A.15120. B.95. C.59. D.126.
Câu 26:Cho tập A = { 0,1, 2, …, 9}. Số các số tự nhiên có 5 chữ số đôi một khác nhau lấy ra từ tập A là?
A.30420. B.27162. B C.27216. D.30240.
Câu 27:Có bao nhiêu số tự nhiên gồm 7 chữ số khác nhau đôi một, trong đó chữ số 2 đứng liền giữa hai chữ số 1 và 3?
A.249. B.7440. C.3204. D.2942.
Vấn đề 3. TỔ HỢP
Câu 28:Một lớp học có40học sinh gồm25nam và15nữ. Chọn3học sinh để tham gia vệ sinh công cộng toàn trường, hỏi có bao nhiêu cách chọn như trên?
A.9880. B.59280. C.2300. D.455.
Câu 29:Một tổ có10người gồm6nam và4nữ. Cần lập một đoàn đại biểu gồm5người, hỏi có bao nhiêu cách lập?
A.25. B.252. C.50. D.455.
Câu 30:Trong một ban chấp hành đoàn gồm7người, cần chọn3người trong ban thường vụ. Nếu không có sự phân biệt về chức vụ của3người trong ban thường vụ thì có bao nhiêu các chọn?
A.25. B.42. C.50. D.35.
Câu 31:Một cuộc thi có15người tham dự, giả thiết rằng không có hai người nào có điểm bằng nhau. Nếu kết quả cuộc thi và việc chọn ra4người có điểm cao nhất thì có bao nhiêu kết quả có thể xảy ra?
A.1635. B.1536. C.1356. D.1365.
Câu 32:Một hộp đựng 5 viên bi màu xanh, 7 viên bi màu vàng. Có bao nhiêu cách lấy ra 6 viên bi bất kỳ?
A.665280. B.924. C.7. D.942.
Câu 33:Có bao nhiêu cách lấy hai con bài từ cỗ bài tú lơ khơ gồm52con?
A.104. B.450. C.1326. D.2652.
Câu 34:Có15đội bóng đá thi đấu theo thể thức vòng tròn tính điểm. Hỏi cần phải tổ chức bao nhiêu trận đấu?
A.100. B.105. C.210. D.200.
Câu 35:Có bao nhiêu cách cắm 3 bông hoa giống nhau vào 5 lọ khác nhau [mỗi lọ cắm không quá một bông]?
A.10. B.30. C.6. D.60.
Câu 36:Trong mặt phẳng cho tập hợpPgồm2018điểm phân biệt. Hỏi có bao nhiêu đoạn thẳng mà hai đầu mút thuộcP?
A.2018!2016!. . B.2016!2!. C.2018!2!. D.2018!2016!.2!.
Câu 37:Cho10điểm, không có3điểm nào thẳng hàng. Hỏi có bao nhiêu đường
thẳng khác nhau tạo bởi2trong10điểm nói trên?
A.90. B.20. C.45. D.Một số khác.
Câu 38:Trong mặt phẳng, cho6điểm phân biệt sao cho không có ba điểm nào thẳng hàng. Hỏi có thể lập được bao nhiêu tam giác mà các đỉnh của nó thuộc tập điểm đã cho?
A.15. B.20. C.60. D.Một số khác.
Câu 39:Cho10điểm phân biệtA1,A2, ...,A10trong đó có4điểmA1,A2,A3,A4thẳng hàng, ngoài ra không có3điểm nào thẳng hàng. Hỏi có bao nhiêu tam giác có3đỉnh được lấy trong10điểm trên?
A.96tam giác. B.60tam giác. C.116tam giác. D.80tam giác.
Câu 40:Cho mặt phẳng chứa đa giác đều [H ] có 20 cạnh. Xét tam giác có 3 đỉnh được lấy từ các đỉnh của [H ]. Hỏi có bao nhiêu tam giác có đúng 1 cạnh là cạnh của [H ].
A.1440. B.360. C.1120. D.816.
Câu 41:Cho hai đường thẳng song songd1vàd2.Trênd1lấy 17 điểm phân biệt, trênd2lầy 20 điểm phân biệt. Tính số tam giác mà có các đỉnh được chọn từ37điểm này.
A.5690. B.5960. C.5950. D.5590.
Câu 42:Số giao điểm tối đa của5đường tròn phân biệt là:
A.10. B.20. C.18. D.22.
Câu 43:Số giao điểm tối đa của10đường thẳng phân biệt là:
A.50. B.100. C.120. D.45.
Câu 44:Với đa giác lồi10cạnh thì số đường chéo là
A.90. B.45. C.35. D.Một số khác.
Câu 45:Cho đa giác đều n đỉnh n ≥3. Tìm n biết rằng đa giác đã cho có 135đường chéo.
A.n=15. B.n=27. C.n=8. D.n=18.
Câu 46:Trong mặt phẳng có bao nhiêu hình chữ nhật được tạo thành từ bốn đường thẳng phân biệt song song với nhau và năm đường thẳng phân biệt vuông góc với bốn đường thẳng song song đó.
A.60. B.48. C.20. D.36.
Câu 47:Một lớp có15học sinh nam và20học sinh nữ. Có bao nhiêu cách chọn5bạn học sinh sao cho trong đó có đúng3học sinh nữ?
A.110790. B.119700. C.117900. D.110970.
Câu 48:Có bao nhiêu số tự nhiên có4chữ số khác nhau và khác0mà trong mỗi số luôn luôn có mặt hai chữ số chẵn và hai chữ số lẻ?
A.4!C41C51. B.3!C32C52. C.4!C42C52. D.3!C42C52.
Câu 49:Một túi đựng6bi trắng,5 bi xanh. Lấy ra4 viên bi từ túi đó. Hỏi có baonhiêu cách lấy mà4viên bi lấy ra có đủ hai màu.
A.300. B.310. C.320. D.330.
Câu 50:Một nhóm học sinh có6bạn nam và5bạn nữ. Hỏi có bao nhiêu cách chọn ra5học sinh trong đó có cả nam và nữ?
A.455. B.7. C.456. D.462.
Câu 51:Để chào mừng kỉ niệm ngày thành lập Đoàn TNCS Hồ Chí Minh, nhà trường tổ chức cho học sinh cắm trại. Lớp 10A có19học sinh nam và16học sinh nữ. Giáo viên cần chọn5học sinh để trang trí trại. Hỏi có bao nhiêu cách chọn5học sinh sao cho có ít nhất1học sinh nữ? Biết rằng học sinh nào trong lớp cũng có khă năng trang trí trại.
A.C195. B.C355−C195. C.C355−C165. D.C165.
Câu 52:Một lớp học có40học sinh, trong đó có25nam và15nữ. Giáo viên cần chọn3học sinh tham gia vệ sinh công cộng toàn trường. Hỏi có bao nhiêu cách chọn 3 học sinh trong đó có nhiều nhất1học sinh nam?
A.2625. B.455. C.2300. D.3080.
Câu 53:Từ20người cần chọn ra một đoàn đại biểu gồm1trưởng đoàn,1phó đoàn,1thư kí và3ủy viên. Hỏi có bao nhiêu cách chọn đoàn đại biểu ?
A.4651200. B.4651300. C.4651400. D.4651500.
Câu 54:Một tổ gồm10học sinh. Cần chia tổ đó thành ba nhóm có5học sinh,3học sinh và2học sinh. Số các chia nhóm là:
A.2880. B.2520. C.2515. D.2510.
Câu 55:Một nhóm đoàn viên thanh niên tình nguyện về sinh hoạt tại một xã nông thôn gồm có21đoàn viên nam và15đoàn viên nữ. Hỏi có bao nhiêu cách phân chia nhóm về3ấp để hoạt động sao cho mỗi ấp có 7 đoàn viên nam và 5 đoàn viên nữ?
A.3C3612. B.C3612. C.3C217C155 D.C217C155C147C105.
Câu 56:Trong một giỏ hoa có5bông hồng vàng,3bông hồng trắng và4bông hồng đỏ [các bông hoa coi như đôi một khác nhau]. Người ta muốn làm một bó hoa gồm7bông được lấy từ giỏ hoa đó. Hỏi có bao nhiêu cách chọn hoa biết bó hoa có đúng1bông hồng đỏ?
A.56. B.112. C.224. D.448.
Câu 57:Một hộp có6viên bi xanh,5viên bi đỏ và4viên bi vàng. Chọn ngẫu nhiên 5 viên bi sao cho có đủ cả ba màu. Số cách chọn là:
A.2163. B.3843. C.3003. D.840.
Câu 58:Đội văn nghệ của nhà trường gồm4học sinh lớp 12A,3học sinh lớp 12B và 2 học sinh lớp 12C. Chọn ngẫu nhiên 5 học sinh từ đội văn nghệ để biểu diễn trong lễ bế giảng. Hỏi có bao nhiêu cách chọn sao cho lớp nào cũng có học sinh được chọn?
A.126. B.102. C.98. D.100.
Câu 59:Có12học sinh giỏi gồm3học sinh khối 12,4học sinh khối 11 và5họcsinh khối 10. Hỏi có bao nhiêu cách chọn ra6học sinh trong số học sinh giỏi đó saocho mỗi khối có ít nhất1học sinh?
A.85. B.58. C.508. D.805.
Câu 60:Đội học sinh giỏi cấp trường môn Tiếng Anh của trường THPT X theo từng khối như sau: khối 10 có5học sinh, khối 11 có5học sinh và khối 12 có5học sinh. Nhà trường cần chọn một đội tuyển gồm10học sinh tham gia IOE cấp tỉnh. Tính số cách lập đội tuyển sao cho có học sinh cả ba khối và có nhiều nhất2học sinh khối 10.
A.50. B.500. C.502. D.501.
Câu 61:Đội văn nghệ của một nhà trường gồm4 học sinh lớp 12A,3học sinh lớp
12B và2học sinh lớp 12C. Cần chọn ngẫu nhiên5học sinh từ đội văn nghệ đó để biểu diễn trong lễ bế giảng. Hỏi có bao nhiêu cách chọn sao cho lớp nào cũng có học sinh được chọn và có ít nhất2học sinh lớp 12A?
A.80. B.78. C.76. D.98.
Câu 62:Một hộp đựng8viên bi màu xanh,5viên bi đỏ,3viên bi màu vàng. Có bao nhiêu cách chọn từ hộp đó ra4viên bi sao cho số bi xanh bằng số bi đỏ?
A.280. B.400. C.40. D.1160.
Câu 63:Một hộp bi có5viên bi đỏ,3 viên bi vàng và4 viên bi xanh. Hỏi có bao
nhiêu cách lấy ra4viên bi trong đó số viên bi đỏ lớn hơn số viên bi vàng.
A.654. B.275. C.462. D.357.
Câu 64:Có5tem thư khác nhau và 6 bì thư khác nhau. Từ đó người ta muốn chọn ra 3 tem thư, 3 bì thư và dán 3 tem thư ấy lên 3 bì đã chọn. Hỏi có bao nhiêu cách làm như thế?
A.1000. B.1200. C.2000. D.2200.
Câu 65:Cho10câu hỏi, trong đó có4câu lý thuyết và6câu bài tập, người ta cấu tạo thành các đề thi. Biết rằng trong đề thi phải gồm3câu hỏi trong đó có ít nhất1câu lý thuyết và1câu hỏi bài tập. Hỏi có thể tạo được bao nhiêu đề như trên ?
A.69. B.88. C.96. D.100.
Vấn đề 4. PHƯƠNG TRÌNH – BẤT PHƯƠNG TRÌNH
Câu 66:Tìm tất cả các giá trịx thuộcℕthỏa mãn6[Px−Px−1]=Px+1.
A.x=2. B.x=3 C.x=2;x=3. D.x=5.
Câu 67:Tính tổngS của tất cả các giá trị củax thỏa mãnP2.x2-P3.x=8.
A.S=−4. B.S=−1. C.S=4. D.S=3.
Câu 68:Có bao nhiêu số tự nhiênxthỏa mãn3.A2x-A22x+42=0.
A.0. B.1. C.2. D.6.
Câu 69:Cho số tự nhiênxthỏa mãnAx10+Ax9=9.Ax8. Mệnh đề nào sau đây đúng?
A.xlà số chính phương. B.xlà số nguyên tố.
C.xlà số chẵn. D.xlà số chia hết cho3.
Câu 70:Có bao nhiêu số tự nhiên n thỏa mãnAn3+5An2=2[n+15]?
A.0. B.1. C.2. D.3.
Câu 71:Tìm giá trịn∈ℕthỏa mãnCn+11+3Cn+22=Cn+13
A.n=12. B.n=9. C.n=16. D.n=2.
Câu 72:Tính tíchPcủa tất cả các giá trị củaxthỏa mãnC14x+C14x+2=2C14x+1.
A.P = 4. B.P = 32. C.P =−32. D.P = 12.
Câu 73:Tính tổngS của tất cả các giá trị củanthỏa mãn 1Cn1-1Cn+12=76Cn+41
A.S=8. B.S=11. C.S=12. D.S=15.
Câu 74:Tìm giá trịx∈ℕthỏa mãnCx0+Cxx-1+Cxx-2=79.
A.x =13. B.x =17. C.x =16. D.x =12.
Câu 75:Tìm giá trịn∈ℕthỏa mãnCn+4n+1-Cn+3n=7[n+3].
A.n=15. B.n=18. C.n=16. D.n=12.
Câu 76:Tìm giá trịn∈ℕthỏa mãnCn1+Cn2+Cn3=7n2.
A.n=3. B.n=4. C.n=6. D.n=8.
Câu 77:Tính tổng S tất cả các giá trị của x thỏa mãnCx1+6Cx2+6Cx3=9x2-14x.
A.S=2. B.S=7. C.S=9. D.S=14.
Câu 78:Tìm giá trịn∈ℕthỏaCn6+3Cn7+3Cn8+Cn9=2Cn+28
A.n=18. B.n=16. C.n=15. D.n=14.
Câu 79:Tính tíchPcủa tất cả các giá trị củanthỏa mãnPnAn2+72=6[An2+2P2].
A.P=12. B.P=5. C.P=10. D.P=6.
Câu 80:Tính tíchPcủa tất cả các giá trị củaxthỏa mãn7[Ax+1x-1+2Px-1]=30Px.
A.P =7. B.P = 4. C.P = 28. D.P =14.
Câu 81:Tìm giá trịn∈ℕthỏa mãnCn+8n+3=5An+63
A.n=15. B.n=17. C.n=6. D.n = 14
Câu 82:Tìm giá trịn∈ℕthỏa mãnAx2.Cxx-1=48.
A.x=4. B.x=3. C.x=7. D.x=12.
Câu 83:Tìm giá trịn∈ℕthỏa mãnAn2-Cn+1n-1=5.
A.n=3. B.n=5. C.n=4. D.n=6.
Câu 84:Tính tíchPcủa tất cả các giá trị củanthỏa mãnAn2-3Cn2=15-5n.
A.P=5. B.P=6. C.P=30. D.P=360.
Câu 85:Tìm giá trịn∈ℕthỏa mãn3Ax4=24[Ax+13-Cxx-4].
A.x=3. B.x=1. C.x=5. D.x=1;x=5.
Câu 86:Có bao nhiêu số tự nhiênnthỏa mãnAn+44[n+2]!