Diễn Đàn MathScope

Diễn Đàn MathScope (http://forum.mathscope.org/index.php)
-   Các Bài Toán Đã Được Giải (http://forum.mathscope.org/forumdisplay.php?f=111)
-   -   Bài tập hợp khó (http://forum.mathscope.org/showthread.php?t=319)

ghjk 18-11-2007 08:49 AM

Bài tập hợp khó
 
Cho 29 phần tử trong 1 tập S. Gọi $S_{1},S_{2},...,S_{9},S_{10} $ là 10 tập con của S(ko nhất thiết phân biệt).Biết rằng cứ lấy 5 tập bất kì trong 10 tập đó thì lun chứa S.C/m có 1 số bộ 3 tập mà tổng các phần tử lun chứa S

psquang_pbc 18-11-2007 11:45 AM

Gọi $a_1 $ là lực lượng của $S_1,a_2 $ là lực lượng của 1 tập con $S_2 $ chứa tất cả các phần tử không thuộc $S_1 $,định nghĩa cho tương tự cho a_i là lực lượng của 1 tập con $S_i $ chứa tất cả các phần tử không thuộc $S_1,S_2,..,S_{i-1} $

Ta có $a_{i_1}+a_{i_2}+a_{i_3}+a_{i_4}+a_{i_5}\ge 29,i_1,i_2,i_3,i_4,i_5\in \{1,2,3,...,10\} $

Ta sẽ chứng minh tồn tại 3 số sao cho tổng của chúng lớn hơn hoặc bằng 29.

Ta có $C^4_9\sum a_{i_j}\ge C^5_{10}.29 $

Từ đó $\frac{10}{3}(a_m+a_n+a_p)\ge 8.29 $

Hay $a_m+a_n+a_p>29 $ với $a_m,a_n,a_p $ là 3 số lớn nhất trong $a_{i_j} $

ghjk 18-11-2007 12:01 PM

Trích:

Nguyên văn bởi psquang_pbc (Post 1461)
Gọi $a_1 $ là lực lượng của $S_1,a_2 $ là lực lượng của 1 tập con $S_2 $ chứa tất cả các phần tử không thuộc $S_1 $,định nghĩa cho tương tự cho a_i là lực lượng của 1 tập con $S_i $ chứa tất cả các phần tử không thuộc $S_1,S_2,..,S_{i-1} $

Ta có $a_{i_1}+a_{i_2}+a_{i_3}+a_{i_4}+a_{i_5}\ge 29,i_1,i_2,i_3,i_4,i_5\in \{1,2,3,...,10\} $

Ta sẽ chứng minh tồn tại 3 số sao cho tổng của chúng lớn hơn hoặc bằng 29.

Ta có $C^4_9\sum a_{i_j}\ge C^5_{10}.29 $

Từ đó $\frac{10}{3}(a_m+a_n+a_p)\ge 8.29 $

Hay $a_m+a_n+a_p>29 $ với $a_m,a_n,a_p $ là 3 số lớn nhất trong $a_{i_j} $

$C^4_9\sum a_{i_j}\ge C^5_{10}.29 $
Bạn làm rõ khúc này chút nhé! Đúng chỗ đó là ok!
1 lời giải rất đẹp! Thx nhìu nhé, Quang!
PS: Bạn quên xét TH 10 b65 đó trùng nhau rùi nhỉ!:)

psquang_pbc 19-11-2007 01:01 AM

Chỗ đó là hiển nhiên mà :D

Này nhé , mỗi $a_i $ xuất hiện đúng $C_9^4 $ lần và có $C_{10}^5 $ tổng 5 số trong số các $a_i $.

Còn có trùng hay kô thì cũng chẳng ảnh hưởng gì cả :)

ghjk 23-11-2007 03:27 AM

Nếu vậy thì làm sao có được bdt trên?Y cậu LÀ TRONG 4C9 lần xuất hiện mỗi số a_i thì chứa 10C5 của 5 số đó chứ gì!Và rốt cuộc mây cái a_i1,a_i2,... là số phần tử của tập A_1,A_2,..., hay là phần ko giao(nếu ko giao thì sai chắc)!

psquang_pbc 23-11-2007 09:56 PM

Hic, lời giải đó kô sai đâu ghjk ạ, cậu hãy đọc cho kĩ xem, ở trên đó $x_i $ là cái gì, còn chỗ $C^4_9 $ và $C^5_{10} $ chỉ là 1 bước suy luận hết sức đơn giản :(

Traum 24-11-2007 07:03 PM

Muốn biết có đúng hay không thì thử làm bài này theo phương pháp trên là rõ:

Cho $X $ là tập hợp có $2n-1 $ phần tử và $A_1,..,A_{2n-1} $tập con của $X $. Biết rằng cứ $n $ tập con bất kì thì hợp $=X $. Chứng minh rằng tồn tại $n-1 $ tập con mà hợp $=X $:spiderman:

lion 26-11-2010 01:34 PM

Trích:

Nguyên văn bởi ghjk (Post 1438)
Biết rằng cứ lấy 5 tập bất kì trong 10 tập đó thì lun chứa S

Lạ ghê, S là tập mẹ của 5 tập đó mà. Có phải là xét hợp 5 tập không ạ??


Múi giờ GMT. Hiện tại là 04:13 AM.

Powered by: vBulletin Copyright ©2000-2018, Jelsoft Enterprises Ltd.

[page compression: 8.74 k/9.42 k (7.14%)]