Câu hỏi 99
Cho $n$ là một số nguyên dương và $A$ là một tập con của $\{1,\ldots,n\}$. Một $A$-phân hoạch của $n$ thành $k$ phần là một biểu diễn $n$ dưới dạng tổng $n=a_1+\cdots+a_k$, trong đó các phần $a_1,\ldots,a_k$ thuộc $A$ và không nhất thiết phân biệt. Số phần khác nhau trong một phân hoạch như vậy là số phần tử (phân biệt) của tập $\{a_1,a_2,\ldots,a_k\}$.
Ta nói một $A$-phân hoạch của $n$ thành $k$ phần là tối ưu nếu không có $A$-phân hoạch nào của $n$ thành $r$ phần với $r\lt k$. Chứng minh rằng mọi $A$-phân hoạch tối ưu của $n$ đều chứa nhiều nhất $\sqrt[3]{6n}$ phần khác nhau.
Ta nói một $A$-phân hoạch của $n$ thành $k$ phần là tối ưu nếu không có $A$-phân hoạch nào của $n$ thành $r$ phần với $r\lt k$. Chứng minh rằng mọi $A$-phân hoạch tối ưu của $n$ đều chứa nhiều nhất $\sqrt[3]{6n}$ phần khác nhau.