Tài liệu Skkn toán một số vấn đề tập hợp

THÔNG TIN CHUNG VỀ SÁNG KIẾN 1. Tên sáng kiến MỘT SỐ VẤN ĐỀ TẬP HỢP 2. Lĩnh vực áp dụng sáng kiến: Dạy Toán cho học sinh các lớp chuyên Toán, học sinh đội tuyển thi Duyên hải và Đồng bằng Bắc Bộ, học sinh đội tuyển thi HSG quốc gia. 3. Thời gian áp dụng sáng kiến: Các năm học từ 2010 - 2011 đến 2015 – 2016. 4. Tác giả: Họ và tên: Trần Mạnh Sang Năm sinh: 1987 Nơi thường trú: Phường Vị Xuyên, thành phố Nam Định Trình độ chuyên môn: Cử nhân Toán học Chức vụ công tác: Giáo viên Toán Nơi làm việc: Trường THPT chuyên Lê Hồng Phong Địa chỉ liên hệ: Số 8C/18 Gốc Mít, thành phố Nam Định Điện thoại: 097.227.6698 5. Đơn vị áp dụng sáng kiến: Tên đơn vị: Trường THPT chuyên Lê Hồng Phong Địa chỉ: 76 Vị Xuyên, tp. Nam Định – tỉnh Nam Định Điện thoại: (0350) 364 0297 1 I. Điều kiện hoàn cảnh tạo ra sáng kiến: Mục tiêu giáo dục của chúng ta hiện nay là đào tạo những con người lao động tự chủ, năng động, sáng tạo có năng lực giải quyết những vấn đề thường gặp, góp phần xây dựng đất nước giàu mạnh, xã hội công bằng và văn minh, đưa đất nước Việt Nam tiến nhanh trên con đường phát triển hòa nhập với thế giới ở đầu thế kỉ XXI. Đứng trước tình hình đó, Bộ Giáo dục và Đào tạo, Sở Giáo dục và Đào tạo cũng như nhà trường đã đề ra nhiều biện pháp tích cực. Một trong những biện pháp đó là cải tiến chương trình dạy học, cải tiến phương pháp dạy của thầy và phương pháp học của trò, phải có cuộc cách mạng thực sự về phương pháp giáo dục, cũng như cách thức tổ chức kiểm tra chất lượng học sinh để hưởng ứng cuộc vận động của Bộ trưởng Bộ GD - ĐT về chống tiêu cực trong thi cử và bệnh thành tích trong giáo dục. Đối với bộ môn Toán - Bộ môn then chốt của khoa học tự nhiên, thì một trong những khâu quan trọng của quá trình cải tiến chương trình dạy học là tiếp nhận và giải quyết một vấn đề theo nhiều hướng khác nhau, cố gắng tìm đến bản chất của nó, từ đó có mối liên hệ giữa các bài toán riêng lẻ với nhau. Trong chương trình môn Toán cấp THPT chuyên, vấn đề tập hợp luôn là lĩnh vực quen thuộc nhưng không kém phần khó khăn với cả thầy và trò. Vấn đề này xuất hiện nhiều trong các kì thi HSG quốc gia và quốc tế, là một phần quan trọng trong việc phát hiện và bồi dưỡng các học sinh có tư chất thực sự. II. Mô tả giải pháp: 1. Mô tả giải pháp trước khi tạo ra sáng kiến Đã có rất nhiều bài toán, các đề thi HSG có xuất hiện lý thuyết tập hợp và các ứng dụng: HSG quốc gia (VMO, VNTST), đề thi quốc tế (IMO, IMC) hay các 2 kì thi của các quốc gia (China TST, USA TST,...). Việc giải quyết các bài toán này không hề đơn giản (Thường là bài khó nhất trong đề thi). Một phần khó đối với học sinh của Việt Nam chính là việc các em ít tiếp xúc với dạng toán, dẫn đến cảm giác sợ khi gặp. Vì vậy tôi viết sáng kiến này, tổng kết những kinh nghiệm, phần nào giúp các em học sinh tháo gỡ các khó khăn, nhìn nhận vấn đề đơn giản hơn, bên cạnh đó cũng mong muốn là một tài liệu tham khảo giúp đỡ các thầy cô một phần nhỏ trong quá trình giảng dạy. 3 III. Nội dung sáng kiến Mục lục 1. 2. 3. 4. 5. 6. 7. Các kiến thức cơ bản về tập hợp. Các bài toán về số phần tử của tập hợp. Các bài toán về mối liên hệ giữa các tập hợp, các phép toán tập hợp. Các bài toán về tập con của tập hợp, phân hoạch tập hợp. Các bài toán kết hợp tính chất số học. Một số định lý tập hợp (Các định lý về họ các tập con của 1 tập hợp). 6.1. Định lý Hall và SDRs 6.2. Định lý Sperner; 6.3. Định lý Erdos–Ko–Rado; 6.4. Định lý de Bruijn–Erdos. Tài liệu tham khảo. 1. Các kiến thức cơ bản về tập hợp. 2.1. Tập hợp Tập hợp là khái niệm cơ bản của toán học. Ta hiểu tập hợp qua các ví dụ như: Tập hợp tất cả các học sinh lớp 10 của trường em, tập hợp các số tự nhiên,… . Thông thường mỗi tập hợp gồm các phần tử cùng có chung một hay một vài tính chất nào đó. Nếu a là phần tử của tập hợp X, ta viết a  X . Nếu a không phải là phần tử của X, ta viết a  X . Tập rỗng là tập hợp không chứa phần tử nào, ký hiệu  . Số lượng các phần tử của tập hợp X ký hiệu là X . Người ta thường ký hiệu tập hợp bằng các cách sau: 2.2 Liệt kê các phần tử của tập hợp: 4 Ví dụ: + Tập hợp các số tự nhiên �  0,1,2,3,4,5,.... . + Tập hợp tất cả các chữ cái có trong dòng chữ: “Không có gì quý hơn độc lập tự do” là {â,c, d, đ, g, h, i, k, l, n, o, ô, ơ, u, ư, p, q, t, y}. 2.3 Chỉ rõ các tính chất đặc trưng cho các phần tử của tập hợp: Ví dụ: + Tập hợp .  B ν n �  .là tập hợp gồm các số tự nhiên không n 20 nhỏ hơn 3 và không lớn hơn 20. + Viết tập B   10, 5,0,5,10,15 bằng cách chỉ ra các tính chất đặc trưng cho các phần tử của tập hợp là  . B  x � 10 x 15, xM 5 2.4 Dùng biểu đồ Ven là đường cong kín để biểu diễn cho tập hợp Chẳng hạn mô tả tập hợp A gồm các phần tử a, b, c, d, e như sau. 2.5. Tập con và tập bằng nhau 1. Tập con Tập A được gọi là tập con của tập B và kí hiệu là A  B , nếu mọi phần tử x thuộc A đều thuộc B. Tập A được gọi là tập con thực sự của tập B, nếu A  B và tồn tại phần tử thuộc B mà không thuộc A. Ví dụ: Biểu diễn A  B , � � � � 5 2. Tập hợp bằng nhau: Hai tập A và B được gọi là bằng nhau và ký hiệu A  B , nếu A là tập con của tập B và B là tập con của tập A. 2.6. Các phép toán trên tập hợp: 1. Phép hợp các tập hợp: Hợp của hai tập hợp A và B là một tập hợp ký hiệu A  B gồm các phần tử hoặc thuộc A hoặc thuộc B. 2. Phép giao các tập hợp: Giao của hai tập hợp A và B là một tập hợp ký hiệu A  B gồm các phần tử vừa thuộc A vừa thuộc B. 3. Hiệu của hai tập hợp: Hiệu của hai tập hợp A và B là một tập hợp ký hiệu là A \ B hoặc A  B gồm các phần tử thuộc A mà không thuộc B. 4. Tích Đề - các của hai hay nhiều tập hợp Tích Đề - các của hai tập hợp A và B là một tập hợp ký hiệu là A  B được xác định như sau  . A  B  (a, b)a  A, b  B Tích Đề - các của ba tập hợp A ,B và C là một tập hợp ký hiệu là A  B  C được xác định  A  B  C  (a, b, c)a  A, b  B, c  C . 2.7. Tính chất của các phép toán trên tập hợp 6 Với mọi tập A , B và C ta có 1. Tính chất của phép hợp các tập hợp: A   A A A A A B  B A A  ( B  C )  ( A  B)  C A, B  A  B A B  A  B  A 2. Tính chất của phép giao các tập hợp: A   A A A A B  B A A  ( B  C )  ( A  B)  C A, B  A  B A B  A  B  A 3. Tính chất của hiệu hai tập hợp: A\ A ,A\ B A Nếu A  B thì B  A  CB ( A) gọi là phần bù của tập A trong B. A  (B  C )  ( A  B)  ( A  C ) 4. Luật phân phối A  ( B  C )  ( A  B)  ( A  C ) A  ( B  C )  ( A  B)  ( A  C ) 5. Luật Đ-móoc – găng A  (B  C )  ( A  B)  ( A  C ) 2.8. Tích Đề các của hai hay nhiều tập hợp 7 1. Tích Đề các của hai tập hợp Cho hai tập hợp A và B khác rỗng, tích Đề các của hai tập hợp A và B là một tập hợp ký hiệu là A  B gồm các phần tử có dạng (a; b) với a  A, b  B .   A  B  (a; b)a  A, b  B 2. Tích Đề các của nhiều tập hợp Tích Đề các của n tập hợp khác rỗng A1 , A2 ,....., An là một tập hợp được xác định như sau  A1   2  ....  An  (a1; a2 ;....; an )a1  A1 , a2  A2 ,....., an  An  3. Nhận xét: Nếu tập hợp A có m phần tử và tập B có n phần tử thì tập A  B có m  n phần tử. 8 2. Các bài toán về số phần tử của tập hợp. Ví dụ 2.1 . Cho 2010 tập hợp, mỗi tập hợp có 45 phần tử và hai tập bất kì có đúng một phần tử chung. Chứng minh rằng tồn tại một phần tử thuộc tất cả 2010 tập hợp trên. Giải Xét tập A trong số 2010 tập đã cho. A giao với 2009 tập còn lại nên tồn tại a  A là  2009   45   1  45 phần tử chung của không ít hơn tập còn lại. Vậy a thuộc các tập A, A1 , A2 ,..., A45 và trong 46 tập này không có hai tập nào có phần tử chung khác a. Ta sẽ chứng minh a thuộc tập B bất kì trong 2010 tập đã cho. Thật vậy, nếu a  B thì B có với mỗi tập A, A1 , A2 ,..., A45 một phần tử chung khác a, suy ra B có không ít hơn 46 phần tử, mâu thuẫn. Bài toán được chứng minh. Ví dụ 2.2 . Cho tập hợp X gồm 2011 phần tử. Chứng minh rằng trong sô 2012 tập con gồm 3 phần tử của X luôn tìm ra đuợc hai tập con mà chúng có chung đúng một phần tử. Giải Xét 2012 tập con gồm 3 phần tử của tập X. Phản chứng rằng với mỗi cặp hai tập con bất kì hoặc chúng không giao nhau hoặc giao nhau 2 phần tử. Ta nói tập con A và B cùng một lớp nếu A và B có đúng 2 phần tử chung. Xét 3 tập con nào đó là A, B, C. * Ta chứng minh nếu A và B cùng lớp, B và C cùng lớp thì A và C cùng lớp: 9 Giả sử A   a; b; c , B   a; b; d  . Do B và C cùng lớp nên C phải có với B hai phần tử chung, trong đó phải có a hoặc b. Lúc đó thì A ǹC nên A và C có 2 phần tử chung. Vậy A và C cùng lớp. * Như thế tất cả các tập trong 2012 tập được chia thành hai nhóm. Trong nhóm 1 hai tập bất kỳ có chung đúng hai phần tử. Trong nhóm 2 hai tập bất kỳ không giao nhau. Đối với mỗi nhóm các tập có thể xảy ra 3 trường hợp TH1: Nhóm đó có đúng 3 phần tử TH2: Nhóm đó có đúng 4 phần tử TH3: Nhóm đó có nhiều hơn 4 phần tử Xét TH1: Do nhóm chỉ có đúng 3 phần tử nên chỉ có 1 tập con Xét TH2: Do nhóm chỉ có đúng 4 phần tử nên số tập hợp trong nhóm  4 Xét TH3 : Giả sử đã chọn được 2 tập con A   a; b; c , B   a; b; d  . Tồn tại phần tử e khác a,b,c,d và thuộc tập C bất kỳ từ nhóm này. Từ điều kiện A và C cùng nhóm, B và C cùng nhóm suy ra C   a; b; e . Xét một tập D bất kỳ từ nhóm này thì tập D bị rằng buộc bởi quan hệ: A và B cùng lớp, B và D cùng lớp, C và D cùng lớp nên D chứa a và b. Kho đó số các tập trong nhóm này bằng số phần tử trong nhóm trừ đi 2 (mỗi phần tử khác a,b tương ứng với đúng 1 tập hợp chứa nó). Vậy trong mọi trường hợp thì ở mỗi nhóm số tập hợp không lớn hơn số các phần tử (mâu thuẫn với giả thiết có 2012 tập). Ta có đpcm. 10 Ví dụ 2.3 . Cho S là một tập hợp có tính chất: i) Một phần tử là một dãy 15 kí tự viết liền nhau, mà chỉ gồm hai kí tự a và b ii) Hai phần tử phân biệt của S là hai dãy khác nhau tại ít nhất 3 vị trí. 11 Chứng minh rằng số phần tử của S không vượt quá 2 . Giải Để cho đơn giản ta mã hóa a là 0, b là 1. Thế thì S đơn giản là tập các dãy nhị phân có độ dài 15 sao cho hai dãy bất kì có ít nhất ba vị trí khác nhau. Với mỗi phần tử s  S , có đúng 15+1=16 dãy nhị phân độ dài 15 (bao gồm cả s ) khác s tại nhiều nhất một vị trí. Ta kí hiệu Bs là tập các dãy như vậy (các phần tử của Bs ngoại trừ s đều không nằm trong S ). Với s, t  S phân biệt ta có Bs  Bt   vì một dãy thuộc Bs khác s tại nhiều nhất một vị trí do vậy khác t tại ít nhất 2 vị trí và như thế không thể thuộc Bt . Do đó, S .16   Bs  U Bs  215 s S s S 11 S  2 cho nên . Ví dụ 2.4 . Cho tập hợp gồm 2014 phần tử sau:  1; 2; 3;.....; 2014 . Cần loại bỏ ít nhất bao nhiêu phần tử khỏi tập hợp trên, sao cho tập hợp còn lại có tính chất: không có phần tử nào bằng tích hai phần tử còn lại khác. Giải Trước hết, ta loại bỏ các số 2, 3, 4, 5, ….., 44, và chứng minh tập các số còn lại là {1;45;46;…..;2014} thỏa mãn đề bài. 11 Thật vậy, nếu trong 2 số có một số bằng 1 thì hiển nhiên 1.x  x  y luôn đúng với mọi x  {45; 46;…..; 2014} và y  {45; 46;…..; 2014}\{x}. Nếu không số nào bằng 1, tức là x, y  {45; 46;…..; 2014} và x  y , thì xy  452  2025  2014 sẽ không thuộc tập đã cho. Như vậy, ta đã chỉ ra một cách loại bỏ 43 phần tử thỏa mãn đề bài. Bây giờ, ta xét một cách loại bỏ bất kỳ ít hơn 43 phần tử. Xét 43 bộ số: (2; 87; 2  87) (3; 86; 3  86) (4; 85; 4  85) ……………. (44; 45; 44  45) Do tất cả các số trong các bộ trên đôi một khác nhau, và ta chỉ loại bỏ ít hơn 43 phần tử, nên trong tập còn lại sẽ chứa ít nhất một trong số các bộ trên. Bộ ba số ấy sẽ không thỏa mãn đề bài, nên cách loại bỏ đang xét cũng không thỏa mãn bài toán. Vậy ta cần loại bỏ ít nhất 43 phần tử. 12 Baiuf * Cho tập hợp X  � gồm hữu hạn phần tử, ta kí hiệu min X ,max X và X lần lượt là số nhỏ nhất, số lớn nhất và số phần tử của tập X . Với mỗi số nguyên dương n  n  2  và số nguyên k thỏa mãn 1  k  n , ta S  min A  max A | A  M , A  k  đặt M   1,2,..., n , k  và gọi xk là tổng tất cả n các phần tử của Sk . Tính Đặt T    1 k 1 k 1 xk . A   a1 , a2 ,..., ak  , A '    n  1  ak ,  n  1  ak 1 ,...,  n  1  a1 . Khi đó quy tắc cho tương ứng A  A ' là một song ánh. Nhận xét: a1  min A, ak  max A  a1  max A ', ak  min A ' . Do đó tổng min, max của hai tập A, A ' là  a1  ak   2  n  1   ak  a1   2  n  1 . Từ đó, tổng min và max của tất cả các tập dạng A  A ' ( A là tập con chạy khắp M) k k là 2 xk  2  n  1 Cn  xk   n  1 Cn . n Vậy T    n  1   1 Cnk  n  1. k k 1 13 2. Các bài toán về mối liên hệ giữa các tập hợp, các phép toán tập hợp. * Ví dụ 4.1. Cho n tập hợp A1 , A2 ,..., An ( n  � ) khác rỗng, phân biệt sao cho với j  k ta có A1  Aj  Ak . Biết A1  2 . Chứng minh rằng tồn tại phần tử x thuộc ít n nhất 2 tập hợp Ai . Hướng dẫn. Chia n tập thành các tập rời nhau, mỗi tập chứa 2 tập khác A1. Xét phần tử thuộc A1, nó sẽ thuộc ít nhất 1 trong 2 tập trong mỗi cặp * Ví dụ 4.2. Tìm tất cả các tập hợp hữu hạn A  N sao cho tồn tại tập hữu hạn B   N * thoả mãn A  B và x B x   x2 x A . Hướng dẫn Gọi m là số lớn nhất trong A 1) Khi m =1 khi đó A =  1 .Ta chọn B =  1 và yêu cầu được thoả mãn 2) Khi m >2 xét số y = Ta có y =  x A  x A (x2 - x) (x2 – x)  m2- m = m (m -1) > 2m >m 14 Như thế y  A .Xét tập hợp B= A   y Ta có  x B x   x  y   x2 x A x A Vậy tập B thoả mãn yêu cầu bài toán 3) Khi m = 2 trong trường hợp này ta có hoặc A =  2 hoặc A =  1,2 Xét trường hợp A =  2 .Khi đó điều kiện của bài toán thì   x2 x A = 4. Như thế nếu tồn tại tập B thoả mãn các x2 x B / A Từ đó B A =  2 .Mâu thuẫn vì 2  A Xét trường hợp A=  1,2 . Tương tự như trên ta cũng chứng minh được rằng không tồn tại tập B thoả mãn các điều kiện của bài toán Vậy tất cả tập hợp A thoả mãn là A=  1 hoặc A là tập hữu hạn tuỳ ý mà phần tử lớn nhất lớn hơn 2. Bài 5: Cho số nguyên dương n  2 . Gọi S là tập hợp gồm n phần tử và Ai với 1  i  m là các tập con khác nhau và gồm ít nhất 2 phần tử của S sao cho từ Ai  A j   , Ai  Ak   , A j  Ak   ta suy ra được Ai  A j  Ak   . Chứng minh rằng: m  2 n 1  1. Ta chứng minh quy nạp theo n. Hiển nhiên phát biểu ở đề bài đúng khi n = 2. Giả sử n > 2 và phát biểu ở đề bàiđúng với mọi số nguyên bé hơn n. Ta xét hai trường hợp. 15 *Trường hợp 1: Không tồn tại i và j nào để cho Ai  Aj  S và Ai  A j  1 (kí hiệu T để chỉ số phần tử của tập hợp hữu hạn T). Gọi x là phần tử tuỳ ý thuộc S. Số tất cả các tập hợp A i không chứa x lớn nhất là bằng 2 n 2  1 theo giả thiết quy nạp. Số các tập con chứa x của S là 2 n 1 . Nếu x  Ai thì sẽ không có j nào để cho A j   S  AJ   x , bằng không thì phải có Ai A j  1 . Do vậy, quá lắm là một nửa các tập con chứa x của S xuất hiện dưới dạng Ai. Như thế, số lớn nhất của tập Ai là 2 n 2  1  2 n 2  2 n 1  1 . * Trường hợp 2: Tồn tại một phần tử x  S sao cho A1  A2  S và A1  A2   x Đặt A1  r  1 và A2  s  1 . Khi đó r  s  n  1 . Theo giả thiết quy nạp, số lớn nhất cả tập hợp Ai sao cho Ai  A1 là 2 r  1 . Tương tự, số lớn nhất cả tập hợp Ai sao cho Ai  A2 là 2 s  1 Nếu Ai không phải là tập con của A1 và A2 thì A1  Ai   , A2  Ai   . Vì A1  A2   , ta có A1  A2  Ai   . Như vậy ta có A1  A2  Ai   x . Do đó Ai   x   Ai  A1    Ai  A2  , ngoài ra do các tập khác rỗng  Ai  A1  ,  Ai  A2  có thể được chọn tương ứng theo 2 r  1 và 2 s  1 cách, nên số lớn nhất các tập này là  2 r  1  2 s  1 . Công thêm kết quả riêng này vào, ta nhận được số lớn nhất các tập Ai là 2 n1  1 . 12. Cho tập hữu hạn X . Ta chọn ra 50 tập con A1 , A2 ,..., A50 , mỗi tập đều chứa quá nửa số phần tử của X . Chứng minh rằng a) Tồn tại phần tử a thuộc ít nhất 26 tập đã cho. 16 b) Tồn tại tập con A của X sao cho số phần tử của A không vượt quá 5 và A ǹ Ai , i 1,50. Giả sử X  n . Tổng số các phần tử của 50 tập con Ai lớn hơn 25n nên tồn tại một phần tử a thuộc ít nhất 26 tập, chẳng hạn A1; A2 ;......; A26 . Xét tập 24 tập còn lại suy ra tồn tại ít nhất một phần tử b thuộc 13 tập, chẳng hạn A27 ; A28 ;...; A39 . Xét 11 tập con còn lại ta suy ra tồn tại c thuộc ít nhất 6 tập, chẳng hạn A40 ; A41;....; A45 . Xét5 tập còn lại ta suy ra tồn tại phần tử d thuộc ít nhất 3 tập chẳng hạn A46 ; A47 ; A48 . Xét hai tập còn lại ta suy ra tồn tại một phần tử e thuộc ít nhất hai tập . chẳng hạn A49 ; A50 . Suy ra tập A   a; b; c; d ; e thỏa mãn bài toán. 16. Cho S là một tập hợp có 2014 phần tử. Giả sử S1 , S 2 ,..., S 2013 là các tập con 2013 của S . Tìm số bộ  S1 , S 2 ,..., S 2013  sao cho 17 I i 1 Si   ? 2013 Giả sử A là số bộ  S1 , S2 ,..., S2013  phần tử là một bộ  S1 , S 2 ,..., S 2013  A2  2014 2013  sao cho I i 1 aj  thỏa mãn Si   và Aj là tập hợp mà mỗi 2013 I Si i 1 . Khi đó ta có: 2014 UA j j 1 Mặt khác ta có: Aj   220141  2013 Ai I Aj   220142  2013 …. k I j 1 Aj   22014k  2013 Âp dụng nguyên lí bù trừ ta được: A2  2014 2013   22014  2013 UA j j 1  2014  2014 1    Aj   Ai I Aj  ...   1 A1 I ... I A2014  1 i  j  2014  j 1  0  C2014  22013    22013  1  2014 2014 1  C2014  22013  2013  ...   1 2014 2014 C2014  22013  2014 2014 2014 . 2013 Vậy số bộ  S1 , S 2 ,..., S2013  sao cho I Si   i 1 18 2 bằng 2013  1 2014 . 27. Tập hợp E được xây dựng theo các qui tắc sau : i) E chứa các số 0, 12, 21. ii) Nếu a , b là các số tùy ý thuộc E và với mọi số nguyên h lớn hơn hoặc h 1 h 1 bằng số chữ số của a thì các số c  10  a.10  2 , d  2.10  a.10  1 , e  b.10h  a cũng thuộc E . Giả sử f là số thuộc E có 2011 chữ số và có tổng các chữ số bằng 2013. Hỏi trong f có mặt bao nhiêu chữ số 0 ? Gọi G là tập hợp tất cả các số được thành lập từ các chữ số 0, 1, 2 sao cho số chữ số 1 và số chữ số 2 có mặt trong các số này là như nhau. Ta chứng minh G = E. 1. Chứng minh E  G. Dùng quy nạp theo số chữ số của những số nằm trong E. Theo cách thành lập tập E thì các chữ số xuất hiện trong mọi số của E chỉ là các chữ số 0, 1, 2. Rõ ràng số có 1 chữ số nằm trong E là 0 và 0 G. Các số có 2 chữ số nằm trong E là 12, 21 và 12, 21 G. Giả sử tất cả các số nằm trong E có số chữ số không vượt quá n + 1 (n ≥ 1) đều thuộc G. Xét số x tùy ý có n + 2 chữ số nằm trong E. + Nếu x có dạng như c hay d thì nó phải bắt đầu bằng 1 (hoặc 2) và kết thúc bằng 2 (hoặc1). Xóa các chữ số đầu và cuối của x ta đươc một số x’ có không quá n chữ số nằm trong E. Theo giả thiết qui nạp x’  G. Vậy trong x số chữ số 1 và số chữ số 2 bằng nhau. Do đó x G. + Nếu x có dạng như e = b.10k + a với a, b  E và a có k chữ số, thì số chữ số của a và b không vượt quá n + 1. Suy ra a, b G. Vì vậy trong x, số chữ số 1 và số chữ số 2 bằng nhau, tức là x G. 2. Chứng minh G  E. Dùng qui nạp theo số chữ số của những số nằm trong G. Ta có số có 1 chữ số nằm trong G là 0 và 0 E. Các số có 2 chữ số nằm trong G là 12, 21 và 12, 21 E. Giả sử tất cả các số nằm trong G có số chữ số không vượt quá n + 1 (n ≥1) đều thuộc E. Xét số y tùy ý có n + 2 chữ số nằm trong G. + Trường hợp y có dạng bắt đầu bằng 1 (hoặc 2) và kết thúc bằng 0 : 19 Xóa các chữ số cuối của y ta được một số b có n +1 chữ số. Trong b số chữ số 1 và số chữ số 2 bằng nhau. Theo giả thiết qui nạp b  E. Ta có y = b.10n+2 + 0. Vì vậy y  E. + Trường hợp y có dạng bắt đầu bằng 1 (hoặc 2) và kết thúc bằng 2 (hoặc1) : Xóa các chữ số đầu và cuối của y ta được một số a có không quá n chữ số. Trong a số chữ số 1 và số chữ số 2 bằng nhau. Theo giả thiết qui nạp a E. Ta có y = 10n+1 + a.10 + 2 hoặc y = 2.10n+1 + a.10 + 1. Vì vậy y E . + Trường hợp y có dạng bắt đầu bằng 1 (hoặc 2) và kết thúc bằng 1 (hoặc 2) : Đặt g(k) = m1 – m2, với m1 là số lần xuất hiện của chữ số 1 ở k chữ số đầu của y và m2 là số lần xuất hiện chữ số 2 ở k chữ số đầu của y (1 ≤ k ≤ n + 1). Ta có g(1) = 1 (hoặc –1), g(n + 1) = –1 (hoặc 1), g (i )  g (i  1)  1 với 1 ≤ i ≤ n. Tồn tại số nguyên p sao cho 1< p < n + 1 và g(p) = 0. Lúc này y = b.10q + a, trong đó a có q chữ số với q ≤ n + 2 – p, b có n – q chữ số và a, b G. Theo giả thiết qui nạp a, b E. Vì vậy y E. Gọi mi là số lần xuất hiện chữ số i (i = 0, 1, 2) trong f. Ta có mo + m1 + m2 = 2011 và 0.mo + 1.m1 + 2.m2 = 2013. Mà m1 = m2 nên m1 = m2 = 671 và mo = 669. 20