Đến nội dung


Hình ảnh
* * * * * 2 Bình chọn

Tìm chữ số thứ $2022$


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

#1 hxthanh

hxthanh

  • Quản trị
  • 3437 Bài viết
  • Giới tính:Nam

Đã gửi 25-08-2022 - 07:39

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?
Cuộc sống thật nhàm chán! Ngày mai của ngày hôm qua chẳng khác nào ngày hôm qua của ngày mai, cũng như ngày hôm nay vậy!

#2 hxthanh

hxthanh

  • Quản trị
  • 3437 Bài viết
  • Giới tính:Nam

Đã gửi 26-08-2022 - 07:31

Đâ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…
Cuộc sống thật nhàm chán! Ngày mai của ngày hôm qua chẳng khác nào ngày hôm qua của ngày mai, cũng như ngày hôm nay vậy!

#3 hxthanh

hxthanh

  • Quản trị
  • 3437 Bài viết
  • Giới tính:Nam

Đã gửi 30-08-2022 - 21:07

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)}$
Cuộc sống thật nhàm chán! Ngày mai của ngày hôm qua chẳng khác nào ngày hôm qua của ngày mai, cũng như ngày hôm nay vậy!

#4 hxthanh

hxthanh

  • Quản trị
  • 3437 Bài viết
  • Giới tính:Nam

Đã gửi 01-09-2022 - 20:43

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ứ…
Cuộc sống thật nhàm chán! Ngày mai của ngày hôm qua chẳng khác nào ngày hôm qua của ngày mai, cũng như ngày hôm nay vậy!

#5 Hoang72

Hoang72

    Sĩ quan

  • Thành viên
  • 436 Bài viết
  • Giới tính:Nam
  • Đến từ:Hà Tĩnh
  • Sở thích:Codingg

Đã gửi 01-09-2022 - 21:49

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


#6 hxthanh

hxthanh

  • Quản trị
  • 3437 Bài viết
  • Giới tính:Nam

Đã gửi 02-09-2022 - 00:56

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!
6BECE55F-4DF3-45D5-97F6-662F7B942857.jpeg 966D2B28-3CF8-4560-8AF9-F47CE1D42C51.jpeg
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

  • C23607C6-60C4-4ECA-A863-4D063A2E29AF.jpeg

Cuộc sống thật nhàm chán! Ngày mai của ngày hôm qua chẳng khác nào ngày hôm qua của ngày mai, cũng như ngày hôm nay vậy!

#7 perfectstrong

perfectstrong

    $LOVE(x)|_{x =\alpha}^\Omega=+\infty$

  • Quản trị
  • 4538 Bài viết
  • Giới tính:Nam
  • Sở thích:Đàn guitar, ngắm người mình yêu, học toán

Đã gửi 02-09-2022 - 03:05

# 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$.


Luôn yêu để sống, luôn sống để học toán, luôn học toán để yêu!!! :D

$$\text{LOVE}\left( x \right)|_{x = \alpha}^\Omega = + \infty $$




I'm still there everywhere.

#8 perfectstrong

perfectstrong

    $LOVE(x)|_{x =\alpha}^\Omega=+\infty$

  • Quản trị
  • 4538 Bài viết
  • Giới tính:Nam
  • Sở thích:Đàn guitar, ngắm người mình yêu, học toán

Đã gửi 02-09-2022 - 03:14

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

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.


Luôn yêu để sống, luôn sống để học toán, luôn học toán để yêu!!! :D

$$\text{LOVE}\left( x \right)|_{x = \alpha}^\Omega = + \infty $$




I'm still there everywhere.

#9 hxthanh

hxthanh

  • Quản trị
  • 3437 Bài viết
  • Giới tính:Nam

Đã gửi 03-09-2022 - 08:57

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…
Cuộc sống thật nhàm chán! Ngày mai của ngày hôm qua chẳng khác nào ngày hôm qua của ngày mai, cũng như ngày hôm nay vậy!

#10 perfectstrong

perfectstrong

    $LOVE(x)|_{x =\alpha}^\Omega=+\infty$

  • Quản trị
  • 4538 Bài viết
  • Giới tính:Nam
  • Sở thích:Đàn guitar, ngắm người mình yêu, học toán

Đã gửi 03-09-2022 - 15:15

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 :D 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ể.


Luôn yêu để sống, luôn sống để học toán, luôn học toán để yêu!!! :D

$$\text{LOVE}\left( x \right)|_{x = \alpha}^\Omega = + \infty $$




I'm still there everywhere.




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

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