Đến nội dung


Chú ý

Nếu các bạn đăng kí thành viên mà không nhận được email kích hoạt thì hãy kiểm tra thùng thư rác (spam). Nếu không biết cách truy cập vào thùng thư rác thì các bạn chịu khó Google hoặc đăng câu hỏi vào mục Hướng dẫn - Trợ giúp để thành viên khác có thể hỗ trợ.


Hình ảnh
- - - - -

Dãy số Hailstone


  • Please log in to reply
Chủ đề này có 1 trả lời

#1 tranghieu95

tranghieu95

    Trung sĩ

  • Thành viên
  • 147 Bài viết
  • Giới tính:Không khai báo
  • Đến từ:THPT Phan Bội Châu

Đã gửi 18-01-2013 - 21:52

Đây là một bài toán khá đơn giản để để miêu tả nó nhưng lại là một bài toán chưa có lời giải.

mua-da.png

Với mọi số nguyên dương $m$ ta xây dựng dãy số như sau:

  • Nếu $m$ chẵn, ta chia $m$ cho $2$ ta được: $m'=\dfrac{m}{2}$
  • Nếu $m$ lẻ, nhân $m$ với $3$ và cộng thêm $1$ ta được: $m'=3m+1$

Sau đó ta coi $m'$ là số bắt đầu và lặp lại quá trình trên.

Nói cách khác, ta xét dãy $(u_n)$ có $u_1=m \in \mathbb{N}^*$ và:

