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

[hxthanh]

Một số tự nhiên $s$ có $2022$ chữ số được viết theo quy luật sau:
$s=1113131131131131113211321…$
$1$
$11$ (đọc lại hàng trên nghĩa là 1 số 1)
$31$ (đọc lại 2 hàng trên nghĩa là 3 số 1)
$311311$ (đọc lại 3 hàng trên theo thứ tự 3 số 1, 1 số 3, 1 số 1)
v.v…
Hỏi chữ số tận cùng của $s$ là bao nhiêu?

[hxthanh]

Đây là một trong những dãy “look and say” nổi tiếng
A225212
Gọi $f:\mathbb N \to \mathbb N$ là hàm “đọc số” theo kiểu trên
$u_n$ là số được đọc ở lần đọc thứ $n$
Như vậy: $u_0=1, u_1=11, u_2=31$
Và $u_{n+1}=\overline{u_nf(u_n)},\;\;\;\;(n\ge 3)$
Từ đây về sau nếu không nói gì thêm có nghĩa là ta chỉ xét với $n\ge 3$
Dễ thấy với $n\ge 3$ thì $u_n$ bắt đầu bởi $3$ và kết thúc bởi $1$
Còn $f(u_n)$ thì bắt đầu và kết thúc đều là $1$
Gọi $d(m)$ là “độ dài” (số chữ số) của $m$
Gọi $g(m)$ là số cặp hai chữ số liên tiếp giống nhau trong số $m$
Khi đó ta có:
$d(f(u_n))=2d(u_n)-2g(u_n)$
$\Rightarrow d(u_{n+1})=d(\overline{u_nf(u_n)})=3d(u_n)-2g(u_n)\;\;\;\;\;\;(1)$
Ý nghĩa của $(1)$ là nếu ta đếm được số cặp chữ số liên tiếp giống nhau trong $u_n$ ta sẽ tính được chiều dài của $u_{n+1}$
•••
$u_0=1$
$u_1=11$
$u_2=31$
$u_3=31’1311$
$u_4=31’1311’13211321$
$u_5=31’1311’13211321’13211331131221131211$
…
Chẳng hạn theo $(1)$, ta có:
$d(u_3)=3d(u_2)-2g(u_2)=3\times 2-2\times 0=6$ (chữ số)
$d(u_4)=3d(u_3)-2g(u_3)=3\times 6-2\times 2=14$ (chữ số)
Ta có nhận xét sau:
$g(u_{n+1})=g(u_n)+1+g(f(u_n))\;\;\;\;\;(2)$
Điều này dễ hiểu khi $u_n$ kết thúc bởi $1$ còn $f(u_n)$ lại bắt đầu bởi $1$ nên một cặp $11$ được thêm vào.
Ví dụ: $ g(31’1311’13211321)=g(u_4)=g(u_3)+1+g(f(u_3))$
$=g(311311)+1+g(13211321)=2+1+1=4$
nên $d(u_5)=3d(u_4)-2g(u_4)=3\times 14-2\times 4=34$ (chữ số)
Vấn đề của ta là làm sao để “đếm” $g(f(u_n))$
… continued…

[hxthanh]

