- Cho tập, xét tất cả các tập con của, mỗi tập hợp có 3 phần tử. - Trong mỗi tập hợp con ta chọn số bé nhất. - Xét và các tập con gồm phần tử của . - Các tập hợp con của có phần tử được chọn là ( có rất nhiều tập con có chung phần tử bé nhất).. - Cách cấu tạo các tập hợp như sau:. - Lấy , có phần tử, thì là tập hợp có phần tử trong đó số 1 là phần tử bé nhất. - Tương tự ta có. - tập con có phần tử có số bé nhất là 2. - tập con có phần tử có số bé nhất là. - Ta chứng minh:. - Khi đó với mỗi cách tô màu luôn tồn tại dây cung mà không có 2 dây cung nào cắt nhau.. - Do các điểm chỉ được tô bởi 1 trong 2 màu nên phải tồn tại 2 điểm kề nhau mà chúng được tô khác màu. - Theo giả thiết quy nạp tồn tại cách chọn cung trong số các dây cung có đầu mút là các điểm trong điểm còn lại mà không có 2 dây cung nào cắt nhau. - Như vậy tồn tại cách chọn dây cung mà không có 2 dây cung nào cắt nhau, Bổ đề được chứng minh. - Khi đó theo bổ đề tồn tại cách chọn dây cung mà mỗi dây cung có 2 đầu mút được tô bởi 2 màu khác nhau và chúng đôi một không cắt nhau. - Chứng minh rằng tập hợp có thể chia thành hai tập con không giao nhau sao cho không tập nào trong chúng chứa phần tử với và với mọi . - Giả sử gồm các phần tử với và với mọi. - Khi đó ta có , với mọi (1). - ta có do . - Suy ra tồn tại ít nhất phần tử thuộc. - Áp dụng nguyên lý Dirichlet, tồn tại ít nhất một tập chứa ít nhất 2 phần tử trong số các phần tử. - Tức là tồn tại sao cho và . - Khi đó ta có Suy ra . - Vậy không chứa các phần tử với và với mọi. - Chứng minh tương tự ta cũng có tập không chứa các phần tử với và với mọi. - Gọi là số đường thẳng thuộc và là số các đường thẳng thuộc tập . - Ta có. - Từ (1) và (2) suy ra. - Tìm tất cả các số tự nhiên sao cho trong mặt phẳng tồn tại đường thẳng mà mổi đường thẳng cắt đúng 2014 đường khác. - Chứng minh rằng tồn tại một hàng có tổng các số trong hàng đó nhỏ hơn tổng các số lớn thứ ba được chọn.. - Cho tập hợp X có 2016 phần tử. - Chứng minh tồn tại tập con A của X có số phần tử không vượt quá 6 mà , với. - Lời giải Tổng số phần tử trong 64 tập con lớn hơn . - Vì vậy tồn tại một phần tử a của tập X thuộc ít nhất 33 tập con, giả sử là X1, X2. - Xét 31 tập con còn lại, lý luận tương tự suy ra tồn tại một phần tử b của tập X thuộc ít nhất 16 tập con, giả sử là X34, X35. - Xét 15 tập con còn lại, lý luận tương tự suy ra tồn tại một phần tử c của tập X thuộc ít nhất 8 tập con, giả sử là X50, X51. - Xét 7 tập con còn lại, lý luận tương tự suy ra tồn tại một phần tử d của tập X thuộc ít nhất 4 tập con, giả sử là X58, X59, X60, X61.. - Xét 3 tập con còn lại, lý luận tương tự suy ra tồn tại một phần tử e của tập X thuộc ít nhất 2 tập con, giả sử là X62, X63.. - Với tập X64 còn lại ta lấy một phần tử f.. - Như vậy tập con A chứa các phần tử a, b, c, d, e, f thỏa mãn bài toán.. - Suy ra đpcm.. - Chứng minh rằng tồn tại ít nhất 21 hình chữ nhật với đỉnh cùng màu và các cạnh song song với các cạnh của hình vuông.. - Lấy một hàng bất kỳ, ta giả sử tồn tại ô đen và ô trắng. - Khi đó tồn tại. - Vậy tồn tại ít nhất 7.9 = 63 cặp ô cùng màu trên cùng hàng. - Tiếp theo tồn tại cặp cột. - Suy ra tồn tại 21.2 = 42 tổ hợp của màu và cặp cột. - Với tổ hợp , giả sử tồn tại ji cặp trong cùng một tổ hợp, thì tồn tại ít nhất ji – 1 hình chữ nhật cho tổ hợp này. - Vì tổng của ji ít nhất là 63 nên tồn tại ít nhất. - Vậy tồn tại ít nhất 21 hình chữ nhật thỏa mãn yêu cầu của bài toán.. - Cho tập hợp . - Cần phải loại khỏi ít nhất bao nhiêu phần tử để tập hợp còn lại có tính chất: Không phần tử nào bằng tích của hai phần tử khác.. - Loại khỏi tập hợp , tập này có 43 phần tử. - Rõ ràng tập này thỏa mãn yêu cầu: Không có phần tử nào là tích của hai phần tử khác. - 1.0 đ Ta sẽ chứng minh mọi cách tách khỏi một tập hợp có nhiều nhất 42 phần tử đều không thỏa mãn yêu cầu đề bài. - Ta có . - Suy ra. - Vì nên toàn bộ các phần tử của 43 bộ ba đều là khác nhau và đều nằm trong tập hợp. - Vì ta tách ra khỏi tối đa 42 phần tử, nên phần còn lại của (sau khi tách) phải có ít nhất một bộ ba nói trên. - 2.0 đ Kết luận: Số phần tử ít nhất cần tách khỏi là 43 phần tử. - Tồn tại hay không cách xếp sỏi sao cho ô chính giữa bảng không có sỏi và. - Vậy không tồn tại các xếp sỏi thỏa mãn điều kiện bài toán.. - Do đó: Trường hợp 1: có điểm chung với tất cả các hình tròn còn lại.. - Từ (1) ta được (đpcm) Trường hợp 2: Tồn tại hình tròn không có điểm chung với. - b) Không tồn tại hình tròn không có điểm chung với ít nhất 1 đường tròn trong các đường tròn. - Từ (1), (2) và (3) suy ra . - Gọi xâu 20 là xâu OLIMPIC nếu 2 và 0 là hai phần tử liên tiếp theo thứ tự đó ở trong xâu có độ dài đã cho ( ví dụ như xâu 2220022 có độ dài là 7 và trong đó có 1 xâu OLIMPIC). - Ta có các trường hợp sau:. - Trường hợp 1. - Trường hợp 2. - Trường hợp 3. - Trường hợp 4. - Gọi là số phần tử ở xâu H ( H ở vị trí đầu tiên trong. - Gọi là số phần tử ở xâu K ( K ở vị trí thứ hai trong. - Gọi là số phần tử ở xâu K ( K ở vị trí cuối trong. - Tìm số lớn nhất các cặp gồm 2 phần tử phân biệt của tập sao cho tổng của các cặp khác nhau là các số nguyên khác nhau và không vượt quá. - Do người thứ nói chuyện với ít nhất một cặp vợ chồng (A,B) và tồn tại hai nhóm khác nhau chứa A và chứa B nên ta có.. - Trường hợp 1 : Tồn tại sao cho.. - Giả sử . - Trường hợp 2: với mọi. - Giả sử. - Khi đó hệ trên có số phương trình ít hơn số ẩn nên tồn tại sao cho khác 0.. - Khi đó:. - Tập hợp gồm hữu hạn điểm trên mặt phẳng sao cho với mọi điểm thuộc tồn tại đúng 4 điểm thuộc có khoảng cách đến bằng 1. - Hỏi tập hợp có thể chứa ít nhất là bao nhiêu phần tử?. - Rõ ràng có ít nhất hai điểm thuộc sao cho. - Nếu tồn tại sao cho thì chứa ít nhất 9 điểm.. - +(0.50 đ) Vậy chứa ít nhất là 9 điểm. - Vậy có thể chứa ít nhất là 9 điểm.. - Tìm số nhỏ nhất trong các cặp tập hợp có giao khác tập trong 2000 tập hợp phân biệt sao cho với 3 tập hợp bất kì trong 2000 tập hợp đó đều có ít nhất một cặp tập hợp có giao khác tập. - Giải tổng quát đối với tập hợp ( trong bài).. - Ta có hình biểu diễn (K) của n tập hợp như sau: tập hợp được biểu diễn bởi điểm phân biệt trong mặt phẳng ( không có 3 điểm nào thẳng hàng), hai tập hợp có giao khác biểu diễn bởi 1 đường liền nét. - nối với hai điểm biểu diễn, hai tập hợp có giao bằng biểu diễn 1 đường không liền nét. - Kí hiệu P là tập hợp điểm, là số đoạn nối liền nét của một biểu diễn (K) thỏa giả thiết bài toán ( tức là: với 3 điểm bất kỳ của P có ít nhất một đoạn liền nét). - Ta luôn luôn có thể giả thiết rằng : Trong biểu diễn (K) tồn tại hai điểm mà đoạn nối là không liền nét. - Lấy CQ, suy ra các đoạn CA, CB phải có ít nhất một đoạn liền nét (vì đoạn AB không liền nét). - Suy ra (do. - Chứng tỏ : Tồn tại. - Chọn tập hợp để có như sau : Nhóm X gồm tập hợp giao nhau khác từng đôi một, nhóm Y gồm tập hợp giao nhau khác từng đôi một. - Mỗi tập hợp của nhóm này thì không có giao khác với bất kỳ một tập hợp của nhóm kia