8 replies to this topic

[hoang]

Cho tap A gom n phan tu khac nhau , gia su rang cac tap hop con U1,..., Um cua A thoa man ton tai so nguyen k sao cho voi moi cap i,j ta co
Card( Ui Uj )=k.

CMR: m n

[QUANVU]

Bài này khó,tôi có biết một lời giải phải dùng 2 bổ đề.

Bạn giải thế nào?

@Thực tập xong chưa?Ổn chứ hả?

[MrMATH]

Anh QV có thể send lời giải bài này cho MM được ko, MM biết 1 lời giải dùng .... đại số tuyến tính, vui miệng MM quen gọi bài này là "bài toán của quán chè" vì lý do gì thì ... các bác tự suy luận nhé

PS: lâu lâu rồi mới khuấy 1 bài lên nhỉ

[vnm]

Bài này có trên mathlinks:

http://www.mathlinks...t=Kvant&t=18437

http://www.mathlinks...=linear algebra

[MrMATH]

Bó tay, cái link thứ 2 thì ... khỏi nói rồi. Cái này là cái mà MM .. đã biết

Còn cái link 1 thì cám ơn vnm nhé

[QUANVU]

Anh QV có thể send lời giải bài này cho MM được ko, MM biết 1 lời giải dùng .... đại số tuyến tính, vui miệng MM quen gọi bài này là "bài toán của quán chè" vì lý do gì thì ... các bác tự suy luận nhé

PS: lâu lâu rồi mới khuấy 1 bài lên nhỉ

Đây này chú:

Attached Files

•  dossier_03047sol.pdf   127.54KB   49 downloads

[TieuSonTrangSi]

Bài này khó,tôi có biết một lời giải phải dùng 2 bổ đề.

Đáp án mà QUANVU gửi trên thật ra là của một bài khác (bàn về lực lượng chẵn/lẻ), khó hơn, nên mới cần 2 bổ đề Bài của hoang có cách giải dùng ma trận, tổng quát từ lời giải trên mathlinks (lời giải mathlinks chỉ cho trường hợp http://dientuvietnam...mimetex.cgi?k=1).

Gọi các phần tử của http://dientuvietnam...n/mimetex.cgi?A là http://dientuvietnam.net/cgi-bin/mimetex.cgi?a_1,a_2,\ldots,a_n. Ta xét ma trận http://dientuvietnam...n/mimetex.cgi?M gồm http://dientuvietnam...n/mimetex.cgi?n hàng, http://dientuvietnam...n/mimetex.cgi?m cột, xác định bởi

http://dientuvietnam.net/cgi-bin/mimetex.cgi?M_{ij}=1 nếu http://dientuvietnam...ex.cgi?M_{ij}=0 nếu http://dientuvietnam...x.cgi?Q=M^{T}M. Dễ thấy rằng đây là một ma trận vuông http://dientuvietnam...n/mimetex.cgi?Q khả nghịch thì khi đó http://dientuvietnam.net/cgi-bin/mimetex.cgi?\mbox{rank}Q=m và điều này sẽ kéo theo http://dientuvietnam.net/cgi-bin/mimetex.cgi?Q_{ij}=k nếu http://dientuvietnam.net/cgi-bin/mimetex.cgi?i. Thật vậy, http://dientuvietnam.net/cgi-bin/mimetex.cgi?i,j sao cho http://dientuvietnam.net/cgi-bin/mimetex.cgi?Q_{ii}=Q_{jj}=k, vì khi đó ta sẽ có http://dientuvietnam.net/cgi-bin/mimetex.cgi?\ell nào đó để http://dientuvietnam.net/cgi-bin/mimetex.cgi?Q_{\ell\ell}=k xảy ra. Với mọi chỉ số http://dientuvietnam.net/cgi-bin/mimetex.cgi?i\neq\ell thì http://dientuvietnam.net/cgi-bin/mimetex.cgi?Q_{ii}>k.

Bây giờ ta suy diễn http://dientuvietnam.net/cgi-bin/mimetex.cgi?Q như là ma trận của dạng toàn phương :

http://dientuvietnam.net/cgi-bin/mimetex.cgi?Q_{ii}, dạng toàn phương này xác định dương. Do đó, ma trận http://dientuvietnam.net/cgi-bin/mimetex.cgi?Q khả nghịch, đpcm.

- Khi hoang ra bày này (07/2005), tôi có nghĩ tới việc sử dụng ma trận như trên, nhưng lúc đó không chứng minh được Q khả nghịch :cry Đọc bài vnm dẫn trên mathlinks thì mới... tìm ra chân lý

- Tôi dời chủ đề này vào box Đại Học vì cho nó là "đại số tuyến tính" nhiều hơn là "rời rạc".

[gadget]

đọc chẳng hiểu gì cả bác quan vu dịch được không

[TieuSonTrangSi]

đọc chẳng hiểu gì cả bác quan vu dịch được không

Như mình đã nói trên, tài liệu của QUANVU tương ứng với một bài khác (dù tựa tựa). Đó là bài "Problème 3", trang 3, xin tạm dịch như sau (dùng ký hiệu của hoang) :

Cho http://dientuvietnam...n/mimetex.cgi?A một tập hợp gồm http://dientuvietnam...n/mimetex.cgi?n phần tử khác nhau, và http://dientuvietnam.net/cgi-bin/mimetex.cgi?U_1,U_2,\ldots,U_m các tập hợp con khác nhau sao cho :

+ http://dientuvietnam...metex.cgi?|U_i| lẻ với mọi ;
+ chẵn với mọi .

Chứng minh rằng .