Tiếp tục các vấn đề bế tắc từ bài toán này:
Các mối liên hệ giữa $u_n, d(u_n), g(u_n), f(n),…$ không hẳn là không có, tuy vậy ta vẫn chưa xác định được chính xác “độ dài” $u_n$ hay “thành phần” của $f(u_n)$ có cái gì trong đó:
Bằng cách “giải” từ định nghĩa “hàm đọc” ta thu được các kết quả:
$$\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|}
\hline u_n&d(u_0)&d(u_1)&d(u_2)&d(u_3)&d(u_4)&d(u_5)&d(u_6)&d(u_7)&d(u_8)&d(u_9)&d(u_{10})&\Sigma d \\ \hline 1&1&&&&&&&&&&&1 \\ \hline 11&1&2&&&&&&&&&&3 \\ \hline 31&1&2&2&&&&&&&&&5 \\
\hline 311311&1&2&2&6&&&&&&&&11 \\ \hline 3113…&1&2&2&6&14&&&&&&&25 \\
\hline 3113…&1&2&2&6&14&34&&&&&&59 \\
\hline 3113…&1&2&2&6&14&34&80&&&&&139 \\
\hline 3113…&1&2&2&6&14&34&80&184&&&&323\\
\hline 3113…&1&2&2&6&14&34&80&184&420&&&743\\
\hline 3113…&1&2&2&6&14&34&80&184&420&958&&1701\\
\hline 3113…&1&2&2&6&14&34&80&184&420&958&2194&3895 \end{array}$$
•••
Như vậy chữ số thứ $2022$ của $s$ cần tìm nằm ở chữ số thứ $321$ của $u_{10}$ hay chữ số thứ $321$ của $u_8$ hay chữ số thứ $323+321=644$ của $s$ … là $1$
•••
Bài toán này quả thực vô cùng bế tắc: có một số vấn đề cần giải quyết hoặc ít ra là “ước lượng”
$\boxed{1}$
- Chứng minh rằng chỉ có $1,2,3$ là các chữ số trong $u_n$
- Không tồn tại $“333”$ trong $u_n$
$\boxed{2}$
- “Có vẻ” như $d(u_n)=2d(u_{n-1})+d(u_{n-2})-d(u_{n-3})+…$
hoặc “gần” như thế!
- Tìm $\lim_{n \to \infty} \frac{d(u_{n+1})}{d(u_n)}$

[hxthanh]

