Bài tập nguyên lý dirichlet toan roi rac năm 2024
|
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:
Giải
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à: |
