[TẶNG BẠN] TRỌN BỘ Bí kíp học tốt 08 môn
Chắc suất Đại học top - Giữ chỗ ngay!!
ĐĂNG BÀI NGAY để cùng trao đổi với các thành viên siêu nhiệt tình & dễ thương trên diễn đàn.
phỏng đoán collatz:
Xét một phép toán sau tác động lên một số nguyên dương bất kỳ:
Nếu nó là số chẵn, chia số đó cho 2.
Nếu nó là số lẻ, nhân số đó với 3 và cộng 1.
gọi a là số nguyên dương chọn ban đầu => a được chọn ngẫu nhiên trong khoảng [math]\left[1;2^{p}\right][/math].
giả sử số chẵn q > p, đủ lớn để: 2^q > max {f(n)}
vì a ngẫu nhiên nên a/2^(x) ngẫu nhiên với mọi x. => nếu a là số chẵn, bội của 2^x thì sẽ chia 2 liên tục đến khi được số lẻ vẫn là một số ngẫu nhiên.
ta có mệnh đề sau có thể chứng minh bằng quy nạp: [math]\left(2^{2k}-1\right)[/math] chia hết cho 3 với mọi k thuộc N* .
1. trường hợp lần đầu chọn số a trùng với 2^k; 0<k≤p
=> xác suất (P1) = n/2^n
2. trường hợp chọn số a chẵn, ta chia 2 đến khi được số lẻ
3. trường hợp chọn số a lẻ, xác suất để a có dạng [math]\left((2^{2k}-1)/3\right)[/math] => có q/2 số lẻ trong q số tự nhiên; có 2^(q-1) số lẻ trong 2^q số tự nhiên => [math](P2)=\frac{\frac{q}{2}}{2^{q-1}}=\frac{q}{2^{q}}[/math](khi số a có dạng đặc biệt như trên thì sau khi tính 3a+1 đa được lũy thừa của 2 và dãy số tiếp theo giảm về 1)
Nếu a không có dạng trên thì 3a+1 là số chẵn ngẫu nhiên, ta lại chia 2 như trường hợp 2 đến khi được số lẻ ngẫu nhiên tiếp thì được phép thử cho trường hợp 3 và xác suất cho lần thử 2 vẫn vậy.
Thiết lập công thức sau t lần thử số lẻ như vậy, xác suất (tính tại thời điểm chưa chọn số a) để không gặp dạng đặc biệt của a là
[math](P)=\left(1-\frac{p}{2^{p}}\right)\left(1-\frac{q}{2^{q}}\right)^{t}[/math]nhận xét: vì p,q nguyên dương; 2^q > 2^p > 0 nên cơ số của t nhỏ hơn 1 => khi t tiến tới vô cùng (sau nhiều lần "thử") (P) tiến tới 0.
vậy chắc chắn dãy hội tụ về 1!
lời giải trên do mình tự nghĩ ra, chắc vẫn còn nhiều sai sót, mọi người góp ý thêm!!!
Xét một phép toán sau tác động lên một số nguyên dương bất kỳ:
Nếu nó là số chẵn, chia số đó cho 2.
Nếu nó là số lẻ, nhân số đó với 3 và cộng 1.
gọi a là số nguyên dương chọn ban đầu => a được chọn ngẫu nhiên trong khoảng [math]\left[1;2^{p}\right][/math].
giả sử số chẵn q > p, đủ lớn để: 2^q > max {f(n)}
vì a ngẫu nhiên nên a/2^(x) ngẫu nhiên với mọi x. => nếu a là số chẵn, bội của 2^x thì sẽ chia 2 liên tục đến khi được số lẻ vẫn là một số ngẫu nhiên.
ta có mệnh đề sau có thể chứng minh bằng quy nạp: [math]\left(2^{2k}-1\right)[/math] chia hết cho 3 với mọi k thuộc N* .
1. trường hợp lần đầu chọn số a trùng với 2^k; 0<k≤p
=> xác suất (P1) = n/2^n
2. trường hợp chọn số a chẵn, ta chia 2 đến khi được số lẻ
3. trường hợp chọn số a lẻ, xác suất để a có dạng [math]\left((2^{2k}-1)/3\right)[/math] => có q/2 số lẻ trong q số tự nhiên; có 2^(q-1) số lẻ trong 2^q số tự nhiên => [math](P2)=\frac{\frac{q}{2}}{2^{q-1}}=\frac{q}{2^{q}}[/math](khi số a có dạng đặc biệt như trên thì sau khi tính 3a+1 đa được lũy thừa của 2 và dãy số tiếp theo giảm về 1)
Nếu a không có dạng trên thì 3a+1 là số chẵn ngẫu nhiên, ta lại chia 2 như trường hợp 2 đến khi được số lẻ ngẫu nhiên tiếp thì được phép thử cho trường hợp 3 và xác suất cho lần thử 2 vẫn vậy.
Thiết lập công thức sau t lần thử số lẻ như vậy, xác suất (tính tại thời điểm chưa chọn số a) để không gặp dạng đặc biệt của a là
[math](P)=\left(1-\frac{p}{2^{p}}\right)\left(1-\frac{q}{2^{q}}\right)^{t}[/math]nhận xét: vì p,q nguyên dương; 2^q > 2^p > 0 nên cơ số của t nhỏ hơn 1 => khi t tiến tới vô cùng (sau nhiều lần "thử") (P) tiến tới 0.
vậy chắc chắn dãy hội tụ về 1!
lời giải trên do mình tự nghĩ ra, chắc vẫn còn nhiều sai sót, mọi người góp ý thêm!!!
