Chủ đề này có 2 trả lời

[lovePearl_maytrang]

Thế này nhé, cho $S$ là tập gồm $n$ phần tử. Bây giờ bạn chọn ra từ $S$ một bộ các tập con của $S$. (Có thể chọn tùy ý không phụ thuộc vào bất cứ tiêu chuẩn nào).
Và câu hỏi sau đây nảy sinh: Tìm $k$ nhỏ nhất sao cho với mọi tập con $k$ phần tử nào của $S$ đều bao hàm một trong các tập con của bộ tập con đã đặt ra ở trên.
Ví dụ: Cho $S$ là tập các số nguyên dương từ 1 đến 15. Tìm $k$ nhỏ nhất sao cho với mọi tập con $k$ phần tử của S đều tồn tại 3 phần tử đôi một phân biệt mà tích của chúng là chính phương.
Bài toán nêu ra ban đầu rất gần với bài toán sau:tìm 1 tập con của $S$ có giao khác rỗng với mỗi tập con trong bộ tập con đã đặt ra. Câu hỏi đặt ra là có tìm được hay không một thuật toán để xác định các giá trị đó?
Chúc các bạn có thêm nhiều khám phá mới.

Bài viết đã được chỉnh sửa nội dung bởi dark templar: 16-03-2013 - 15:02

[lovePearl_maytrang]

Ví dụ: Cho S là tập các số nguyên dương từ 1 đến 15. Tìm k nhỏ nhất sao cho với mọi tập con k phần tử của S đều tồn tại 3 phần tử đôi một phân biệt mà tích của chúng là chính phương.

Bà con thử suy nghĩ bài này xem sao

[lehoan]

Đây là một bài tọán có lẽ là rất phức tạp và rất khó.Chúng ta có thể thấy là rất nhiều bài toán về vấn đề này đã được ra trong các kì thi plimpic cung như các kì thi TST.đây là một vấn đề rất hay