Gọi tổng của một tập hợp là tổng các phần tử của tập hợp đó. Gọi S là tập các số nguyên dương không vượt quá 15. Giả sử rằng không có 2 tập con nào của S có tổng bằng nhau. Tìm GTLN của tổng S?
Tìm GTLN của tổng S?
#1
Đã gửi 20-09-2006 - 17:49
#2
Đã gửi 31-07-2017 - 17:36
Gọi tổng của một tập hợp là tổng các phần tử của tập hợp đó. Gọi S là tập các số nguyên dương không vượt quá 15. Giả sử rằng không có 2 tập con nào của S có tổng bằng nhau. Tìm GTLN của tổng S?
$\bullet$ đầu tiên ta nhận xét là tập $\mathcal{S}$ có nhiều nhất $5$ phần tử
thật vậy giả sử $\left | S \right |\ge 6$
số tập con khác rỗng của $\mathcal{S}$ có nhiều nhất $4$ phần tử là $\begin{pmatrix} 6\\1 \end{pmatrix}+\begin{pmatrix} 6\\2 \end{pmatrix}+\begin{pmatrix} 6\\ 3 \end{pmatrix}+\begin{pmatrix} 6\\4 \end{pmatrix}=56$
trong khi đó tổng các phần tử trong mỗi tập này $\le 15+14+13+12=54$
$\Rightarrow$ tồn tại $2$ tập con của $\mathcal{S}$ có tổng các phần tử bằng nhau,giả sử là $\mathcal{A}$, $\mathcal{B}$
nếu $\mathcal{A}\cap \mathcal{B}=\varnothing$ thì mâu thuẫn với giả thiết
nếu $\mathcal{A}\cap \mathcal{B}=\mathcal{C}$ thì ta có $2$ tập $\mathcal{A}\setminus \mathcal{C},\mathcal{B}\setminus \mathcal{C}$ mâu thuẫn giả thiết
$\bullet$ do ta mong muốn có tập $\mathcal{S}$ nhiều phần tử nhất nên ta giả sử
$\mathcal{S}=\left \{ a,b,c,d,e \right \},\ a<b<c<d<e$
sau một hồi dự tính toán ta dự đoán được tập $\left \{ 8,11,13,14,15 \right \}$ là tập $\mathcal{S}$ cần tìm và giờ ta sẽ chứng minh =))
ta có
$d+e\le 14+15=29,\ c\le 13$
có $\begin{pmatrix} 5\\2 \end{pmatrix}=10$ tập con có hai phần tử của $\mathcal{S}$
trong $10$ tập này thì $\left \{ d,e \right \},\left \{ a,b \right \}$ lần lượt là $2$ tập có tổng phần tử lớn nhất là nhỏ nhất nên
$a+b\le d+e-9\le 20$
$\Rightarrow a+b+c+d+e\le 20+13+29=62\Leftrightarrow \left\{\begin{matrix} a+b=20\\c=13 \\d=14\\e=15 \end{matrix}\right.$
- chanhquocnghiem yêu thích
Đừng khóc vì chuyện đã kết thúc hãy cười vì chuyện đã xảy ra
Thật kì lạ anh không thể nhớ đến tên mình mà chỉ nhớ đến tên em
Chúa tạo ra vũ trụ của con người còn em tạo ra vũ trụ của anh
#3
Đã gửi 01-08-2017 - 16:58
Gọi tổng của một tập hợp là tổng các phần tử của tập hợp đó. Gọi S là tập các số nguyên dương không vượt quá 15. Giả sử rằng không có 2 tập con nào của S có tổng bằng nhau. Tìm GTLN của tổng S?
(Làm tiếp bài của @nhungvienkimcuong)
......................
trong $10$ tập này thì $\left \{ d,e \right \}$ và $\left \{ a,b \right \}$ lần lượt là $2$ tập có tổng các phần tử lớn nhất và nhỏ nhất nên
$a+b\leqslant d+e-9\leqslant 20$
Giả sử $a+b=20$
Vì $a< b< c\leqslant 13$ nên ta chỉ xét $2$ trường hợp sau :
+ $a=9$ ; $b=11$ : Khi đó $c,d,e$ lấy $3$ trong $4$ giá trị $12,13,14,15$ nên trong $3$ số e-d ; e-c ; d-c phải có $1$ số bằng $2$
Giả sử số đó là e-d. Khi đó ta có $b-a=e-d\Rightarrow a+e=b+d$ (loại)
Tương tự, nếu số đó là e-c hoặc d-c thì cũng loại.
+ $a=8$ ; $b=12$ : Khi đó $c=13$ ; $d=14$ ; $e=15$ và ta có $b+e=c+d$ (loại)
Từ đó suy ra $a+b\leqslant 19$.
Nếu chọn $a=8$ ; $b=11$ ta có $S=\left \{ 8,11,13,14,15 \right \}$ thỏa mãn điều kiện đề bài và tổng các phần tử của nó là $61$.
- nhungvienkimcuong yêu thích
...
Ðêm nay tiễn đưa
Giây phút cuối vẫn còn tay ấm tay
Mai sẽ thấm cơn lạnh khi gió lay
Và những lúc mưa gọi thương nhớ đầy ...
0 người đang xem chủ đề
0 thành viên, 0 khách, 0 thành viên ẩn danh