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

[Peter Pan]

Cho tập X có n phần tử. Các tập con $a_1,a_2,..a_m$ của X đều có 3 phần tử thỏa mãn $|a_i \cap a_j|\leq 1$ với mọi $i \neq j$. chứng minh tồn tại một tập con của X không chứa bất cứ tập $a_i$ nào mà số phần tử của tập này không nhỏ hơn $[\sqrt{2n}]$

[PSW]

Cắm dùi
Chắc không? (hxthanh)

@PSW: lời quân tử nói ra như núi Thái Sơn cắm vào, ko lay chuyển

( đùa thầy thôi, chứ bài này cũ xì rồi, giờ em ngồi nhớ lại thôi, nên mới dám mạnh miệng )

-------------------
@ Alex_hoang: hề đây là đề thi đề nghị Olympic 30-4-2009 mà )

@ PSW: thôi vậy anh không phải mất công nhớ lại nữa

Bài viết đã được chỉnh sửa nội dung bởi PSW: 23-04-2012 - 18:19

[Karl Heinrich Marx]

Gọi $k$ sao cho tập hợp A thỏa đề bài có $k$ phần tử và $k$ là số lớn nhất. Khi đấy cứ lấy 2 phần tử thuộc A thì phải tồn tại duy nhất 1 phần tử thuộc tập X\A để 3 phẩn tử này lập thành 1 trong các tập đã cho cho. Như vậy gọi $f$ là một ánh xạ với 2 phần tử thuộc A ứng với 1 phần tử thuộc X\A thì $f$ là một toàn ánh. Do đó $ C_k^2 \ge n-k \Rightarrow k \ge \frac{-1+\sqrt{1+8n}}{2}$ cái này lớn hơn $[\sqrt{2n}] $thì phải :-?

Bài viết đã được chỉnh sửa nội dung bởi Karl Heinrich Marx: 23-04-2012 - 20:02