Một số bài toán Tổ hợp ôn thi HSG Toán - Giáo sư Lê Anh Vinh

TỔNG HỢP MỘT SỐ BÀI TOÁN CHỌN LỌC CỦA PGS.TS. LÊ ANH VINH Bài 1. Người ta tô màu mỗi ô vuông của bảng ô vuông kích thước 8  8 bởi màu xanh lá hoặc xanh da trời sao cho có đúng a ô vuông xanh lá trong mỗi bảng 3  3 và có đúng b ô vuông xanh lá trong mỗi bảng 2  4. Tìm tất cả các giá trị có thể có của (a, b). Bài 2. Hỏi có bao nhiêu dãy số tự nhiên thỏa mãn 1  a1  a2  ...  a11  2015 và thỏa mãn ai  i 2 (mod12) với 1  i  11 ? Bài 3. Một ổ khóa có 16 chìa được xếp thành một bảng 4  4 mà mỗi chìa có 2 hướng là ngang và dọc. Để mở được ổ khóa này, tất cả các chìa đều phải nằm dọc. Biết rằng khi 1 trong 16 chìa khóa được xoay, tất cả các chìa cùng hàng và cột của nó cũng được xoay theo (ngang thành dọc, dọc thành ngang). Chứng minh rằng cho dù vị trí ban đầu là thế nào, ta đều luôn có thể mở được ổ khóa này. Các số tự nhiên 0,1,2,3,... được điền vào bảng ô vuông kích thước 2015 2015 (mỗi ô một số), bắt đầu từ số 0 ở chính giữa bảng, đến các số tiếp theo được điền theo hình xoắn ốc ngược chiều kim đồng hồ như hình vẽ bên dưới: 1) Biết rằng các cột của bảng được đánh số từ 1 đến 2015 từ trái sang phải và các dòng của bảng được đánh số từ 1 đến 2015 theo thứ tự từ trên xuống dưới. Hỏi theo cách điền trên thì số 2015 nằm ở dòng nào, cột nào? 2) Người ta cho phép thực hiện thao tác sau: Đầu tiên, thay số 0 ở giữa bảng bằng số 14. Mỗi lần sau đó, người ta sẽ chọn ra 12 ô vuông liên tiếp thuộc cùng hàng, hoặc 12 ô vuông liên tiếp thuộc cùng cột, hoặc 12 ô vuông thuộc một bảng hình chữ nhật 3 4 rồi cộng thêm 1 vào tất cả các ô được chọn (mỗi lần chỉ được chọn 1 trong 3 loại hình trên). Hỏi sau một số hữu hạn lần, có thể làm cho tất cả các ô vuông của bảng đã cho đều chia hết cho 2016 được không? 1 Bài 4. Cho tập hợp X có n phần tử và m tập con khác rỗng T1 , T2 ,..., Tm thỏa mãn: i/ Ti  4, i  1, m . ii/ Với mọi i, j  X thì tồn tại duy nhất k sao cho (i, j )  Tk . iii/ Với mọi 1  i  j  m thì Ti  T j  1 . Tính các giá trị có thể có của m, n . Bài 5. Tìm số các dãy số tự nhiên tăng ngặt thỏa mãn đồng thời các điều kiện: i. ii. Số hạng đầu tiên là 0 và số hạng cuối cùng là 15. Trong 2 số hạng liên tiếp, có đúng 1 số chẵn. Bài 6. Cho 2015 tập con tùy ý A1 , A2 ,..., A2015 của tập hợp 1, 2,3,...,1000 thỏa mãn Ai  2 với i  1, 2015 và Ai  Aj  1 với mỗi 1  i  j  2015 . Chứng minh rằng k  3 là số lượng nhỏ nhất các màu có thể dùng để tô các phần tử của tập hợp 1, 2,3,...,1000 sao cho mỗi tập con Ai thì đều có ít nhất 2 phần khác màu. Bài 7. Tìm số các bộ 6 phần tử (a1 , a2 , a3 , a4 , a5 , a6 ) gồm các số nguyên dương phân biệt thỏa mãn đồng thời các điều kiện sau: i. a1  a2  a3  a4  a5  a6  30 ; ii. Có thể viết các số a1 , a2 , a3 , a4 , a5 , a6 lên trên cạnh của một lục giác sao cho sau một số hữu hạn các bước chọn 1 đỉnh nào đó của lục giác rồi thêm 1 vào 2 số viết ở cạnh xuất phát từ đỉnh đó thì ta có thể thu được trạng thái tất cả các số trên cạnh lục giác bằng nhau. Bài 8. Chứng minh rằng tồn tại vô hạn hợp số n sao cho 7n1  3n1 chia hết cho n. Bài 9. Hamza và Majid chơi một trò chơi trên một bảng hình chữ nhật ngang có kích thước 3  2015 . Họ chơi luân phiên và Hamza đi trước. Biết rằng: - Hamza được tô màu 3 ô vuông trên một bảng hình chữ nhật nằm ngang kích thước 1 3. - Majid được tô màu 3 ô vuông trên một bảng hình chữ nhật nằm dọc kích thước 3 1. Biết rằng không ai được tô lên ô vuông đã tô trước đó và người nào đến lượt mình mà không tô được thì thua. 2 Hỏi ai trong Hamza và Majid, luôn có chiến lược để thắng cho dù đối phương chơi thế nào đi nữa? Chiến lược đó là gì? Bài 10. Gọi S là số nguyên dương chia hết cho tất cả các số từ 1 đến 2015 và a1 , a2 ,..., ak là các số trong tập hợp 1, 2,3,..., 2015 (không nhất thiết phân biệt) sao cho 2S  a1  a2  ...  ak . Chứng minh rằng có thể chọn ra từ các số a1 , a2 ,..., ak một vài số sao cho tổng của chúng đúng bằng S . Bài 11. Tìm số các xâu nhị phân S độ dài 2015 sao cho với mỗi xâu con I1 , I 2 có cùng độ dài của S (không nhất thiết rời nhau), ta đều có: - Tổng các số trên I1 chênh lệch so với tổng các số trên I 2 không quá 1 đơn vị. - Nếu I1 ở bìa trái của S thì tổng các số trên I1 không lớn hơn tổng các số trên I 2 . - Nếu I 2 ở bìa phải của S thì tổng các số trên I 2 không nhỏ hơn tổng các số trên I1 . Bài 12. Người ta tô màu một đa giác đều A1 A2 ... A20 mà trong đó có 10 đỉnh được tô màu đen, 10 đỉnh được tô màu xanh. Xét tập hợp gồm đường chéo A1 A4 và các đường chéo có cùng độ dài với A1 A4 . 1. Chứng minh rằng trong S , số đường chéo có 2 đỉnh được tô đen bằng với số đường chéo có 2 đỉnh được tô xanh. 2. Tìm tất cả số lượng có thể có của các đường chéo có 2 đỉnh được tô đen trong S . Bài 13. Cho 4 số thực x, y, z, t và đặt (a, b, c, d ) là một hoán vị nào đó của ( x, y, z, t ) . Ta xây dựng dãy ( xn ),( yn ),( zn ),(tn ) như sau: x1  a  b , y1  b  c , z1  c  d , t1  d  a . Các số x2 , y2 , z2 , t2 cũng được xây dựng tương tự như thế (xét hoán vị của số hạng hiện tại rồi lấy các chênh lệch cho bộ số hạng tiếp theo). Biết rằng tồn tại n sao cho xn  x, yn  y, zn  z, tn  t. Tìm tất cả các giá trị có thể có của ( x, y, z, t ). 3 Hướng dẫn giải. Bài 1. Bài 2. 4 Bài 3. 1) Ta có các nhận xét sau: i. Trong một bảng ô vuông con có kích thước lẻ (2n 1) (2n 1) và có tâm là ô chứa số 0, tất cả (2n 1)2 số từ 0 đến (2n 1)2 1 đều được điền và cột đầu tiên tính từ trái sang của bảng này chứa 2n 1 số lớn nhất (số lớn nhất là (2n 1)2 1 nằm cuối cột đó). ii. Số 0 nằm ở hàng 1008, cột 1008 của bảng. Từ đó, ta thấy rằng: Vì 2015 452 2025 nên số này nằm trong bảng ô vuông 45 45 và số lớn nhất trong bảng này là 2024. Số 2024 nằm ở cột 1 của bảng này, tương ứng là cột 1008 22 986 của bảng đã cho. Số 2024 nằm ở dòng 45 của bảng này, tương ứng là dòng 1008 22 1030 của bảng. Do 2024 2015 9 nên số 2015 sẽ nằm cao hơn số 2024 là 9 dòng, suy ra số 2015 nằm ở dòng thứ 1030 9 1021. 5 Vậy số 2015 nằm ở dòng thứ 1021 và cột thứ 986 của bảng. 2) Sau bước thay 0 bởi 14, ta thấy tổng các số của bảng là: 14 1 2 3 ... 2015 2 1 14 20152 20152 1 2 . Dễ thấy số này chia 4 dư 2. Trong thao tác cộng các số trong 12 ô (bất kể nằm trên hàng nào, cột nào) của bảng thì tổng các số tăng lên đúng 12 đơn vị. Suy ra số dư của tổng các số trên bảng khi chia cho 4 là bất biến trong suốt quá trình. Để bảng có tất cả các số chia hết cho 2016 thì dễ thấy tổng của chúng phải chia hết cho 4, đây là điều không thể xảy ra. Vậy câu trả lời là phủ định. Bài 4. Ta sẽ tính số bộ (i, j, T ) mà (i, j )  T . Xét các cặp (i, j )  X mà i  j thì có tất cả Cn2 cặp. Ta có Ti  4 nên với mỗi tập Ti thì có sự lặp lại C42  6 lần, suy ra m  n(n  1) . 12 Đặt T1  a1 , a2 , a3 , a4  là một tập hợp nào đó trong các tập hợp đã cho. Xét ak  X mà ak  a1 , a2 , a3 , a4 . Với mỗi bộ (ak , ai ) thì ta có 1 tập T j mà mỗi tập tính 3 lần, suy ra số tập là Suy ra m  1  n4 . 3 4(n  4) . Từ đây ta được 3 n(n  1) 4(n  4)  1  (n  4)(n  13)  0 . 12 3 Với n  4 thì m  1 . Với n  13 thì m  13 . Trong cả 2 trường hợp, ta đều dễ dàng xây dựng được mô hình thỏa mãn. Bài 5. 6 Bài 6. Bài 7. 7 Bài 8. 8 Bài 9. Bài 10. 9 Bài 11. 10 11 Bài 12. 12 Bài 13. 13 14 15