Cho một bộ bài gồm 52 quân bài bình thường, gồm các quân Át, 2, 3,..., J, Q, K và 4 chất Bích, Nhép, Rô, Cơ. Bạn Hiền chia bộ bài thành 13 bộ 4 con một cách ngẫu nhiên. Chứng minh rằng Hiền có thể sắp xếp lại 13 bộ của mình sao cho bộ thứ nhất chứa con Át, bộ thứ 2 chứa con 2, bộ thứ 3 chưa con 3,...v...v..., bộ cuối cùng chứa con K.
cứ $\text{Hall}$ mà lần thôi anh nhỉ =))
ta quy định $\text{Át,J,Q,K}$ lần lượt là các số $1,11,12,13$ nên ta có tổng cộng $13$ số khác nhau và mỗi số xuất hiện $4$ lần trong tổng cộng $52$ số
ta gọi $13$ bộ lần lượt là $\mathcal{A}_1,\mathcal{A}_2,...,\mathcal{A}_{13}$ với $\left | \mathcal{A}_i \right |=4,i=\overline{1,13}$
theo đề bài ta chỉ cần chứng minh $\exists a_1,a_2,..,a_{13}$ tương ứng thuộc $\mathcal{A}_1,\mathcal{A}_2,...,\mathcal{A}_{13}$ sao cho $a_i\neq a_j,i\neq j$
theo định lý $\text{Hall}$ thì ta chỉ cần chứng minh
$\left | \mathcal{A}_{i_1}\cup \mathcal{A}_{i_2}\cup ...\cup \mathcal{A}_{i_k} \right |\ge k,\ \ \forall k\le 13$
với tập $\mathcal{A}=\mathcal{A}_{i_1}\cup \mathcal{A}_{i_2}\cup ...\cup \mathcal{A}_{i_k}$ có tổng cộng $4k$ số (ở đây chưa trừ đi các số bị lặp)
mà mỗi số xuất hiện nhiều nhất trong $4$ tập nên
$\left | \mathcal{A} \right |\ge \frac{4k}{4}=k$
do đó ta có $\text{Q.E.D}$
Bài viết đã được chỉnh sửa nội dung bởi nhungvienkimcuong: 23-08-2017 - 16:31