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

[vuhuutiep]

Gần hết hạn gửi bài rồi, chắc ko ai gửi nữa đâu
cho 2 tập hợp điểm A và B |A|=|B| =n một số diểm của A được nối với 1 số điểm của B, tìm số lớn nhất các đoạn thẳng được nối sao cho có đúng 1 cách chia chia 2n điểm trên thành n cặp mỗi cặp gồm 1 điểm của A, 1 điểm của B sao cho 2 điểm trong 1 cặp được nối với nhau.

[vnm]

bài này có thể phát biểu lại như sau:bảng vuông n.n tô lớn nhất bao nhiêu ô
sao cho tồn tại đúng 1 bộ n ô được tô mà 2 ô bất kì ko cùng hàng hay cùng cột
Ta chứng minh $k_n=\dfrac{n(n+1)}{2}$.Giả sử bảng n.n được tô 1 số ô sao cho đ/k trên thỏa mãn
nếu mọi ô được tô có ít nhất 1 ô cùng hàng được tô thì chọn ra 1 bộ S gồm n ô thỏa mãn giả thiết sau đó xét 1 ô A trong n ô đó;tồn tại 1 ô A' được tô cùng hàng với A;chọn 1 ô B thuộc S cùng cột với A'.trong hàng chứa B lại tồn tại 1 ô B' được tô.Cứ như vậy ta xây dựng dãy A;A';B:B':C;C'... và tới lúc nào đó trở lại A thay A=A';B=B'... được 1 bộ mới vô lí
Vậy tồn tại 1 ô mà hàng chứa nó ko chứa ô được tô nào khác -> ô này thuộc S.Xóa cột và hàng chứa nó và áp dụng giả thiết quy nạp có $k_n\leq\ k_{n-1}+n$->do k_2=3 $k_n\leq\ 3+3+...+n=\dfrac{n(n+1)}{2}$
cách xây dựng suy ra từ phép c/m

Bài viết đã được chỉnh sửa nội dung bởi vnm: 13-04-2007 - 22:56

[tanlsth]

Bài này mô tả qua lí thuyết lưỡng phân cũng được
Xét 1 thành tố bậc nhất thì khi xóa đi các cạnh đó thì ở mỗi cặp gồm 4 điểm bất kì ở 2 tập đỉnh chỉ có tối đa 1 cạnh nữa suy ra có tối đa $ n+C^2_n $ cạnh tức $ \dfrac{n(n+1)}{2} $ cạnh
Cách xây dựng thì đơn giản rồi

Bài viết đã được chỉnh sửa nội dung bởi tanlsth: 17-04-2007 - 19:56

[vuhuutiep]

Mọi người nói khó hiểu quá, thực ra chứng minh bằng quy nạp cũng được,chỉ cần chỉ ra tồn tại 2 điểm được nối với nhau mà có nhiều nhất n đoạn thẳng có đầu là một trong 2 điểm trên thôi (phản chứng thôi)