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

[dhkhtn-tnt]

Tôi có 2 bt khá hay về hàm hoán vị:G/sử http://dientuvietnam....cgi?{1,2...n}:
1/ Hoán vị http://dientuvietnam.net/cgi-bin/mimetex.cgi?\pi được gọi là tốt nếu http://dientuvietnam.net/cgi-bin/mimetex.cgi?|\pi(i)-i|=const với http://dientuvietnam...i?i=1,2,..n.Hỏi có bao nhiêu hoán vị tốt??
2/ Hoán vị http://dientuvietnam.net/cgi-bin/mimetex.cgi?\pi được gọi là bất động mạnh tại điểmhttp://dientuvietnam.net/cgi-bin/mimetex.cgi?k<j.Hỏi có bao nhiêu hoán vị mạnh??

Bài viết đã được chỉnh sửa nội dung bởi dhkhtn-tnt: 04-08-2005 - 19:49

[dhkhtn-tnt]

Ko có ai quan tâm đên topic này sao??

[lehoan]

Tôi có 2 bt khá hay về hàm hoán vị:G/sử http://dientuvietnam....cgi?{1,2...n}:
1/ Hoán vị http://dientuvietnam.net/cgi-bin/mimetex.cgi?\pi được gọi là tốt nếu http://dientuvietnam.net/cgi-bin/mimetex.cgi?|\pi(i)-i|=const với http://dientuvietnam...i?i=1,2,..n.Hỏi có bao nhiêu hoán vị tốt??
2/ Hoán vị http://dientuvietnam.net/cgi-bin/mimetex.cgi?\pi được gọi là bất động mạnh tại điểmhttp://dientuvietnam.net/cgi-bin/mimetex.cgi?k<j.Hỏi có bao nhiêu hoán vị mạnh??

Mình mới đọc đề bài nhưng thấy ở bài 2 có gì đó chưa thống nhất.

Ở đầu đề thì ghi là bất động mạnh ở j. Ở cuối đề thì lại bắt tính số hoán vị mạnh. Vậy cần hiểu "mạnh" ở đây là gì?

[dhkhtn-tnt]

j ở đây ko phải 1 số cố địh mà

[lehoan]

Ta chứng minh nếu n lẻ thì có duy nhất 1 hoán vị tốt. Nếu n chẵn thì có http://dientuvietnam.net/cgi-bin/mimetex.cgi?1+d(\dfrac{n}{2}) hoán vị tốt. Với http://dientuvietnam...mimetex.cgi?d(k) là số các ước số của http://dientuvietnam.../mimetex.cgi?k.

Ta chứng minh nếu http://dientuvietnam...metex.cgi?2a|n. (a khác 0)

Thật vậy kí hiệu g(k) là số mà http://dientuvietnam...metex.cgi?f(g(k))=k

Theo bài ta http://dientuvietnam...imetex.cgi?|f(k)-k|=a suy ra http://dientuvietnam...mimetex.cgi?f(k)=k+a hoặc http://dientuvietnam...mimetex.cgi?f(k)=k-a
.

Suy ra http://dientuvietnam...mimetex.cgi?f(k)=k-a với http://dientuvietnam...=n;n-1;...n-a 1

Lại có : Ta có http://dientuvietnam.net/cgi-bin/mimetex.cgi?|f(g(k))-g(k)|=a suy ra http://dientuvietnam.net/cgi-bin/mimetex.cgi?|g(k)-k|=a suy ra http://dientuvietnam.net/cgi-bin/mimetex.cgi?g(k)=k+a hoặc http://dientuvietnam.net/cgi-bin/mimetex.cgi?g(k)=k-a.

Suy ra http://dientuvietnam.net/cgi-bin/mimetex.cgi?f(k)=k+a với mọi http://dientuvietnam.net/cgi-bin/mimetex.cgi?f(\{1;2;...;n-2a\})=\{1;2;...;n-2a\}

Và tương tự như trên ta có



Dẫn đến n là bội của 2a. Và cứ mỗi a thì có duy nhất 1 hoán vị f thỏa mãn

Như vậy ta có ĐPCM

[lehoan]

Nếu thế theo bạn thì ta chỉ cần tìm số hoán vị mà

http://dientuvietnam.net/cgi-bin/mimetex.cgi?i

Vì nếu tồn tại http://dientuvietnam...n/mimetex.cgi?i mà http://dientuvietnam...mimetex.cgi?f(i)=i thì dĩ nhiên đó là hoán vị mạnh

[EROS_CUPID]

Có lẽ bạn chưa đọc kĩ đề: còn có đkiện r(k) khác k với k<j

[lehoan]

Có lẽ bạn chưa đọc kĩ đề: còn có đkiện r(k) khác k với k<j

Thế này nhé:

Nếu hoán vị có điểm bất động. Gọi điểm bất động nhỏ nhất là i thì dĩ nhiên ta có

Suy ra f là hoán vị bất động mạnh

[dhkhtn-tnt]

Bài 1/ lời giải của bạn đúng rồi.Lời giải của mình là cm :Nếu http://dientuvietnam...imetex.cgi?|f(i)-i|=a
Còn bài 2/ xin lỗi vì mình đã nhớ nhầm đề:Phải là f(k)<j với k<j

Bài viết đã được chỉnh sửa nội dung bởi dhkhtn-tnt: 10-08-2005 - 11:32