Nguyên tắc Dirichlet – toán rời rạc - lôgic
B1: Ở miền trong của một hình vuông cạnh bằng 1 có một tứ giác lồi diện tích lớn hơn
. Chứng minh rằng tồn tại một đoạn thẳng có hai đầu mút ở trên cạnh của tứ giác,
song song với cạnh của hình vuông và có độ dài lớn hơn
B2: Mỗi ô vuông đơn vị của bảng kích thước 10 x 10 [10 dòng, 10 cột] đựơc ghi một
số nguyên dương không vượt quá 10 sao cho bất kì hai số nào ghi trong hai ô chung
một cạnh hoặc hai ô chung một đỉnh của bảng là hai số nguyên tố cùng nhau. Chứng
minh rằng có số được ghi ít nhất 17 lần
B3: Cho hình vuông ABCD có AB = 14cm. Trong hình vuông có đánh dấu 76 điểm
phân biệt. Chứng minh rằng tồn tại một đường tròn có bán kính 2cm chứa trong nó ít
nhất 4 điểm trong số các điểm trên.
B4: Trong một giải đấu bóng đá, có 4 đội thi đấu vòng tròn một lượt [trong một trận,
đội thắng đựơc 3 điểm, đội hoà được 1 điểm, đội thua đượưc 0 điểm]. Khi kết thúc giải
đấu, người ta thấy có 3 đội đạt được tổng số điểm lần lượt là 6 điểm, 5 điểm và 1 điểm.
Hãy cho biết đội còn lại của giải có tổng số điểm là bao nhiêu và giải thích tại sao?
B5: Cho 13 số thực thoả mãn điều kiện tổng của 6 số bất kì đều nhỏ hơn tổng của 7 số
còn lại. Chứng minh rằng tất cả 13 số đã cho đều dương
B6: Cho S là một tập hợp gồm ba số tự nhiên có tính chất: tổng hai phần tử bất kì tuỳ ý
của S là một số chính phương [Ví dụ S = {5, 20, 44} hoặc S = {10, 54, 90} là các tập
hợp thoả mãn điều kiện trên]. C/m trong tập S không có quá một số lẻ.
B7: Cho một lưới vuông kích thước 5 x 5. Người ta điền vào mỗi ô của lưới một trong
các số: -1; 0; 1. Xét tổng của các số được tính theo từng cột, theo từng hàng và theo
từng đường chéo. C/m trong tất cả các tổng đó luôn tồn tại 2 tổng có giá trị bằng nhau
B8: Trong một hình chữ nhật có diện tích bằng 5 chứa chín hình chữ nhật nhỏ mà mỗi
hình có diện tích bằng 1. Chứng minh tồn tại 2 hình chữ nhật nhỏ có diện tích phần
chung không nhỏ hơn
B9: Đội bóng bàn của trường A thi đấu với đội bóng bàn của trường B, mỗi đấu thủ
của trường này thi đấu với mọi đấu thủ của trường kia 1 trận. Biết rằng tổng số trận
Links downloaded from ToanDHSP.COM
Bai tap toan roi rac co giai
BT Toan roi rac 1
BÀI TẬP CHƯƠNG I
Bài 1:
Số mã vùng cần thiết nhỏ nhất là bao nhiêu để đảm bảo 25 triệu máy điện thoại khác nhau.
Mỗi điện thoại có 9 chữ số có dạng 0XX-8XXXXX với X nhận giá trị từ 0 đến 9.
Giải:
Vì số mã vùng có dạng: 0XX-8XXXXX, với X nhận các giá trị từ 0 đến 9 [10 số], có 07 ký tự X
do vậy sẽ có 107 trường hợp. Do đó, theo nguyên lý Dirichlet với 10 triệu máy điện thoại thì số mã vùng
cần thiết là:
][
35,2
000.000.10
000.000.25 \=\=
⎢
⎣
⎡
⎥
⎦
⎤. Vậy số mã vùng cần thiết thỏa yêu cầu bài toán là 3.
Bài 2:
Biển số xe gồm 8 ký tự, dạng NN-NNNN-XN, ví dụ 75_1576_F1. Hai số đầu là mã tỉnh, X là
chữ cái [26 chũ cái]. N gồm các số 0, 1, …, 9. Hỏi một tỉnh nào đó cần đăng ký cho 10 triệu xe thì
cần bao nhiêu serial [X].
Giải
Bài toán này có 02 cách hiểu: serial ở đây có thể là 02 ký tự NN đầu tiên hoặc là 02 ký tự XN cuối
cùng.
Cách hiểu 1: [serial là 02 ký tự XN cuối cùng].
Hai số NN đầu là mã tỉnh, do nhà nước quy định nên không ảnh hưởng đến kết quả bài toán.
Sáu ký tự còn lại có 5 ký tự là N, như vậy có 5
10 trường hợp. Theo nguyên lý Dirichlet, số serial
X tối thiểu phải thỏa mãn: 100
000.100
000.000.10 \=
⎢
⎣
⎡
⎥
⎦
⎤. Điều này không hợp lý vì số ký tự chữ cái chỉ là 26. Do
vậy, nếu bài toán sửa lại là 1 triệu bảng số xe thì kết quả hợp lý hơn, khi đó số serial là:
10
000.100
000.000.1 \=
⎢
⎣
⎡
⎥
⎦
⎤.
Cách hiểu 2: [serial là 02 ký tự NN đầu tiên]
Bốn ký tự NNNN sẽ có 104 trường hợp, 02 ký tự XN sẽ có 26*10 = 260 trường hợp. Theo quy tắc
nhân, tổng số trường hợp sẽ là: 104*260 = 2.600.000. Do đó, theo nguyên lý Dirichlet, số serial tối thiểu
phải là:
][
484,3
000.600.2
000.000.10 \=\=
⎢
⎣
⎡
⎥
⎦
⎤.
Vậy cần 04 số serial để đăng ký đủ cho 10 triệu xe.
Bài 3:
Có bao nhiêu xâu nhị phân có độ dài 10:
- Bắt đầu bằng 00 hoặc kết thúc bằng 11.
- Bắt đầu bẳng 00 và kết thúc bằng 11.
Giải
- Bắt đầu bằng 00 hoặc kết thúc bằng 11.
Xâu nhị phân bắt đầu bằng 00 có dạng: 00.xxxx.xxxx. Ký tự x có thể là 0 hoặc 1, có 8 ký tự x do
vậy có 8
2 xâu.
Xâu nhị phân kết thúc bằng 11 có dạng: xx.xxxx.xx11. Tương tư ta cũng tính được có 8
2 xâu.
Xâu nhị phân bắt đầu bằng 00 và kết thúc bằng 11 có dạng 00.xxxx.xx11. Tương tự như trên, ta
cũng tính được có 6
2 xâu.
Vậy số xâu nhị phân bắt đầu bằng 00 hay kết thúc bằng 11 là: