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

[thangde.]

Cho n là số nguyên dương lớn hơn 1.Tìm số hoán vị http://dientuvietnam...mimetex.cgi?p(1)...p(n) của http://dientuvietnam...x.cgi?{1;2...n} thỏa mãn với mọi

Bài viết đã được chỉnh sửa nội dung bởi thangde.: 01-11-2006 - 19:55

[thangde.]

đáp số của bài này là 2 với n=2;http://dientuvietnam...{n 1} F_{n-1} 2 với n lớn hơn 2
bài này có 7 ngừoi làm đựơc trong kì thi

[tmbtw]

đáp số của bài này là 2 với n=2;http://dientuvietnam...{n 1} F_{n-1} 2 với n lớn hơn 2
bài này có 7 ngừoi làm đựơc trong kì thi

BÀi này dùng cách gì vậy ?

[tanlsth]

Truy hồi bạn ạ

[tmbtw]

Truy hồi bạn ạ

Mình cũng đã nghĩ là truy hồi (Với hầu hết dạng này) nhưng với bài này (tuy chưa làm )nhưng mình nghĩ là có vẻ hơi phức tạp (vì n thay đổi )
Để về xem đã

[tanlsth]

đáp số của bài này là 2 với n=2;http://dientuvietnam...{n 1} F_{n-1} 2 với n lớn hơn 2
bài này có 7 ngừoi làm đựơc trong kì thi

Kết quả này sai rồi
Đúng phải là
Trong đó

Chẳng hạn với thì có đúng 10 hoán vị thỏa mãn mà theo kết quả của bạn chỉ có 9 hoán vị

[manutd]

Kết quả này sai rồi
Đúng phải là
Trong đó

Chẳng hạn với thì có đúng 10 hoán vị thỏa mãn mà theo kết quả của bạn chỉ có 9 hoán vị

Mới chỉ tìm được 9 hoán vị với n=4 thôi, là thế này nhá:
(1,2,3,4) (1,2,4,3) (1,3,2,4)
(2,1,3,4) (2,1,4,3) (2,3,4,1)
(4,1,2,3) (4,2,3,1) (4,3,2,1)

[manutd]

Mấy cái đầu hơi đặc biệt nên viết cho cụ thể.
Gọi số hoán vị cần tìm là http://dientuvietnam...mimetex.cgi?f(n). http://dientuvietnam...mimetex.cgi?f(2)=2,f(3)=6,f(4)=9.
Gọi http://dientuvietnam...mimetex.cgi?A_n là số hoán vị có http://dientuvietnam...mimetex.cgi?p(n)=n
http://dientuvietnam...mimetex.cgi?B_n là số hoán vị có http://dientuvietnam...mimetex.cgi?p(n)=n-1
http://dientuvietnam...mimetex.cgi?C_n là số hoán vị có http://dientuvietnam...mimetex.cgi?p(n)=1
Bây giờ ta tìm cách thêm phần tử http://dientuvietnam...mimetex.cgi?n 1 vào hoán vị (ứng với http://dientuvietnam...n/mimetex.cgi?n) để được một hoán vị ứng với http://dientuvietnam.net/cgi-bin/mimetex.cgi?n+1.
Ta có công thức truy hồi :
http://dientuvietnam.net/cgi-bin/mimetex.cgi?A_n=A_{n-1}+B_{n-1}
http://dientuvietnam.net/cgi-bin/mimetex.cgi?B_n=A_{n-1}
Suy ra http://dientuvietnam.net/cgi-bin/mimetex.cgi?B_{n+1}=A_n=A_{n-1}+B_{n-1}=B_n+B_{n-1}, với http://dientuvietnam.net/cgi-bin/mimetex.cgi?B_3=2,B_4=3. Vậy http://dientuvietnam.net/cgi-bin/mimetex.cgi?A_n+B_n=B_{n+2}
Các hoán vị có http://dientuvietnam.net/cgi-bin/mimetex.cgi?p(n)=1 có dạng: http://dientuvietnam.net/cgi-bin/mimetex.cgi?2,3,\ldots,n-1,n,1 hoặc http://dientuvietnam.net/cgi-bin/mimetex.cgi?n,p(2),p(3),\ldots,p(n-1),1. Khi đó http://dientuvietnam.net/cgi-bin/mimetex.cgi?(p(2)-1,p(3)-1,\ldots,p(n-1)-1) là một hoán vị ứng với http://dientuvietnam.net/cgi-bin/mimetex.cgi?n-2 và có http://dientuvietnam.net/cgi-bin/mimetex.cgi?A_{n-2}+B_{n-2}=B_{n}.
KL. http://dientuvietnam.net/cgi-bin/mimetex.cgi?f(n)=B_{n}+B_{n+2}, với http://dientuvietnam.net/cgi-bin/mimetex.cgi?B_n xác định như trên.
hi@: ai ở KHTN làm ơn post đáp án lên cho em khảo bài với.

[thangde.]

gọi http://dientuvietnam...mimetex.cgi?u_n là số hoán vị thỏa mãn http://dientuvietnam...metex.cgi?p_n=n thì có http://dientuvietnam...tex.cgi?u_{n-1} hoán vị thỏa mãn
nếu http://dientuvietnam...->n=p_{n-1}->có http://dientuvietnam...tex.cgi?u_{n-2} hoán vị thỏa mãn
->http://dientuvietnam...=2->u_n=F_{n 1}
Gọi s_n là số hoán vị thỏa mãn http://dientuvietnam...n=p_n;n=p_{n-1} hoặc http://dientuvietnam...metex.cgi?n=p_1
_nếu http://dientuvietnam...ex.cgi?n=p_n;ta có http://dientuvietnam...1,p_2...p_{n-1} là hoán vị của http://dientuvietnam.net/cgi-bin/mimetex.cgi?1,2...n-1 thỏa mãn http://dientuvietnam.net/cgi-bin/mimetex.cgi?u_{n-1} hoán vị
_nếu http://dientuvietnam.net/cgi-bin/mimetex.cgi?n=p_{n-1}->p_n=n-1 hay http://dientuvietnam.net/cgi-bin/mimetex.cgi?p_n=1
+http://dientuvietnam.net/cgi-bin/mimetex.cgi?p_n=n-1 thì http://dientuvietnam.net/cgi-bin/mimetex.cgi?1,2..p_{n-2} là hoán vị của http://dientuvietnam.net/cgi-bin/mimetex.cgi?1,2...n-2 thỏa mãn http://dientuvietnam.net/cgi-bin/mimetex.cgi?u_{n-2} hoán vị
+http://dientuvietnam.net/cgi-bin/mimetex.cgi?p_n=1->p_1=2->p_2=3...p_{n-2}=n-1->1 hoán vị
_nếu http://dientuvietnam.net/cgi-bin/mimetex.cgi?n=p_{1}->p_n=1 hoặc http://dientuvietnam.net/cgi-bin/mimetex.cgi?p_n=n-1
+http://dientuvietnam.net/cgi-bin/mimetex.cgi?p_n=1->p_2...p_{n-1} là hóan vị của http://dientuvietnam.net/cgi-bin/mimetex.cgi?2,3...n-1 thỏa mãn http://dientuvietnam.net/cgi-bin/mimetex.cgi?u_{n-2} hoán vị
+http://dientuvietnam.net/cgi-bin/mimetex.cgi?p_n=n-1->p_{n-1}=n-2...p_2=1->1 hoán vị
->http://dientuvietnam.net/cgi-bin/mimetex.cgi?s_n=u_{n-1}+2u_{n-2}+2=u_n+u_{n-1}+2=F_{n+1}+F_{n-1}+2

Bài viết đã được chỉnh sửa nội dung bởi thangde.: 11-11-2006 - 08:50

[tanlsth]

Uh về xem lại thì mình nhầm một chỗ
Lời giải như trên là hoàn toàn đúng rồi

[dangngocthanh]

http://dientuvietnam.net/cgi-bin/mimetex.cgi?B_n=A_{n-1}

chỗ này phải là http://dientuvietnam...i?B_n=A_{n-1} 1

[manutd]

góp ý một tí:
1. chữ "hay" thay bằng chữ "hoặc" vì hai chữ này ý nghĩa khác nhau, tránh nhầm lẫn.
2. cách gọi có vấn đề.
Nói chung lời giải này ổn rồi, có lẽ đáp án là đây!
@ cách mình sai ở đâu hở trời?

[tanlsth]

Có lẽ cách của bác sai ở chỗ xét trường hợp chưa hết
Tôi chưa xem hết nhưng có lẽ thế
Bài này cứ thẳng băng theo cách xét truy hồi là ra ấy mà

[MrLonely]

gọi http://dientuvietnam...mimetex.cgi?u_n là số hoán vị thỏa mãn http://dientuvietnam...metex.cgi?u_n=n thì có http://dientuvietnam...tex.cgi?u_{n-1} hoán vị thỏa mãn
nếu http://dientuvietnam...->n=u_{n-1}->có http://dientuvietnam...tex.cgi?u_{n-2} hoán vị thỏa mãn
->http://dientuvietnam...=2->u_n=F_{n 1}
Gọi s_n là số hoán vị thỏa mãn http://dientuvietnam...n=s_n;n=s_{n-1} hay http://dientuvietnam...metex.cgi?n=s_1
_nếu http://dientuvietnam...ex.cgi?n=s_n;ta có http://dientuvietnam...1,s_2...s_{n-1} là hoán vị của http://dientuvietnam.net/cgi-bin/mimetex.cgi?1,2...n-1 thỏa mãn http://dientuvietnam.net/cgi-bin/mimetex.cgi?u_{n-1} hoán vị
_nếu http://dientuvietnam.net/cgi-bin/mimetex.cgi?n=s_{n-1}->s_n=n-1 hay http://dientuvietnam.net/cgi-bin/mimetex.cgi?s_n=1
+http://dientuvietnam.net/cgi-bin/mimetex.cgi?s_n=n-1 thì http://dientuvietnam.net/cgi-bin/mimetex.cgi?1,2..s_{n-2} là hoán vị của http://dientuvietnam.net/cgi-bin/mimetex.cgi?1,2...n-2 thỏa mãn http://dientuvietnam.net/cgi-bin/mimetex.cgi?u_{n-2} hoán vị
+http://dientuvietnam.net/cgi-bin/mimetex.cgi?s_n=1->s_1=2->s_2=3...s_{n-2}=n-1->1 hoán vị
_nếu http://dientuvietnam.net/cgi-bin/mimetex.cgi?n=s_{1}->s_n=1 hay http://dientuvietnam.net/cgi-bin/mimetex.cgi?s_n=n-1
+http://dientuvietnam.net/cgi-bin/mimetex.cgi?s_n=1->s_2...s_{n-1} là hóan vị của http://dientuvietnam.net/cgi-bin/mimetex.cgi?2,3...n-1 thỏa mãn http://dientuvietnam.net/cgi-bin/mimetex.cgi?u_{n-2} hoán vị
+http://dientuvietnam.net/cgi-bin/mimetex.cgi?s_n=n-1->s_{n-1}=n-2...s_2=1->1 hoán vị
->http://dientuvietnam.net/cgi-bin/mimetex.cgi?s_n=u_{n-1}+2u_{n-2}+2=u_n+u_{n-1}+2=F_{n+1}+F_{n-1}+2

gọi http://dientuvietnam.net/cgi-bin/mimetex.cgi?u_n là số hoán vị thỏa mãn http://dientuvietnam.net/cgi-bin/mimetex.cgi?u_n=n thì có http://dientuvietnam.net/cgi-bin/mimetex.cgi?u_{n-1} hoán vị thỏa mãn

đọc ngay 2 dòng đã chả hiểu gì. Bác nào giải thích rõ giùm em với.

[manutd]

không hiểu là phải thôi, tại thangde viết lẫn lộn cả. Chỗ mà bạn hỏi là chứ không phải . Phần sau cũng mắc lỗi này.

[MrLonely]

vậy bác Manutd có thể viết lại hết lời giải này cho anh em được không? chứ ngồi dịch lời giải bác thangde thì chắc chết mất

[manutd]

