Một bài Số học - Tổ hợp

[avip]

1) Gọi $S $ là một tập con gồm $10 $ phần tử phân biệt của $\{1,...,100\} $. Chứng minh rằng $S $ có hai tập con không giao nhau với tổng các phần tử bằng nhau.

2) Tổng quát bài toán này như thế nào?

Em không chắc bài này có đúng là một bài Lý Thuyết Số không. Có gì các Mod move giùm em sang box Tổ Hợp. Em cảm ơn trước.

[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT] 

[kien10a1]

Xét tập S với 10 phần tử là tập con của ${1,2,3...100} $, S có $2^{10}=1024 $ tập con, tính tổng các phần tử của từng tập con này ta có 1024 tổng.
Mặt khác, từ điều kiện tập chứa S, các tổng này thuộc đoạn 1,995.
Suy ra tồn tại 2 tổng có giá trị bằng nhau.
Nếu 2 tổng này của 2 tập con không giao nhau, thỏa mãn.
Nếu 2 tổng này của 2 tập có phần tử chung, ta loại bỏ tất cả phần tử chung của 2 tập và được 2 tập mới thỏa mãn.
Suy ra ĐPCM.
Tổng quát thì mình nghĩ là thế này: xét tập con S có k phần tử của ${1,2,3...x} $( thực sự chỉ cần xác định số nhỏ nhất và k số lớn nhất)
Giải theo hướng trên thì chỉ cần $2^{k+1}\geqslant (2x-k+1)k $ là tập con này có 2 tập con không giao nhau, có tổng bằng nhau

có bạn nào có cách tối ưu hơn không?

[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT] 

[avip]

Để mình làm rõ đánh giá cuối của bạn chút:
1) $k \; (k \in \mathbb{N}, k \ge 2) $ cho trước, ta có $\max{x} = \left \lfloor \dfrac{k^2-k+2^{k+1}}{2k} \right \rfloor $.
2) $x \; (x \in \mathbb{N}, x \ge 3) $ cho trước, ta có $\min{k} = \left \lceil k_0 \right \rceil $ với $k_0 $ là nghiệm lớn của phương trình $2^k = \dfrac{2x+1}{2} k + \dfrac{-1}{2} k^2 $.
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]