5 replies to this topic

[gadget]

Cho bảng vuông n*(n-2) điền các số 1,2...n thỏa mãn điều kiện không có số nào xuất hiện trên một hàng hoặc một cột 2 lần
Chứng minh ta có thể thêm vào bảng 2 hàng(gồm các số 1,2..n) nữa sao cho tính chất trên vẫn thỏa mãn

[chuyentoan]

chắc bạn nằm trong hội đồng ra đề

[gadget]

không ai làm ah

[lehoan]

Bài toán này chỉ là một áp dụng khéo léo của định lí Hall!.
Ta xét cho bảng http://dientuvietnam...n/mimetex.cgi?n số http://dientuvietnam...x.cgi?1,2,...,n chỉ xuất hiện đúng http://dientuvietnam...n/mimetex.cgi?k lần. Bây giờ mỗi số sẽ có thể cho vào http://dientuvietnam...mimetex.cgi?n-k hàng , mỗi hàng thích hợp với http://dientuvietnam...mimetex.cgi?n-k số nên theo định lí Hall ta có thể điền số thích hợp. Nên được bảng . ĐPCM

[thinhsp]

cho tớ hỏi một chút về ĐL HALL được không

[lehoan]

Định lí: Giả sử http://dientuvietnam...tex.cgi?G(X;Y;E) là đồ thị lưỡng phân. Giả sử với mỗi http://dientuvietnam...n/mimetex.cgi?X vào http://dientuvietnam.../mimetex.cgi?Y.

Có thể phát biểu theo cách khác:

Giả sử http://dientuvietnam...?A_1;A_2;..;A_n là http://dientuvietnam...n/mimetex.cgi?n tập con của tập http://dientuvietnam.net/cgi-bin/mimetex.cgi?\{1;2;..;m\}. Khi đó điều kiện cần và đủ để tồn tại http://dientuvietnam...a_1;a_2;...;a_n thỏa mãn http://dientuvietnam.net/cgi-bin/mimetex.cgi?I\subset\{1;2;..;n\} thì