$$u_{n+1}=\left\{\begin{matrix} \dfrac{u_n}{2},&\text{khi } u_n = 2k\\ 3u_n+1,&\text{khi } u_n=2k+1\end{matrix}\right., (k\in \mathbb{N}), \forall n \geq 1$$

Ví dụ:

Khi $m=5$ ta có dãy số sau:

$$5; 16; 8; 4; 3; 1; 4; 2; 1; ...$$

Khi $m=11$ ta có dãy số sau:

$$11; 34; 17; 52; 26; 13; 40; 20; 10; 5; 16; 8; 4; 2; 1; 4; 2; 1;...$$

 

Chúng đôi khi được gọi là " dãy Hailstone" (dãy mưa đá) vì chu kỳ vô tận $4; 2; 1; 4; 2; 1$ đi lên và xuống giống như một hạt mưa đá trong một đám mây trước khi đâm xuống mặt đất. Có vẻ như từ một số dãy số trên, ta thấy được chúng đều kết thúc bằng $4; 2; 1; 4; 2; 1$. Nhưng một số giá trị của $m$ lại khiến cho dãy có nhiều số hạng trước khi chu kỳ $4;2;1$ trên bắt đầu. Ví dụ khi $m=27$, ta có thể thấy từ số hạng thứ $110$ thì chu kì mới xuất hiện.

 

Một vấn đề chưa được giải quyết, đó là: có phải với mọi giá trị của $m$, dãy số $(u_n)$ xác định như trên luôn xuất hiện chu kì $4;2;1$ kề từ số hạng nào đó trở đi hay không? Có dãy số $(u_n)$ nào không có chu kì đó hay không?

 

Dịch theo http://plus.maths.org

Mời bạn thảo luận thêm tại đây


TỪ TỪ LÀ HẠNH PHÚC
A1K39PBC

#2 bangbang1412

bangbang1412

    Độc cô cầu bại

  • Phó Quản trị
  • 1525 Bài viết
  • Giới tính:Không khai báo
  • Đến từ:Dốt nhất khoa Toán
  • Sở thích:Unstable homotopy theory

Đã gửi 26-01-2017 - 23:08

Thập niên $1950$ , giới toán học thế giới lưu truyền một hiện tượng toán học kì lạ mà thú vị sau đây : Lấy một số tự nhiên $x$ , nếu là số chẵn thì chia đôi $\frac{x}{2}$ , nếu lẻ thì nhân $3$ rồi cộng $1$ tức là $3x+1$ , cứ tiếp tục như vậy bao giờ cũng sẽ thu được số $1$ .

Chẳng hạn : lấy $x=6$ làm như trên thì $\frac{6}{2}=3,3.3+1=10,\frac{10}{2}=5,5.3+1=16,\frac{16}{2}=8,\frac{8}{2}=4,\frac{4}{2}=2,\frac{2}{2}=1$

Hiện tượng toán học thú vị này gây cảm hứng cho rất nhiều người yêu thích toán học . Một nhá toán học Mĩ nói : "có một thời trong các trường đại học Mĩ , hiện tượng này trở thành hấp dẫn nhất , sinh viên khoa Toán và khoa Máy tính gần như ai cũng nghiên cứu nó . "

Có người hình dung quá trình tính toán là các giọt nước trong mây , dưới tác dụng của luồng không khí trên cao , gặp lạnh nước sẽ đóng băng , thể tích ngày càng lớn , cuối cùng biến thành mưa đá . Rồi cuối cùng biến thành $1$ . Ví vậy người ta đặt cho quá trình này cái tên trừu tượng : ý tưởng " mưa đá " hoặc số " mưa đó " .

Các nhà nghiên cứu phát hiện một cách vừa kinh ngạc vừa mừng vui dù phải thực hiện bao nhiêu phép tính thì cuối cùng vẫn về $ 4 \to 2 \to 1$ . Để kiểm tra nên bắt đầu từ $1.3+1=4,\frac{4}{2}=2,\frac{2}{2}=1$ tức là phải qua $4$ đến $2$ rồi mới đến $1$ .

Giáo viên và sinh viên ở đại học Tokyo ( Nhật Bản ) đã kiểm tra từng số của tất cả các số tự nhiên đến $2^{40}$ vẫn không tìm thấy ngoại lệ , đều kết thúc bằng $4 \to 2 \to 1$ .

Như vậy đây là sự ngẫu nhiên hay một quy luật tất yếu ? Vấn đề này vẫn chưa có câu trả lời thuyết phục .

Sư biến đổi các số tự nhiên ở trên trong thực tế là lặp lại hàm số

$$C(x)=\begin{cases} & \frac{x}{2}\text{ if } x= 2k \\ & 3x+1 \text{ if } x= 2k+1 \end{cases}$$

Vấn dề là , bắt đầu từ một số tự nhiên $x$ bất kì , trải qua phép lặp hàm số $C(x)$ một số lần hữu hạn ( sau đây gọi tắt là lặp $C$ ) , cuối cùng có một nhóm số tuần hoàn $(4,2,1)$ không ?Hoặc nói cách khác là cuối cùng có được $1$ không ?

Có người cho rằng ý tưởng này do L.Collatz đưa ra tại Hội nghị Toán học thế giới năm $1950$ nhưng có người lại nói do B.Thwaiter ( Anh ) , R.V.Andree ( Nga ) , Hans , Neolamu ( Mỹ ), ... đưa ra , chưa ai xác nhận chính xác người đưa ra đầu tiên , do vậy nhiều tài liệu gọi nó là vấn đề $3x+1$ .

Điều lôi cuốn người ta là ở chỗ trong quá trình lặp $C$ hễ gặp lũy thừa của $2$ là bài giải kết thúc , mà lũy thừa của $2$ thì nhiều vô cùng , do vậy người ta cho rằng chỉ cần quá trình lặp $C$ đủ dài nhất định sẽ gặp lũy thừa của $2$ .

Năm $1992$ , G.T.Leavens và M.Vermulen đã kiểm tra các số tự nhiên đến $5,6.10^{13}$ vẫn thấy đúng quy luật .

Vấn đề $3x+1$ thật đơn giản , ngay cả học sinh tiểu học cũng hiểu được , thế mà các nhà toán học , ngay cả các nhà toán học nổi tiếng cũng chưa giải quyết được . Học giả R.K.Guy gọi đây là " Đề toán khó thế giới " và khuyên mọi người không nên toan tính giải quyết vấn đề này . Người ta đưa ra nhiều giải thưởng , số tiền thưởng ngày càng tăng cao hơn nhưng vẫn chưa ai giải quyết được . Đến nay ta tạm chấp nhân cách nói của nhà toán học nổi tiếng Paul Erdos : " Toán học còn chưa đủ chính chắn để giải quyết vấn đề 3x+1" . Có người đề nghị lấy vấn đề $3x+1$ làm bài toán sau định lý lớn Fermat .

Cái khó của vấn đề $3x+1$ là tính phức tạp được biểu hiện ra trong quá trình lặp nhiều lần C . Để thuận tiện khi trình bày ta gọi dãy số khi thu được lặp nhiều lần $C$ đối với số $x$ là dãy số $C$ của số $x$ .

Tính phức tạp của vấn đề trước tiên là tính không quy tắc của độ lớn các chữ trong trong dãy số $C$ . Chẳng hạn , lặp $111$ lần đối với số $x=27$ cuối cùng vẫn được $1$ nhưng dao động lên xuống $42$ lần , Tuy vậy người ta vẫn tìm thấy một " cái gì đó " có tính quy luật trong sự hỗn loạn mất trật tự này .

Nhằm nghiên cứu quy luật dãy số $C$ , người ta đã làm thống kê như sau : Đặt $u,v$ là hai số lẻ thu được liên tiếp trong quá trình lặp $C$ , hiển nhiên $\frac{1}{2}(3u+1)$ vừa có thể là số lẻ vừa có thể là chẵn , hai khả năng này mỗi cái chiếm một nửa $\frac{1}{2}$  . Do đó $u$ qua một lần lặp $C$ thì được số lẻ $v$ , tức là khả năng của $\frac{3u+1}{2}=v$ là $\frac{1}{2}$ , cũng tức là khả năng của $u$ qua một lần thay đổi tăng dần bằng khoảng $\frac{3}{2}(\frac{u}{v} \approx \frac{3}{2})$ ban đầu là $\frac{1}{2}$ . Nhưng khả năng của $\frac{1}{2}(3u+1)$ là số chẵn cũng là $\frac{1}{2}$ . Lúc này thay một lần nữa sẽ được $\frac{1}{4}(3u+1)$ nó vừa là số lẻ cũng có thể là số chẵn . Từ đó $\frac{1}{4}(3u+1)=v$ , tức là khả năng của sự tăng dần bằng khoảng $\frac{3}{4}(\frac{u}{v} \approx \frac{3}{4})$ ban đầu là $\frac{1}{2}.\frac{1}{2}=\frac{1}{4}$ . Cũng vây , khả năng của $\frac{1}{4}(3u+1)$ là số chẵn cũng là $\frac{1}{4}$ . Thay một lần nữa được $\frac{1}{8}(3u+1)$ nó vừa có thể là lẻ cũng có thể là chẵn . Từ đó $\frac{1}{8}(3u+1)=v$ khả năng của sư tăng dần bằng khoảng $\frac{3}{8}$ ban đầu $\frac{1}{4}.\frac{1}{2}=\frac{1}{8}$ . Cứ tiếp tục như vậy , khả năng tăng dần bình quân từ một số lẻ $u$ để được số lẻ $v$ là :

$$r = (\frac{3}{2})^{\frac{1}{2}}.(\frac{3}{4})^{\frac{1}{4}}.(\frac{3}{8})^{\frac{1}{8}}...=\frac{3}{4}$$

Điều này chứng tỏ trong quá trình lặp $C$ , khả năng tăng dần bình quân độ lớn của hai số lẻ liên tiếp là $\frac{3}{4}$ , tức là xu thế bình quân tổng thể hạ thấp xuống , do vậy sự lặp $C$ sớm muộn sẽ dẫn đến $1$ . Đây là quy luật mang tính thống kê nhưng quan trọng trong việc chứng minh vấn đề $3x+1$ .

Còn một điều thú vị nữa là : Rất nhiều số tự nhiên liên tiêp có cùng một chiều dài đoạn lặp $C$ như nhau . Chẳng hạn $N = 8s+4,8s+5$ ( $s$ là số tự nhiên túy ý) qua ba lần lặp $C$ đều được $6s+4$ , do đó chiều dài đoạn lặp $C$ của hai số tự nhiên liên tiếp là như nhau . Chẳng hạn $17$ số tự nhiên liên tiếp từ $7083$ đến $7099$ đều có chiều dài đoạn lặp $C$ là như nhau . Năm $1976$ nhà toán học Colunborge người Mỹ lại phát hiện được $52$ số tự nhiên liên tiếp có cùng một chiều dài đoạn lặp $C$ như nhau .

Qua nghiên cứu người ta đã tìm được

+ Khi $x$ là số nguyên dương sẽ xuất hiện tuần hoàn $(4,2,1)$

+ Khi $x=0$ sẽ xuất hiện tuần hoàn $(0)$

+ Khi $x=-1,-2,-3,-4$ sẽ xuất hiện tuần hoàn $(-1,-2)$

+ Khi $x=-5$ sẽ xuất hiện tuần hoàn $(-5,-14,-7,-20,-10)$

+ Khi $x=-6,-7,...-16$ sẽ xuất hiện tuần hoàn $(-17,-50,-25,-74,-37,-110,-55,-164,-82,-41,-122,-61,-182,-91,-272,-138,-68,-34)$

+ Khi $x=-17$ sẽ xuất hiện tuần hoàn ( blo bla mọi người tính nhé )

+ Khi $x < -17$ sẽ không xuất hiện tuần hoàn .

Năm $1978$ có người phỏng đoán : Nếu lặp $C$ cho tất cả số nguyên thì chỉ có thể nhận được $5$ loại tuần hoàn nói trên. Người ta kiểm tra cho các số nguyên âm đến $-10^{8}$ thì phỏng đoán này vẫn đúng . Tuy vậy vẫn chưa có một chứng minh cho trường hợp tổng quát .

Người ta lại đưa ra hàm số đơn giản hơn :

$$C(x)=\frac{3x+1}{2^{e(x)}}$$

Trong đó $e(x)$ là các lũy thừa của ước nguyên tố $2$ trong phân tích thành các ước nguyên tố của $3x+1$ .

Trường hợp tổng quát đặt $a,b$ là các số nguyên dương lẻ $a>1$ thì

$$C(x)=\frac{ax+b}{2^{e(x)}}$$

Trong đó $x$ lấy số lẻ dương , nếu lấy $a=3,b=1$ thì về vấn đề $3x+1$ , điều đặc biệt là nếu $(a,b)$ mà khác $(3,1)$ thì lặp $C$ sẽ không xuất hiện số $1$ ( thần kì ! )

Nếu lấy $r= bt$ ( $t$ là số lẻ dương bất kì )

$$C(r).2^{e(r)}=ar+b=(at+1)b$$

Nếu $b>1$ thì tất cả $C(r)$ đều chia hết cho $b$ và như vậy không bao giờ xuất hiên $1$ .

Nếu $b=1$ thi khi $a$ là số chẵn , $C(x)=ax+1$ luôn lẻ và dãy $C$ tăng dần , lặp $C$ không thể có $1$ được . Còn khi $a$ là số lẻ , sẽ tồn tại một số lẻ dương $r$ nào đó mà $C(r)=\frac{ar+1}{2^{e(r)}}$ không xuất hiện $1$

Năm $1978$ , R.E.Crandall đã chứng minh $a=5,181,1093$ thì phỏng đoán nếu trên đúng .

+ Khi $a=5$ thì $C(r)=\frac{5r+1}{2^{e(r)}}$ , lấy $r=13$ thì dãy xuất hiện tuần hoàn $(33,83,13)$ không xuất hiện $1$

+ Khi $a=181$ thì $C(r)=\frac{181r+1}{2^{e(r)}}$ , lấy $r=27$ thì xuất hiện tuần hoàn $(611,27)$ không xuát hiện $1$

+ Khi $a=1093$ thì $C(s) = \frac{1093s+1}{2^{e(s)}}$ , lấy $s= \frac{2^{364p}-1}{1093}$ trong đó $p$ là số tự nhiên bất kì thì $1093s+1=2^{364p}$ vì vậy $e(s)=364p,C(s)=1$

Như vậy đây là nhóm số duy nhất xuất hiện $1$ , còn đối với bất cứ số lẻ dương $s$ khác , lặp $C$ có thể kéo dài vô hạn mà không đạt được $1$ .

Có người đã lấy $a=7$ và thực hiện việc lặp $r=3$ vượt qua số $10^{2000}$ mà vẫn chưa thấy dấu hiệu lặp lại ( tuần hoàn) nào . Xem ra phỏng đoán $7x+1$ rất có thể là chính xác nhưng chưa ai chứng minh được bằng lý thuyết ,

Thập niên $1930$ , khi L.Collatz đang học đại học , ông đã say mê nghiên cứu vấn đề $3x+1$ . Trong cuốn số ghi chép để ngày $1-7-1932$ ông đã nghiên cứu hàm số $F(x)=\frac{2x}{3},\frac{4x-1}{3},\frac{4x+1}{3}$ lần lượt tương ứng với $x$ chia $3$ dư $0,1,2$

Các kết quả tính được cho thấy rằng với $x$ bằng $2,3$ thì sinh ra tuần hoàn $(2,3)$ , với $x=4,5,6,7,9$ thì sinh ra tuần hoàn $(5,7,9,6,4)$ còn $x=8$ thì ông chưa thấy xuất hiên tuần hoàn , mặc dù đã thực hiện khá nhiều phép tính . Vấn đề này được coi là " vấn đề Collatz nguyên thủy " .

Vấn đề ngược lại với vấn đề Collatz nguyên thủy là hàm $G(x)$ xác định

$$G(x) = \frac{3x}{2}$$ khi $x$ chẵn

$$G(x)=\frac{3x-1}{4}$$ khi $x$ chia $4$ dư $3$

$$G(x)=\frac{3x+1}{4}$$ khi $x$ chia $4$ dư $1$ ,

Đang làm nhiều người quan tâm . Tính toán như hàm $F(x)$ ta được bốn nhóm số tuần hoàn $(1),(2,3),(4,6,9,7,5),(44,66,99,74,111,83,62,93,70,105,79,59)$ tuy vậy nhóm tuần hoàn còn nữa hay không thì vẫn chưa ai trả lời được .

Trích từ : Tuyển tập những vấn chưa toán học chưa có lời giải - Nguyễn Bá Đô


Bài viết đã được chỉnh sửa nội dung bởi bangbang1412: 26-01-2017 - 23:17

Declare to yourself that, from now on, your life is dedicated to one and only one woman, the greatest mistress of your life, the tenderest woman you have ever encountered, Mathematica.





1 người đang xem chủ đề

0 thành viên, 1 khách, 0 thành viên ẩn danh