Bạn nào có thể giúp mình xây dựng thuật toán (pascal, c#, v.v…) để tính các giá trị $d(u_n)$ được không?
Mình rất cần những giá trị này để kiểm chứng một vài thứ…

[Hoang72]

Bạn nào có thể giúp mình xây dựng thuật toán (pascal, c#, v.v…) để tính các giá trị $d(u_n)$ được không?
Mình rất cần những giá trị này để kiểm chứng một vài thứ…

Một vấn đề quá khó.

$d(u_n)$ của $n$ chạy từ $3$ đến $18$ ạ... 

6

14

34

80

184

420

958

2194

5036

11564

26544

60912

139814

321244

739270

1704232

Vì $u_n$ sau đó dài hơn nên với thuật toán $O(n)$ tiếp tục cũng khá khó khăn.

Bài viết đã được chỉnh sửa nội dung bởi Hoang72: 01-09-2022 - 22:15

[hxthanh]

Mình không có máy tính để build up, chạy trên điện thoại thì thật kỳ lạ!
Tính đến $d(u_{12})$ thì hiện kết quả chưa đến 1s . Nhưng đến $d(u_{13})$ thì đơ luôn!

Cảm ơn các kết quả của Hoang72
Trước tiên từ các kết quả này thì $\frac{d(u_{n+1})}{d(u_n)} \approx 2.3$

Hình gửi kèm

• 

[perfectstrong]

# m is an array of digits read
def f(m):
    count_history = []
    last_digit = ""
    last_digit_count = 0
    for digit in m:
        if digit != last_digit:
            if last_digit != "":
                count_history.extend([last_digit_count, last_digit])
            last_digit = digit
            last_digit_count = 1
        else:
            last_digit_count += 1
    count_history.extend([last_digit_count, last_digit])
    return count_history

m = [1] # n = 0
for n in range(1, 6):
    u = f(m)
    m.extend(u)
    print(m)
    print("d(u_{}) = {}. d(m) = {}".format(n, len(u), len(m)))

Nếu đặt $m$ là một mảng các chữ số rồi sau đó cứ ghép vào bên phải thì sẽ tiết kiệm được chút thời gian
d(u_1) = 2. d(m) = 3
d(u_2) = 2. d(m) = 5
d(u_3) = 6. d(m) = 11
d(u_4) = 14. d(m) = 25
d(u_5) = 34. d(m) = 59
d(u_6) = 80. d(m) = 139
d(u_7) = 184. d(m) = 323
d(u_8) = 420. d(m) = 743
d(u_9) = 958. d(m) = 1701
d(u_10) = 2194. d(m) = 3895
d(u_11) = 5036. d(m) = 8931
d(u_12) = 11564. d(m) = 20495
d(u_13) = 26544. d(m) = 47039
d(u_14) = 60912. d(m) = 107951
d(u_15) = 139814. d(m) = 247765
d(u_16) = 321244. d(m) = 569009
d(u_17) = 739270. d(m) = 1308279
d(u_18) = 1704232. d(m) = 3012511
d(u_19) = 3934800. d(m) = 6947311
d(u_20) = 9094942. d(m) = 16042253
d(u_21) = 21035168. d(m) = 37077421
d(u_22) = 48658712. d(m) = 85736133
Chia thử tí thì đúng là $\frac{d(u_{n+1})}{d(u_n)} \approx 2,3$.

[perfectstrong]

Em thử chứng minh một nhận xét đơn giản

Mệnh đề 1: $u_n$ không bao giờ có quá $3$ chữ số $1$ liên tiếp.

Ta sẽ sử dụng phản chứng. Giả sử tồn tại ${n_0}$ nào đó để $u_{n_0}$ có ít nhất $4$ chữ số $1$ liên tiếp. Ta sẽ chọn cụm số $1$ liên tiếp bên trái cùng của $u_{n_0}$.

TH1: Nếu cụm chữ số $1$ này không xuất phát từ chữ số hàng cao nhất. Thế thì bên trái cụm này, phải có một chữ số $d$ khác $1$. Ta thấy $d$ không thể là số đếm, bởi vì có nghĩa là ta đã viết $u_{n_0}$ bằng cách đọc $d$ chữ số $1$, rồi tiếp tục $1$ chữ số $1$ (hai chữ số $1$ tiếp theo trong cụm đã chọn): trái với quy tắc. Vì thế $d$ không phải số đếm số $1$ trong $u_{n_0 - 1}$.

Như vậy, 4 chữ số $1$ đầu tiên của cụm đã chọn sẽ có nghĩa là $1$ chữ số $1$, rồi $1$ chữ số $1$: trái với quy tắc xây dựng.

TH2: Nếu cụm chữ số $1$ đã cho xuất phát từ bên trái cùng. Tương tự, $4$ chữ số đầu tiên của cụm sẽ trái với quy tắc xây dựng.

Từ đó, ta có đpcm.

 

Bằng phương pháp tương tự, ta chứng minh được rằng
 

Mệnh đề 2: $u_n$ không bao giờ có chữ nào lặp quá $3$ lần liên tiếp.

 

Từ mệnh đề 2, ta suy ra rằng, $u_n$ không chứa chữ số nào vượt quá $3$. Mặt khác, từ quy tắc đã cho, $u_n$ không thể chứa chữ số $0$ nào.

Do đó, $u_n$ chỉ cấu tạo từ các chữ số $1,2,3$.

Mệnh đề 3: $u_n$ chỉ gồm các chữ số $1,2,3$.

 

Mạnh hơn, ta có thể chứng minh rằng, bằng phương pháp cực hạn và phản chứng:

Mệnh đề 4: $u_n$ không chứa $3$ số $3$ liên tiếp.

Mệnh đề 5: $u_n$ không chứa $3$ số $2$ liên tiếp.

[hxthanh]

Mệnh đề 5 không đúng! 3 chữ số 2 liên tiếp xuất hiện nhiều là đằng khác!
Bằng chứng ngay trong hình chạy thử đã thấy 222 xuất hiện trong $u_6$
Mình đang “nghĩ” xem tần số xuất hiện các chữ số 1,2,3 trong một đoạn bất kỳ có tuân theo quy tắc nào không?
Có vẻ số 1 xuất hiện nhiều hơn hai chữ số kia.
Chẳng hạn đặt câu hỏi:
- Chọn ngẫu nhiên một chữ số ở vị trí bất kỳ trong $s$. Tìm phân phối xác suất cho chữ số nhận được.
- Chọn ngẫu nhiên một đoạn độ dài 3 (hoặc tổng quát hơn là k) chữ số trong $s$. Tìm phân phối xác suất cho kết quả nhận được.
V.v…

[perfectstrong]

Mệnh đề 5 không đúng! 3 chữ số 2 liên tiếp xuất hiện nhiều là đằng khác!
Bằng chứng ngay trong hình chạy thử đã thấy 222 xuất hiện trong $u_6$

Dạ đúng thật. Em sót chỗ này 3 số 3 thì sẽ hoặc có nghĩa là $x$ số 3 rồi 3 số số 3, hoặc 3 số 3 rồi 3 số $x$. Đằng nào cũng dẫn tới vô lý. Nhưng 3 số 2 thì có thể.