thangde viết như thế là chi tiết lắm rồi, mấy bác chịu khó đọc là ok, loại truy hồi này cũng không có đặc biệt gì, nhớ sửa cái lỗi mà tôi nói ở trên là xong!
@thangde: vô đây mà giải quyết hậu quả đi!

[MrLonely]

ồ , đọc kỹ lại thì cũng hiểu rồi cám ơn bác manutd nhé.

[thangde.]

Mấy cái đầu hơi đặc biệt nên viết cho cụ thể.
Gọi số hoán vị cần tìm là http://dientuvietnam...mimetex.cgi?f(n). http://dientuvietnam...mimetex.cgi?f(2)=2,f(3)=6,f(4)=9.
Gọi http://dientuvietnam...mimetex.cgi?A_n là số hoán vị có http://dientuvietnam...mimetex.cgi?p(n)=n
http://dientuvietnam...mimetex.cgi?B_n là số hoán vị có http://dientuvietnam...mimetex.cgi?p(n)=n-1
http://dientuvietnam...mimetex.cgi?C_n là số hoán vị có http://dientuvietnam...mimetex.cgi?p(n)=1
Bây giờ ta tìm cách thêm phần tử http://dientuvietnam...mimetex.cgi?n 1 vào hoán vị (ứng với http://dientuvietnam...n/mimetex.cgi?n) để được một hoán vị ứng với http://dientuvietnam.net/cgi-bin/mimetex.cgi?n+1.
Ta có công thức truy hồi :
http://dientuvietnam.net/cgi-bin/mimetex.cgi?A_n=A_{n-1}+B_{n-1}
http://dientuvietnam.net/cgi-bin/mimetex.cgi?B_n=A_{n-1}
Suy ra http://dientuvietnam.net/cgi-bin/mimetex.cgi?B_{n+1}=A_n=A_{n-1}+B_{n-1}=B_n+B_{n-1}, với http://dientuvietnam.net/cgi-bin/mimetex.cgi?B_3=2,B_4=3. Vậy http://dientuvietnam.net/cgi-bin/mimetex.cgi?A_n+B_n=B_{n+2}
Các hoán vị có http://dientuvietnam.net/cgi-bin/mimetex.cgi?p(n)=1 có dạng: http://dientuvietnam.net/cgi-bin/mimetex.cgi?2,3,\ldots,n-1,n,1 hoặc http://dientuvietnam.net/cgi-bin/mimetex.cgi?n,p(2),p(3),\ldots,p(n-1),1. Khi đó http://dientuvietnam.net/cgi-bin/mimetex.cgi?(p(2)-1,p(3)-1,\ldots,p(n-1)-1) là một hoán vị ứng với http://dientuvietnam.net/cgi-bin/mimetex.cgi?n-2 và có http://dientuvietnam.net/cgi-bin/mimetex.cgi?A_{n-2}+B_{n-2}=B_{n}.
KL. http://dientuvietnam.net/cgi-bin/mimetex.cgi?f(n)=B_{n}+B_{n+2}, với http://dientuvietnam.net/cgi-bin/mimetex.cgi?B_n xác định như trên.
hi@: ai ở KHTN làm ơn post đáp án lên cho em khảo bài với.

mình đã sửa lời giải ,cám ơn bác mu đã góp ý
về lời giải của bác thì theo mình hiểu http://dientuvietnam.net/cgi-bin/mimetex.cgi?A_n=A_{n-1}+B_{n-1} đã ko đúng;vì những hoán vị thuộc A_n mà ko thuộc A_{n-1} có dạng {p(1);...;n-2;n} trong đó |p(i)-i|<=1 nhưng của bác còn có thêm điều kiện |p(i)-i| có thể là n-2;tính thừa hoán vị {n-1;1;...;n-3;n-2;n}
->A_n=A_{n-1}+B_{n-1}-1
đúng ko nhỉ

[dangngocthanh]

tôi nghĩ giải quyết theo hướng của thangde là đúng
còn cách giải của mu có lẽ sai ở chỗ khi dùng truy hồi như thế thì không nhận được
http://dientuvietnam...tex.cgi?B_{n-1} vì hiệu đó chỉ thuộc 0,1

Bài viết đã được chỉnh sửa nội dung bởi dangngocthanh: 11-11-2006 - 16:44