Cho tập hợp A gồm 31 phần tử và dãy gồm m tập con của A thỏa mãn đồng thời các điều kiện sau i) Mỗi tập thuộc dãy có ít nhất hai phần tử ii) Nếu hai tập thuộc dãy có chung nhau ít nhất hai phần tử thì số phần tử của hai tập này khác nhau. Chứng minh rằng m ≤ 900

Giải thích

Từ giả thiết ta thấy m tập con thuộc dãy là phân biệt. Vì A có 31 phần tử nên số tập con có đúng 2 phần tử củaA là 2 31.30 ​ Kí hiệu a k ​ ( 2 ≤ k ≤ 31 ) là các tập có đúng k phần tử, nằm trong dãy đã cho, suy ra m = a 2 ​ + a 3 ​ + ... a 31 ​ . Xét một tập hợp có k phần tử suy ra số các tập hợp con có hai phần tử của tập đó là 2 k ( k − 1 ) ​ ⇒ a k ​ tập này sẽ có a k ​ . 2 k ( k − 1 ) ​ tập con 2 phần tử. Mà theo giả thiết với hai phần tử bất kì của A thì chúng không thể đồng thời thuộc 2 tập có k phần tử của dãy suy ra các tập con của hai phần tử nói trên là phân biệt. suy ra 2 k ( k − 1 ) ​ a k ​ ≤ 2 31.30 ​ ⇒ a k ​ ≤ 31.30. k ( k − 1 ) 1 ​ suy ra a 2 ​ + a 3 ​ + ... + a 31 ​ ≤ 31.30 ( 1.2 1 ​ + 2 + 3 1 ​ + ... + 30.31 1 ​ ) ⇒ m ≤ 31.30 ( 1 − 1 1 ​ + 2 1 ​ − 3 1 ​ + ... + 30 1 ​ − 31 1 ​ ) Vậy m ≤ 900