TOÁN RỜI RẠC CHO HỌC SINH CHUYÊN TOÁN
Toán rời rạc là loại toán còn mới mẻ đối với học sinh THPT nói chung nhưng lại đặc biệt quan trọng đối với học sinh có năng khiếu toán .Toán rời rạc vận dụng không nhiều kiến thức toán, phần nhiều chỉ là những kiến thức toán ở trường trung học cơ sở cùng lắm là kiến thức toán đến lớp 11.Trong những năm gần đây khi công nghệ thông tin phát triển thì bộ môn này đặc biệt phát triển trên thế giới nói chung và ở Việt Nam trong các đề thi quốc gia cũng như trong các kỳ thi Ôlympíc phần toán này được sử dụng rộng rãi.Trong thời gian còn dạy các lớp chuyên toán và bây giờ thường xuyên tham gia tập huấn đội tuyển học sinh giỏi trong trường ,tôi thấy bộ môn này rất cần thiết cho học sinh ,nó giúp học sinh trong rèn luyện tư duy ,lô gíc cũng như rèn luyện sáng tạo trong học tập các môn toán khác. Toán rời rạc tuy đã phát triển trên thế giới từ rất lâu nhưng lại rất mới mẻ ở Việt Nam .Học sinh thường khó khăn khi giải các bài toán loại này phần nhiều thấy khó và sợ nó.Trong lúc đó sách tham khảo loại toán này lại hầu như không có. Thấy được điều này trong giảng dạy Tôi đã thường xuyên có ý thức sưu tầm ,phân loại trên cơ sở đó phát triển thêm những bài tương tự cũng như khuyến khích học sinh tìm tòi sáng tạo thêm. Trong bài viết này tôi mạnh dạn. Công bố những sưu tầm và những sáng tạo đó .Vì khuôn khổ qui định hạn hẹp của số trang ,trong bài viết này Tôi chỉ đề cập đến những kiến thức tối thiểu cho học sinh cần thiết khi học toán rời rạc cũng như đề xuất một số dạng bài tập.Phần 2 tiếp theo sẽ đề cập đến các cách giải khác nhau.Các em học sinh có trao đổi gì liên lạc the hòm thư: nvhthpt_chuyenlamson.
KIẾN THỨC TOÁN TỐI THIỂU
1/. Tập hợp số tự nhiên và tập hợp số nguyên
N= Z=
Sắp thứ tự thực hiện được trên tậpN,,Z trên 2 tập số tự nhiên và tập số tự nhiên khác 0 có phần tử bé nhất nhưng không có phần tử lớn nhất,tập Z không có phần tử nhỏ nhất và phần tử lớn nhất.
2/.Một số kiến thức về toán tổ hợp trong trường phổ thông
a/. Chỉnh hợp: E là một tập hợp gồm n phần tử phân biệt.
Một bộ phận gồm r phần tử phân biệt ,có kể thứ tự,các phần tử của E() được gọi là một chỉnh hợp chập r của n phần tử.
b/. Tổ hợp: Cho E là một tập hợp gồm n phần tử
Mỗi tập con gồm r phần tửcủa E được gọi là một tổ hợp chập r của n phần tử.
Chú ý phân biệt 2 khái niệm tổ hợp và chỉnh hợp ,đặc biệt là vận dụng nó vào bài toán cụ thể . Vận dụng quy tắc cộng và quy tắc nhân một cách chính xác
3/. ánh xạ:
Cho 2 tập Xvà tập Y một tương ứng sao cho mỗi x thuộc X tương ứng duy nhất với mỗi y thuộc Y gọi là một ánh xạ từ X vào Y
Cần phân biệt cho học sinh thấy sự giống nhau và sự khác nhau của khái niệm ánh xạ và khái niệm hàm số.
Đơn ánh: một ánh xạ được gọi là một đơn ánh nếu
Toàn ánh: một ánh xạ được gọi là toàn ánh, nếu
3/. Nguyên tắc Điricslê cũng như các phương pháp :
Quy nạp toán học ,
Phương pháp phản chứng
Phương pháp suy luận trực tiếp
Phương pháp Logic mệnh đềvv…
4/. Hình lồi:
+ Một đa giác là đa giác lồi khi nó nằm về một phía của đường thẳng đi qua một cạnh bất kỳ.
+ Giao khác rỗng của một hình lồi.
+ Đường kính của một hìnhvv…
MỘT SỐ BÀI TẬP THAM KHẢO: BÀI 1:Trong 1 đa giác lồi 2006 cạnh cho 2005 điểm sao cho kể cả đỉnh của đa giác không có 3 điểm nào thẳng hàng ,chia thành các tam giác không chồng lên nhau. Hỏi có bao nhiêu tam giác ?
BÀI 2: Độ dài cạnh của 1 tam giác đều lớn nhất là bao nhiêu,sao cho có thể phủ nó bởi 3 tam giác đều cạnh bằng 1?
BÀI 3: Trong 1 hình vuông cạnh bằng 1 ,chứa 1 đa giác lồi n cạnh.CMR:tồn tại 3 đỉnh của đa giác tạo thành 1 tam giác có diện tích không vượt quá .
BÀI 4:Cho 1 tập các số sắp thứ tự E=có bao nhiêu hoán vị n phần tử của E mà không có phần tử nào giữ nguyên vị trí ban đầu ?
BÀI 5:Cho 1 tập hữu hạn các số sắp thứ tự : E= có bao nhiêu hoán vị của E ,mà có 3 phần tử giữ nguyên vị trí ban đầu ?
BÀI 6: Cho tập M có 22222 phần tử .Hỏi M có hay không 50 tập con thoả mãn :
1/Mỗi phần tử của M là phần tử của ít nhất 1 trong các tập con.
2/Mỗi tập con đều có 1111 phần tử.
3/Với 2 tập Mi;Mj (i khác j) có 22 phần tử.
BÀI 7: Giả sử M là tập hợp các dãy a=(a1,a2,…an) với độ dài n cố định và ở đó ai với i= .Tích của 2 dãy a.b (b=(b1,b2,…bn)) là:
ab=(a1b1,a2b2,….,anbn). Giả sử a thuộc M và T là tập con của M và giả sử at=.CMR với mỗi tập con B của M,B gồm k phần tử đều tồn tại 1 dãy :
c=thuộc M sao cho Chứa nhiều nhất là dãy
BÀI 8:Cho 2 số nguyên dương m,n mà n+2m .Tính số bộ 3 số nguyên dương (x,y,z) Thoả mãn :x+y+z mà,y,z
BÀI 9: Giả sử m,n,k,là 3 số nguyên dương trong đó .CMR nếu
thì các số 1,2,…,n có thể chia được thành k nhóm mỗi nhóm có tổng bằng m.
BÀI 10 Cho 12 giác đều A1A2 …A12tại ghi ((-)) các đỉnh còn lại ghi dấu ((+)).
Xét phép toán f : Mỗi lần lấy 3 dấu tại 3 đỉnh của 1 tam giác cân không vuông rồi thay bằng dấu ngược lại. Hỏi với phép toán đó có thể nhận được 12 giác đều mà A1 ghi dấu ((-)) còn các đỉnh còn lại ghi dấu ((+)) hay không?
BÀI 11 :Bảng 88 điền 64 số nguyên , Xét phép toán f mỗi lần lấy các số trong hình 33 hoặc 44 rồi tăng lên 1 đơn vị . Có đúng hay không nếu nói rằng mọi bảng ban đầu ta đều có thể thu được1 bảng toàn các số chia hết cho 3.
BÀI 12:Bảng nn ô vuông (n>1) điền các số 1 và -1 ,thực hiện phép toán f .Mỗi lần thay tất cả mỗi số trong 1 ô bằng tích của nó và các ô kề cạnh với nó .sau đó xoá bảng cũ đi. Hỏi có tồn tại hay không số n>1 ,sao cho với bảng nn ban đầu tuỳ ý ,ta có thể đưa về bảng toàn số 1 .
BÀI 13: Cho bảng ô vuông mn (m,n1) ở mỗi ô của bảng điền số 1 hay -1.Tính cách điền bảng sao cho tích các số trong mỗi hàng , mỗi cột >0.
BÀI 14: Trong bảng hình vuông 20012002 điền 20012002 số nguyên dương phân biệt .Cho 2 số nguyên dương m,n sao cho :1 m 2000 ; 1 n 2001. Một ô được gọi là xấu nếu ô đó bé thua m số trong cột và n số trong hàng chứa nó .Tìm số nhỏ nhất các ô xấu .
BÀI 15: Gọi hình chữ nhật kích thước 23 hoặc 32 bị cắt bỏ 1 hình vuông 11 ở 1 góc là hình chữ nhật khuyết đơn
Gọi hình chữ nhật 23 hoặc 32 bị khuyết 2 hình 11 ở 2 góc đối diện là hình chữ nhật kép
Người ta ghép một số hình 22,một số hình khuyết đơn và một số hình khuyết kép với nhau ,sao cho không có 2 hình nào chờm lên nhau ,để tạo thành hình chữ nhật 19932000.Gọi s la tổng các hình vuông 22 và hình chữ nhật khuyết kép cần dùng trong mỗi các ghép hình trên .Tìm giá trị lớn nhất của s.
BÀI 16:Có thể ghép các hình 21và hình vuông 66 sao cho các đường ghép không tạo thành đường thẳng nối liền 2 cạnh hình vuông (cách ghép phải kín ,không chờm lên nhau)
BÀI 17:Từ các hình vuông 11;22;33 ta lập hình vuông 2323.Hỏi có ít nhất bao nhiêu hình vuông 11cần dùng .
BÀI 18:Cho 1 dãy gồm 10 dấu (-)và 10 dấu (+) ,xét phép toán như sau:
- Nếu có 2 dấu cùng loại thì thay bằng dấu (+)
- -Nếu có 2 dấu khác nhau thì thay bằng dấu (-)
Sau đó xoá 2 dấu cũ ,tiếp tục như vậy với bộ mới .Hỏi sau khi thực hiện dãy phép toán (đến lúc nào chỉ còn 1 dấu duy nhất )ta được dấu gì ?
BÀI 19:Chia 1 hình tròn thành 10 phần bằng nhau hình quạt ,tại mỗi phần để 1 viên bi .Thực hiện việc chuyển bi theo nguyên tắc :mỗi lần lấy 2 viên bi bất kỳ ,rồi chuyển sang ô bên cạnh .Hỏi sau 1 số hữu hạn lần thực hiện có thể chuỷên tất cả các viên bi về một ô hay không ?
BÀI 20: Tại đỉnh A0 của đa giác lồi A0A1…An (n0) người ta đặt n viên bi .Thực hiện phép chuyển bi như sau .Mỗi lần lấy 2 viên bi ở cùng 1 đỉnh chuyển sang 2 đỉnh kề với nó.Hãy tìm tất cả các giá trị có thể của n sao cho sau hữu hạn lần thực hiện ta có thể làm cho tại mỗi đỉnh A1A2…Anđều có 1 viên bi
BÀI 21: Cho dãy hữu hạn các số thực : x1,x2,…,xn(n 4) Lấy ra 4 số bất kỳ,rồi xếp chúng vào vị trí đó nhưng theo thứ tự ngược lại.Với dãy mới nhận được lại làm như thế .Với những giá trị nào của n thì sau hữu hạn lần thực hiện được bộ :xnxn-1…x1
BÀI 22: Trên một vòng tròn ghi 4 số 1 , 5 số 0 thực hiện phép toán :Giữa 2 số giống nhau ta ghi số 1,giữa 2 số khác nhau ta ghi số 0. Hỏi ta có thể nhận được 1 vòng tròn gồm 9 số 1 hay không ?
BÀI 23:Cho các phép toán sau :
1/có (a,b) viết (a+1;b+1)
2/có (a,b) viết (a/2,b/2) nếu a,b chẵn
3/ có (a,b),(b,c) viết (a,c)
a/ Hỏi bằng 3 phép toán này từ cặp (5,19) có thể đưa về cặp (1,50) hay (1,100) không ?
b/ Tìm tất cả số tự nhiên n>0 sao cho nhờ các phép toán trên có thể nhận được (1,n)từ (a,b) với a<b cho trước
BÀI 24: Cho (x,y) là cặp các số thực có được từ cặp (a,b) biết (x,y) là một trong 3 cặp (a+1;b+2a+1);( ( với b khác 0) hoặc với .
Bất kì. Hỏi cặp (44,1992) có thể được suy ra từ cặp (2,3) sau một số hữu hạn phép toán trên không ?
BÀI 25:Tại các điểm của vòng tròn ,ta xét n số thực không đòng thời bằng 0.Xét 4 điểm a,b,c,d liên tiếp theo chiều kim đồng hồ mà (a-b)(b-c)<0 thì ta đổi chỗ b với c.CMR phép toán trên chỉ thực hiện được hữu hạn lần
BÀI 26:Tại n điểm phân biệt trên vòng tròn ta ghi n số nguyên dương .Phép toán f: lấy số cạnh nhau ghi ước số chung lớn vào giữa rồi xoá các số đó đi .CMRsau một số hữu hạn lần ta sẽ được 1 vòng tròn số mà tất cả các số bằng nhau.
BÀI 27:Cho một số điểm xanh và một số điểm đỏ sao cho không có 3 điểm nào thẳng hàng . Một số cặp điểm được nối với nhau bằng các đoạn thẳng . Điểm A được gọi là điểm đặc biệt nếu nó có quá nửa số điểm được nối có mầu khác A. 1/2 trong hệ điểm nói trên có điểm đặc biệt thì lấy 1 điểm đặc biệt trong số đó thay bằng màu còn lại .Với bộ điểm nhận được lại làm như thế .CMR sau một số hữu hạn lần thực hiện ta sẽ có hệ điểm không có điểm đặc biệt .
BÀI 28:(Dĩ bất biến ,ứng vạn biến ) Tại mỗi đỉnh của ngũ giác lồi ta ghi các số nguyên có tổng dương .Xét phép toán f: Nếu có 3 số x,y,z,theo thứ tự đó liên tiếp theo chiều kim đồng hồ mà y<0 thì thay chúng bằng x+y,-y,z+y.Hỏi phép toán đó có vô hạn không ?
BÀI 29:Trên 1 đường thẳng điền n số 1,2,...,n thực hiện phép toán f: Nếu 3 số x,y,z, theo thứ tự đó nằm liên tiếp trên đường thẳng thì có thể đổi chúng thành x+y,-y,y+z .Hỏi có thể chuyển dãy số thành a1,a2,...,an có thứ tự mà (a1,,a2,...,an) là một hoán vị và khác với (1,2,...,n).
BÀI 30: Trong 1 dãy nhà vô hạn ,được đánh số :1,2,3,…mỗi phòng có thể có người hoặc không có người ,nhưng số người là hữu hạn .Mỗi buổi sáng 2 người ở 2 phòng liên tiếp k,k+1 nào đó sẽ thực hiện việc chuyển phòng như sau :
· Người ở phòng k chuyển sang phòng k-1 (k>1)
· Người ở phòng k+1 chuyển sang phòng k+2
CMR:Việc chuyển phòng chỉ ra hữu hạn lần.
BÀI 31: Cho n số nguyên a1,a2,…,an Mỗi lần thay đồng thời tất cả các số an+1=a1.Tìm điều kiện cần và đủ đối với bộ số nguyên ban đầu, sao cho suốt quá trình thực hiện, ta chỉ nhận được các số nguyên .
BÀI 32 Có n học sinh đứng thành vòng tròn quay mặt vào trong,mỗi em đều có 1 số kẹo không đồng thời bằng nhau .Theo hiệu lệnh của người điều khiển ,mỗi em lấy một nửa số kẹo của mình đưa cho bạn bên trái .Nếu em nào có số kẹo là một số lẻ sẽ được nhận từ cô giáo 1 cái trước khi chia.CMR làm như vậy sau 1 số hữu hạn lần mỗi em có số kẹo bằng nhau.
BÀI 33: Cho 2m giác lồi A1A2A3…A2m Bên trong lấy 1 điểm P không nằm trên 1 đường chéo nào .CMR P thuộc một số chẵn các tam giác với các đỉnh là A1;A2;….
BÀI 34: CMR tồn tại đa giác mà không thể phân ra được thành các đa giác (có thể không lồi ) là ảnh của nhau qua 1 phép tịnh tiến .
BÀI 35: CMR 1 đa giác không lồi ,không thể phân chia được thành một số hữu hạn tứ giác lõm .
BÀI 36: Cho dãy n số :a1,a2,…,an nguyên dương .Ta thực hiện các phép toán f: xoá 2 số a,b khác nhau trong dãy điền vào đó số 2ab-a-b+1. Hỏi số cuối cùng là số gì ?
BÀI 37: Trên bảng ghi :10 số 1; 10 sô 0 ;1985 số -1.Ta thực hiện các phép toán sau :
+ Bỏ 2 số 0;1 thay bằng -1
+ Bỏ 2 số -1,1 thay bằng số 0
+ Bỏ 2 số 0,-1 thay bằng số 1
Hỏi với các phương án khác nhau ,thì kết quả cuối cùng có giống nhau không ?
BÀI 38:Cho 1 dãy vô hạn các ô vuông và hữu hạn hạt đậu được đặt trong các ô vuông đó .Xét các phép chuyển như sau .Nếu có 1 ô vuông nào đó có nhiều hơn 1 hạt đậu ,thì lấy ra từ ô đó 2 hạt ,1 hạt chuyển sang ô bên trái ,1 hạt chuyển sang ô bên phải .CMR từ một cách sắp các hạt đậu cho trước thì ta chỉ thực hiện hữu hạn các phép toán và dù thứ tự thực hiện ra sao thì cũng có 1 cách duy nhất đặt các hạt đậu lúc không thể thực hiện được phép toán .
BÀI 39: Trên mặt phẳng cho n đường thẳng .Biết rằng không có 2 đường thẳng nào song song và không có 3 đường thẳng nào đồng quy .
Hãy tính số miền được tạo thành và số các đa giác lồi trong các miền này .
BÀI 40: Cho a1,a2,a3,b1,b2,b3,,c1,c2,c3.là các số thực cho trước.CMR Một trong 8 hệ bất phương trình dạng:
là vô nghiệm .
BÀI 41:Trên mặt phẳng có n4 không cùng thẳng hàng .Biết rằng cứ chọn ra 3 điểm không thẳng hàng nào cũng tìm được thứ 4 để 4 điểm này lập thành 1 hình bình hành thì n=4.
BÀI 42: CMR 1 đa giác là lồi khi và chỉ khi 4 đỉnh bất kỳ của chúng tạo nên 1 tứ giác lồi .
BÀI 43:Trên mặt phẳng cho một số n giác đều .CMR bao lồi của nó là một đa giác có không ít hơn n đỉnh .
BÀI 44:Cho 1 đa giác không tự cắt và 2 điểm không nằm trên biên sao đoạn AB không đi qua đỉnh nào của đa giác .CMR A và B cùng trong 1 miền của đa giác khi và chỉ khi AB cắt biên của đa giác tại một số chẵn điểm.
BÀI 45: CMR mọi n giác lồi không tự cắt có thể kẻ được 1 đường chéo nằm hoàn toàn trong đa giác .
BÀI 46: CMR mọi đa giác có các cạnh không tự cắt thì luôn luôn có thể kẻ được n-3 đường chéo ,đôi một không cắt nhau và nằm hoàn toàn trong đa giác ..Chứng minh rằng con số n-3 là con số lớn nhất có thể
BÀI 47: Trên mặt phẳng cho n hình lồi ,biết rằng 3 hình bất kỳ trong số đó có điểm chung .CMR tất cả n hình đều có điểm chung .
BÀI 48:Trên 1 đường thẳng cho n đoạn thẳng ,biết rằng 2 đoận thẳng bất kỳ trong số đó có điểm chung .CMR nđoạn thẳng có điểm chung .Hãy tổng quát bài toán trong không gian n chiều .
BÀI 49: CMR một họ các đa giác giác đôi một giao nhau sẽ có 1 cát tuyến chung .
BÀI 50:Trên mặt phẳng cho một số điểm mà khoảng cách giữa 2 điểm bất kỳ trong chúng không vượt quá 1 .CMR có thể phủ chúng bằng một đường tròn bán kính.
BÀI 51: Trên mặt phẳng vẽ một số hình tròn .Biết rằng có 1 đĩa hình tròn có tính chất :Với 3 hình tròn tuỳ ý trong chúng đều có thể chọn vị trí đặt đĩa sao cho nó cắt cả 3 hình tròn này .CMR tồn tại 1 vị trí đặt đĩa để nó cắt tất cả hình tròn đã cho.
BÀI 52: Trên mặt phẳng có một số hình tròn .Biết rằng có 1 cái đĩa hình tròn có tính chất với 3 hình tròn tuỳ ý trong chúng đều tồn tại 1 vị trí đặt đĩa mà phủ cả 3 hình tròn này .CMR tồn tại 1 vị trí đặt đĩa phủ tất cả hình tròn đã cho.
BÀI 53: Trên mặt phẳng có 1số đường thẳng .Biết rằng có 1 đĩa tròn có tính chất với 3 đường thẳng tuỳ ý trong chúng tồn tại cách đặt đĩa sao cho cắt cả 3 đường thẳng này .CMR tồn tại 1 vị trí đặt đĩa sao cho cắt tất cả các đường thẳng đã cho.
BÀI 54: Trên mặt phẳng có 1 hệ các hình chữ nhật có các cạnh tương ứng song song .CMR nếu 2 hình bất kỳ trong chúng có giao khác rỗng thì cả hệ có gíao khác rỗng .
BÀI 55:Trên 1 đường tròn có 1 hệ các cung <có tính chất là giao của 3 cung bất kỳ trong chúng khác rỗng CMRgiao của cả hệ khác rỗng
BÀI 56:Trên 1 đường tròn cho 1 hệ các cung <
.Biết rằng 2 cung bất kỳ giao nhau khác rỗng .CMR cả hệ có giao khác rỗng .
BÀI 57: Cho 1 hình F tuỳ ý không tự cắt ,với mỗi điểm P trong F ta ký hiệu R(P)và r(P) là khoảng cách lớn nhất và nhỏ nhất từ P đến biên của F. Đặt R= min r=Max CMR Rr , trong trường hợp nào dấu bằng diễn ra ?
BÀI 58:CMR số đường kính của 1 n giác tuỳ ý không vượt quá nmHãy chỉ ra 1 ngiác lồi có đúng n đường kính .
BÀI 59:CMR một hình khối là hình cầu khi và chỉ khi mọi thiết diện phẳng của nó đều là hình tròn .
BÀI60: CMR mọi hình đường kính d đều có thể phủ được bởi 1 hình vuông cạnh d.
T 61: Tìm số n nhỏ nhất sao cho từ n điểm nằm trong 1 hình đường kính d luôn tìm được 2 điểm có khoảng cách nhỏ hơn .
BÀI 61:CMR 1 hình đường kính d luôn có thể được phủ bởi bởi 1 hình tròn bán kính .
BÀI 62 : CMR bao lồi của 1 hình Ftuỳ ý luôn có đường kính bằng đường kính của hình F.
BÀI 63: CMR 1 hình F có đường kính d có thể được phủ bởi 1 hình tam giác đều có cạnh .
BÀI 64:Trong 1 tháng 30 ngày 1 đội bóng chuyền thi đấu mỗi ngày ít nhất 1 trận ,nhưng cả tháng chơi không quá 45 trận .CMR phải tìm được 1 giai đoạn gồm 1 số ngày liên tục nào đó trong tháng sao cho đội đó chơi đúng 14 trận .
BÀI 65:Trên mặt phẳng cho 9 điểm được nối với nhau đôi một bởi các đoạn màu xanh hoặc đỏ sao cho trong 3 điểm bất kỳ bao giờ cũng tìm được 2 điểm nối với nhau bằng 1 đoạn màu đỏ .CMR luôn tìm được 4 điểm mà các đoạn nối chúng màu đỏ .
BÀI 66:Cho góc vuông xoy ,chia góc đó thành các hình vuông đơn vị bởi các tia song song vớí ox,oy .Ký hiệu (i,j) là ô giao giữa cột i và hàng j.Đặt vào ô (1,1) 1 viên bi .Xét các bước chuyển bi như sau :Lấy 1 viên ở ô (i,j) mà các ô (i+1,j) và ô (i,j+1)không có bi và đặt vào 2 ô nói trên .Hỏi có thể làm cho các ô ; (1,1);(2,1);(3,1);(1,2);(2,2);(1,3) đều không có bi hay không ?
BÀI 67:Trên mặt phẳng có một số vết mực có tổng diện tích lớn hơn 1 .CMR luôn tồn tại 2 điểm A và B trong vết mực sao cho khoảng cách có dạng
với n là số tự nhiên .
BÀI 68: Trên mặt phẳng có 1 vết mực có diện tích <1 CMR tồn tại trên mặt phẳng 1 hệ trục toạ độ trực chuẩn sao cho không có điểm nguyên nào bị dính mực .
BÀI69:Có 10 em bé đứng trên 1 sân chơi ,biết rằng khoảng cách giữa các em bé đôi một khác nhau và mỗi em có trong tay 1 quả bóng .Sau hiệu lệnh của chị phụ trách mỗi em sẽ ném bóng của mình cho bạn gần nhất .Hỏi có ít nhất có bao nhiêu em bé có bóng trong tay ?
BÀI 70: CMR bằng 3 hình vuông cạnh bằng 4 không thể phủ được 1 hình vuông cạnh bằng 5 .Nếu các hình vuông có cạnh bằng 4 không có phần chung trong với nhau .
BÀI 71: Trong 1 đất nước ,các thành phố được nối với nhau bằng những con đường .Độ dài mỗi con đường <100km.Từ thành phố này có thể đi đến các thành phố khác theo các con đường có tổng chiều dài <100 km .Khi một trong những con đường bị cấm để sữa chữa, thì ta vẫn đi từ thành phố này đến thành phố khác trên các con đường còn lại .CMR có thể chọn các con đường này sao cho độ dài tổng cộng <300km .
BÀI 72:Trong 1 lớp học 1 em học sinh chơi thân với 1 số lẻ bạn .CMR trong lớp có có 2 em học sinh chơi thân với 1 số chẵn các bạn trong lớp .
BÀI 73:Tất cả các mặt của 1 hình khối đa diện là hình tam giác .CMR có thể tô màu các cạnh của nó bởi 2 màu xanh và đỏ sao cho 2 đỉnh bất kỳ của hình khối đa diện này ta luôn tìm được 2 đường đơn sắc (1 đỏ,1 xanh)nối chúng .
BÀI 74: Một đồ thị đơn với n 3 đỉnh và cạnh luôn có ít nhất 1 chu trình .
BÀI 75: Một đò thị đơn G với n3 đỉnh và bậc nhỏ nhất có ít nhất 1 chu trình c có độ dài :
BÀI 76: Trong mỗi ô vuông của 1 hình vuông được điền 1 chữ số sao cho các số được tạo thành trên mỗi dòng là đôi một khác nhau .CMR ta có thể bỏ đi 1 cột sao cho các số tạo thành vẫn đôi một khác nhau.
BÀI 77: Một đất nước có các thành phố được nối với nhau bằng các con đường .Biết rằng, mỗi thành phố được nối với một số chãn cac TP khác. CMR nếu lúc đó có 1 con đường bị hỏng thì từ TP này ta vẫn đến bất kỳ TP khác .
BÀI 78: Hai cạnh đối diện của 1 bàn cờ ô vuông được dán lại với nhau để thu được 1 bàn cờ hình trụ có 64 ô vuông . Có thể xếp 8 quân hậu tren bàn cờ này ,sao cho không có 2 quân hậu nào có thể ăn nhau được không ?
BÀI 79: Trong 1 hình vuông kích thước 20002000 ô vuông ,cần phải tô màu đỏ 1 số ô vuông ,sao cho mỗi ô vuông bất kỳ ( được tô màu hay không tô màu )có cạnh chung với ít nhất 1 ô màu đỏ.Số ô ít nhất cần tô màu là bao nhiêu?