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

[perfectstrong]

Ta sử dụng định nghĩa dãy Fibonacci như sau: $F_1 = 1; F_2 = 2; F_{n} = F_{n-1}+F_{n-2} \, \forall n \ge 3$.

Câu 1: Chứng minh rằng mọi số nguyên dương $N \ge 1$ luôn có thể phân tích tổng của một số hữu hạn số Fibonacci $F_n$ phân biệt.

Câu 2: Gọi $L^*(N)$ là độ dài của cách phân tích $N$ thành tổng các số Fibonacci phân biệt sao cho số số hạng là nhiều nhất. Một cậu học trò không biết làm sao để tìm $L^*(N)$, nên cậu đề xuất một thuật toán $H$ như sau:

1. Gọi $m_N$ là số nguyên dương nhỏ nhất sao cho $S_N = \sum\limits_{n=1}^{m_N} F_n \ge N$
2. Nếu $S_N$ thì $L^*(N) = m_N$, tức là $S_N$ là cách phân tích cần tìm.
3. Nếu $S_N > N$ thì đặt $d_N = S_N - N$
4. Phân tích $d_N$ thành tổng các số Fibonacci phân biệt sử dụng thuật toán $H'$
5. Loại bỏ những số Fibonacci nào trong $S_N$ nào xuất hiện trong $d_N$, thu được $S'_N$. Khi đó, $S'_N$ là kết quả của thuật toán.

Thuật toán $H'$: phân tích một số nguyên dương $N$ thành tổng các số Fibonacci phân biệt theo nguyên tắc tham lam giảm dần (decreasing greedy):

1. Gọi $i$ là chỉ số lớn nhất sao cho $F_i \le N$.
2. Đặt $N'=N-F_i$.
3. Nếu $N'=0$ thì dừng.
4. Nếu $N'>0$ thì thay $N$ bởi $N'$, và quay lại bước 1.

Các chỉ số $i$ tìm được sẽ cho ta cách phân tích $N$ thành ít số Fibonacci nhất có thể.

 

a. CMR thuật toán $H'$ sẽ tìm ra phân tích Fibonacci ngắn nhất có thể

b. CM tính đúng đắn của thuật toán $H$, tức là $H$ sẽ cho ra một phân tích Fibonacci, dù cho có thể không phải là phân tích tối ưu.

c. Ta muốn đánh giá hiệu suất của $H$. Gọi $L^H(N)$ là độ dài của cách phân tích bởi thuật toán $H$. Tìm $a,b$ tốt nhất sao cho \[\mathop {\lim }\limits_{N \to \infty } \left( {\frac{{{L^H}\left( N \right)}}{{{L^*}\left( N \right)}} - \left( {aN + b} \right)} \right) = 0\]

Bài viết đã được chỉnh sửa nội dung bởi perfectstrong: 03-01-2025 - 03:57
Giải thích cụ thể câu 2a

[perfectstrong]

Câu 1:

Mệnh đề

Mọi số nguyên dương $N \ge 1$ luôn có thể phân tích tổng của một số hữu hạn số Fibonacci $F_n$ phân biệt.

Dễ thấy Theorem đúng với $N \in \{1,2,3\}$. Giả sử Theorem đúng tới $N=k \ge 3$, ta chứng minh Theorem cũng đúng tới $N=k + 1$.

Ta sẽ tìm cách phân tích $k+1$ bằng cách sử dụng số Fibonacci lớn nhất không vượt quá $k+1$.

Ký hiệu $\phi(x)$ là chỉ số lớn nhất sao cho $F_{\phi(x)} \le x \, \forall x \in \mathbb N^*$.

Như vậy số hạng đầu tiên trong phân tích Fibonacci của $k+1$ sẽ là $F_{\phi(k+1)}$.

Phần dư là $f_{k+1} = k+1 - F_{\phi(k+1)}$.

Vì $f_{k+1} < k+1$ nên theo giả thiết quy nạp, ta hoàn toàn có thể phân tích $f_{k+1}$ thành tổng hữu hạn số Fibonacci phân biệt.

Để hoàn tất chứng minh, ta cần chỉ ra rằng phân tích của $f_{k+1}$ không thể chứa $F_{\phi(k+1)}$.

Thật vậy, ta sẽ dùng phản chứng : giả sử phân tích Fibonacci của $f_{k+1}$ chứa $F_{\phi(k+1)}$.

Do đó $f_{k+1} \ge F_{\phi(k+1)} \Rightarrow k+1 \ge 2F_{\phi(k+1)}$.

Thế nhưng điều này mâu thuẫn với định nghĩa của $\phi(k+1)$, vì số Fibonacci tiếp sau đó $F_{\phi(k+1)+1}$ sẽ nằm giữa $k+1$ và $F_{\phi(k+1)}$ :

\[k + 1 \ge 2{F_{\phi \left( {k + 1} \right)}} > {F_{\phi \left( {k + 1} \right)}} + {F_{\phi \left( {k + 1} \right) - 1}} = {F_{\phi \left( {k + 1} \right) + 1}} > {F_{\phi \left( {k + 1} \right)}}\]

(Dãy Fibonacci mà ta sử dụng là dãy tăng nghiêm ngặt)

Vì thế, Theorem đúng tới $N=k + 1$. Theo nguyên lý quy nạp, ta có đpcm.

 

[perfectstrong]

Câu 2a:

Định lý

Thuật toán $H'$ tìm được phân tích Fibonacci ngắn nhất.

Ta chứng minh Theorem bằng phản chứng.

Dễ dàng kiểm tra được $H'$ đúng tới $N \le 5$.

Giả sử tồn tại số nguyên dương nào đó mà $H'$ không đưa ra được phân tích Fibonacci ngắn nhất.

Gọi $N_0$ là số nguyên dương nhỏ nhất mà $H'$ không thành công.

Gọi phân tích Fibonacci ngắn nhất thật sự của $N_0$ là bộ chỉ số ${j_1},{j_2}, \ldots ,{j_{v\left( {{N_0}} \right)}}$ sao cho ${j_1} > {j_2} >  \ldots  > {j_{v\left( {{N_0}} \right)}}$

Gọi phân tích Fibonacci sinh từ $H'$ cho $N_0$ là bộ chỉ số ${i_1},{i_2}, \ldots ,{i_{u\left( {{N_0}} \right)}}$ sao cho ${i_1} > {i_2} >  \ldots  > {i_{u\left( {{N_0}} \right)}}$ và $u(N_0) > v(N_0)$

Do định nghĩa của $i_1$ nên dễ thấy $i_1 \ge j_1$. Ta cần nghiên cứu tính chất của bộ chỉ số $(j_k)$.

Mệnh đề

Phân tích Fibonacci ngắn nhất không chứa hai số Fibonacci liên tiếp : Nếu tồn tại chỉ số $j_k$ và $j_{k+1}$ thì $j_k \ge j_{k+1} + 2$

Chứng minh

Thật vậy, nếu tồn tại $k$ để $j_k = j_{k+1} + 1$ thì vì $F_{j_k+1} = F_{j_k} + F_{j_{k+1}}$, ta có thể chọn $k$ nhỏ nhất và thay cặp $(F_{j_k},F_{j_{k+1}})$ bằng $F_{j_{k}+1}$ để có được một phân tích mới ngắn hơn cho $N_0$, trái với định nghĩa của bộ ${j_1},{j_2}, \ldots ,{j_{v\left( {{N_0}} \right)}}$

Tính chất này khiến ta liên tưởng tới đẳng thức tổng xen kẽ của dãy Fibonacci :

Mệnh đề

Với mọi số nguyên dương $n$:

\[\begin{array}{l}
{F_{2n}} = {F_{2n - 1}} + {F_{2n - 3}} +  \ldots  + {F_1} + 1\\
{F_{2n + 1}} = {F_{2n}} + {F_{2n - 2}} +  \ldots  + {F_2} + 1
\end{array}\]

Ta vận dụng Theorem để chứng minh rằng $i_1=j_1$. Thật vậy, giả sử $i_1 > j_1$. Khi đó

\[{F_{{j_1}}} + {F_{{j_2}}} +  \ldots  + {F_{{j_{v\left( {{N_0}} \right)}}}} \le {F_{{j_1}}} + {F_{{j_1} - 2}} + {F_{{j_1} - 4}} +  \ldots  = {F_{{j_1} + 1}} - 1 \le {F_{{i_1}}} - 1 < {N_0}\]

Mâu thuẫn với định nghĩa của bộ chỉ số $(j_k)$. Vậy nên $i_1=j_1$.

Thế nhưng, số nguyên dương $N_1 = N_0 - F_{i_1} < N_0$ lại có phân tích Fibonacci $j_2, j_3, \ldots, j_{v(N_0)}$ ngắn hơn lời giải của $H'$ cho $N_1$, trái với định nghĩa của $N_0$.

 

Vì vậy, Theorem được chứng minh.

Bài viết đã được chỉnh sửa nội dung bởi perfectstrong: 07-01-2025 - 21:39

[perfectstrong]

Câu 2b: Vì $S_N$ có thể phân tích thành tổng các số Fibonacci từ $F_1$ tới $F_{m_N}$ nên ta chỉ cần chứng minh phân tích Fibonacci của $d_N$ không chứa số nào lớn hơn $F_{m_N}$ để khẳng định tính đúng đắn của $H$. Thật vậy, ta có thể chứng minh một khẳng định mạnh hơn:

Mệnh đề

$$d_N < F_{m_N}$$

Giả sử rằng $d_N \ge F_{m_N}$. Khi đó \[S{'_N} = \sum\limits_{k = 1}^{{m_N} - 1} {{F_k}}  = {S_N} - {F_{{m_N}}} \ge {S_N} - {d_N} = N\]

Điều này trái với định nghĩa của $m_N$. Vì vậy, Theorem được chứng minh. Nghĩa là thuật toán $H$ sẽ cho ta một phân tích Fibonacci đúng

Bài viết đã được chỉnh sửa nội dung bởi perfectstrong: 04-01-2025 - 18:44

[perfectstrong]

Câu 2c.

Giả sử phân tích Fibonacci dài nhất của $N$ cho ta bộ chỉ số $i^*_1 > i^*_2 > \ldots > i^*_{L^*(N)}$

Và phân tích Fibonacci của thuật toán $H$ cho số $N$ đưa ra bộ $i^H_1 > i^H_2 > \ldots > i^H_{L^H(N)}$ sao cho $L^*(N) > L^H(N)$

Ta cần đánh giá các bộ chỉ số này để so sánh độ dài của chúng.

Mệnh đề

Trong phân tích Fibonacci dài nhất, chỉ số của hai số hạng liên tiếp sẽ không cách nhau quá 2 đơn vị.\[i_k^* \le i_{k + 1}^* + 2 \quad \forall k : 1 \le k < L^*(N)\]

Chứng minh

Giả sử $i^*_k \ge i^*_{k+1} + 3$. Khi đó, ta có thể thay số hạng $F_{i^*_k}$ bằng $F_{i^*_k - 1}$ và $F_{i^*_k - 2}$, và thu được một phân tích Fibonacci dài hơn: vô lý với định nghĩa của bộ chỉ số $(i^*_k)$.

Mệnh đề

Phân tích Fibonacci bằng $H$ luôn chứa số Fibonacci thứ $m_N$ là số hạng lớn nhất: $${i_1^H} = m_N$$

Chứng minh

Từ Theorem, ta thấy ngay phân tích Fibonacci của $d_N$ không chứa $F_{m_N}$. Nên khi loại bỏ các phần tử trong $S_N$, ta sẽ không xóa $F_{m_N}$. Vì thế, phân tích Fibonacci bằng $H$ sẽ luôn giữ lại số Fibonacci thứ $m_N$.

Mệnh đề

$$m_N - 1 \le i^*_1 \le m_N + 1$$

Chứng minh

Để chứng minh, ta sẽ cần sử dụng tính chất sau của tổng liên tiếp các số Fibonacci:

Mệnh đề

\[\sum\limits_{k = 1}^n {{F_k}}  = {F_{n + 2}} - 2\]

Áp dụng vào, ta có:

Nếu $i^*_1 \le m_N - 2$ thì \[\sum\limits_{k = 1}^{{L^*}\left( N \right)} {{F_{i_k^*}}}  \le \sum\limits_{k = 1}^{i_1^*} {{F_k}}  = {F_{i_1^* + 2}} - 2 \le {F_{{m_N}}} - 2 < N : \text{ vô lý}\]

Nếu $i^*_1 \ge m_N + 2$ thì \[{F_{i_1^*}} \ge {F_{{m_N} + 2}} = 2 + \sum\limits_{k = 1}^{{m_N}} {{F_k}}  \ge 2 + \sum\limits_{k = 1}^{{L^H}\left( N \right)} {{F_{i_k^H}}}  = 2 + N > N : \text{ vô lý}\]

Mệnh đề

Trong phân tích Fibonacci dài nhất, số hạng nhỏ nhất là $F_1$ hoặc $F_2$.\[i_{{L^*}\left( N \right)}^* \in \left\{ {1,2} \right\}\]

Chứng minh

Thật vậy, nếu $i_{{L^*}\left( N \right)}^* \ge 3$ thì ta có thể thay $F_{i_{{L^*}\left( N \right)}^*}$ bằng $F_{i_{{L^*}\left( N \right)}^* - 1}$ và $F_{i_{{L^*}\left( N \right)}^* - 2}$ để thu được một phân tích dài hơn: trái với định nghĩa của bộ chỉ số $(i^*_k)$.

 

... (Còn nữa, mình vẫn còn đang giải )

Bài viết đã được chỉnh sửa nội dung bởi perfectstrong: 19-01-2025 - 19:40

[perfectstrong]

Mình vẫn chưa chứng minh hay phủ nhận $H$ là tối ưu Tạm thời cứ mò thêm vài tính chất.

Mệnh đề

$$m_N \le \phi(N) \le m_N + 1$$

Chứng minh

Theo định nghĩa của $m_N$:

\[\sum\limits_{k = 1}^{{m_{N - 1}}} {{F_k}}  < N \le \sum\limits_{k = 1}^{{m_N}} {{F_k}}  \Leftrightarrow {F_{{m_N} + 1}} - 2 < N \le {F_{{m_N} + 2}} - 2 \Leftrightarrow {F_{{m_N} + 1}} < N + 2 \le {F_{{m_N} + 2}}\]

Nếu $N \ge F_{m_N+1}$ thì $\phi(N)=m_N+1$.

Nếu $N < F_{m_N+1}$ (cụ thể là $N=F_{m_N+1}-1$) thì $\phi(N)=m_N$. Ta có đpcm

Mệnh đề

Nếu $N$ có dạng $F_{n}-2$ thì kết quả của $H$ là tối ưu.

Chứng minh

Giả sử tồn tại $n$ để $N=F_n - 2$, thì theo Theorem, ta có \[N = {F_n} - 2 = \sum\limits_{k = 1}^{n - 2} {{F_k}}  \Rightarrow {m_N} = n - 2\]

Nếu $L^*(N) > L^H(N)$ thì $N$ sẽ viết được thành tổng của ít nhất $n-1$ số Fibonacci khác nhau. Tổng này sẽ lớn hơn tổng của $n-2$ số Fibonacci đầu tiên, lại chính là $N$: vô lý. Do đó, $H$ tối ưu trong trường hợp này.

[perfectstrong]

Tương tự như Theorem, ta chứng minh được một trường hợp khác mà $H$ tối ưu:

Mệnh đề

Nếu $N$ có dạng $F_n - 2 - F_j$ với $j<n$ thì kết quả của $H$ là tối ưu.

Còn TH $F_n - 2 - F_{j_1} - F_{j_2}$ thì mình vẫn đang suy nghĩ

[perfectstrong]

Ta có thể làm chặt Theorem thêm một chút:

Mệnh đề

$$m_N \le i_1^*$$

Chứng minh

Thật vậy, nếu $i_1^* = m_N-1$ thì \[N = \sum\limits_{k = 1}^{{L^*}\left( N \right)} {{F_{i_k^*}}}  \le \sum\limits_{k = 1}^{{m_N} - 1} {{F_k}} \]

Mà theo định nghĩa của $m_N$ thì \[\sum\limits_{k = 1}^{{m_N} - 1} {{F_k}}  < N \le \sum\limits_{k = 1}^{{m_N}} {{F_k}} : \text{ mâu thuẫn}\]

Do đó, ta có đpcm.

 

Tuy nhiên, mình chưa chứng minh được nếu $i_1^*=m_N+1$ thì sẽ dẫn tới vô lý

Bài viết đã được chỉnh sửa nội dung bởi perfectstrong: 17-01-2025 - 03:36

[perfectstrong]

Cuối cùng cũng chứng minh được $H$ là tối ưu

 

Giả sử $i_1^*=m_N + 1$, ta chứng minh rằng

\begin{equation}\label{N_lb} N = \sum\limits_{k = 1}^{{L^*}\left( N \right)} {{F_{i_k^*}}}  \ge {F_{{m_N} + 2}} - 1\end{equation}

Thật vậy, từ Theorem, ta đã có hai số hạng liên tiếp trong phân tích Fibonacci dài nhất sẽ có chỉ số Fibonacci cách nhau $1$ hoặc $2$.

TH1: Nếu tất cả các chỉ số Fibonacci đều cách nhau $2$ đơn vị : $i_k^* = i_{k + 1}^* + 2 \, \forall k$

Khi đó, $N$ có thể viết thành : \[N = {F_{i_1^*}} + {F_{i_1^* - 2}} + {F_{i_1^* - 4}} +  \ldots \]

Chú ý rằng, do Theorem, tổng xen kẽ trên sẽ kéo dài đến $F_1$ hoặc $F_2$, tùy theo $i_1^*$ lẻ hay chẵn. Vì vậy, ta có thể áp dụng Theorem:

\[N = {F_{i_1^*}} + {F_{i_1^* - 2}} + {F_{i_1^* - 4}} +  \ldots  = {F_{i_1^* + 1}} - 1 = {F_{{m_N} + 2}} - 1: \text{ thỏa mãn \eqref{N_lb}}\]

TH2: Nếu tồn tại một chỉ số $i^*_{t}$ và $i^*_{t+1}$ nào đó sao cách nhau $1$ đơn vị: $i_t^*=i_{t+1}^*+1$

Ta chọn $t$ nhỏ nhất. Nghĩa là $i_{k}^* = i_{k+1}^*+2$ với mọi $k<t$. Ta viết $N$ thành:

\begin{align*}
N& = {F_{i_1^*}} + {F_{i_1^* - 2}} + {F_{i_1^* - 4}} +  \ldots  + {F_{i_1^* - 2\left( {t - 2} \right)}} + {F_{i_1^* - 2\left( {t - 1} \right)}} + {F_{i_1^* - 2\left( {t - 1} \right) - 1}} + {F_{i_{t + 2}^*}} +  \ldots \\
 & \ge {F_{i_1^*}} + {F_{i_1^* - 2}} + {F_{i_1^* - 4}} +  \ldots  + {F_{i_1^* - 2\left( {t - 2} \right)}} + \underbrace {{F_{i_1^* - 2\left( {t - 1} \right)}} + {F_{i_1^* - 2\left( {t - 1} \right) - 1}}}_{}\\
& = {F_{i_1^*}} + {F_{i_1^* - 2}} + {F_{i_1^* - 4}} +  \ldots  + {F_{i_1^* - 2\left( {t - 2} \right)}} + {F_{i_1^* - 2\left( {t - 1} \right) + 1}}\\
& = {F_{i_1^*}} + {F_{i_1^* - 2}} + {F_{i_1^* - 4}} +  \ldots  + \underbrace {{F_{i_1^* - 2\left( {t - 2} \right)}} + {F_{i_1^* - 2\left( {t - 2} \right) - 1}}}_{}\\
& = {F_{i_1^*}} + {F_{i_1^* - 2}} + {F_{i_1^* - 4}} +  \ldots  + {F_{i_1^* - 2\left( {t - 2} \right) + 1}}\\
 &= {F_{i_1^*}} + {F_{i_1^* - 2}} + {F_{i_1^* - 4}} +  \ldots  + {F_{i_1^* - 2\left( {t - 3} \right) - 1}}\\
 &= ...\\
 &= {F_{i_1^*}} + {F_{i_1^* - 2}} + \underbrace {{F_{i_1^* - 4}} + {F_{i_1^* - 5}}}_{}\\
 &= {F_{i_1^*}} + \underbrace {{F_{i_1^* - 2}} + {F_{i_1^* - 3}}}_{}\\
 &= {F_{i_1^*}} + {F_{i_1^* - 1}}\\
 &= {F_{i_1^* + 1}}\\
 &= {F_{{m_N} + 2}} : \text{ thỏa mãn \eqref{N_lb}}
\end{align*}

Như vậy, \eqref{N_lb} được chứng minh. Thế nhưng, điều này lại mâu thuẫn với định nghĩa của $m_N$ vì $N \le \sum\limits_{k = 1}^{{m_N}} {{F_k}}  = {F_{{m_N} + 2}} - 2$ (áp dụng Theorem).

Vì vậy, ta không thể có $i_1^*=m_N+1$. Nghĩa là ta luôn luôn có $i_1^*=m_N$.

 

Đến đây, ta áp dụng nguyên lý cực hạn: dễ dàng kiểm tra được $H$ tối ưu với $N$ từ $1$ đến $5$.

Gọi $N_0$ là số nguyên dương đầu tiên mà $H$ không đưa ra đáp án tối ưu. Với chứng minh trên, ta thấy rằng số $N_1=N_0 - F_{m_N}$ là một số nguyên dương nhỏ hơn $N_0$ nhưng lại có một phân tích (dùng bộ chỉ số $i_2^* > i_3^* >  \ldots  > i_{{L^*}\left( {{N_0}} \right)}^*$) dài hơn phân tích bằng $H$ (dùng bộ chỉ số $i_2^H > i_3^H >  \ldots  > i_{{L^H}\left( {{N_0}} \right)}^H$): mâu thuẫn.

 

Do đó, ta kết luận $H$ là thuật toán tối ưu để tìm phân tích Fibonacci dài nhất.

Đáp án cho câu $2c$ là $a=0$ và $b=1$.

[hxthanh]

Perfect!
Chứng minh tính đúng đắn cho một nhận định cảm quan quả nhiên là một điều phi thường! Như vậy với thuật toán H, ta luôn tìm ra cách phân tích một số nguyên dương thành tổng các số Fibonacci có độ dài tổng lớn nhất, nếu đó là tổng duy nhất thì perfect luôn!
Phán đoán thực chất là một chuỗi phép thử, có thể trực tiếp cũng có thể gián tiếp, có thể đúng cũng có thể sai, nhưng nhờ đó mà ta tìm ra hướng giải quyết bài toán.
Ngày trước, khoảng năm 1994-1995 gì đó, khi mà computer còn khá xa lạ, hiếm hoi và kém hấp dẫn. Nhà nào có điều kiện thì lắp điện thoại cố định, việc hiển thị số gọi đến còn là dịch vụ của nhà cung cấp thì “intelligent phone” còn là khái niệm ngoài vũ trụ và chưa được Apple đăng ký độc quyền. Lúc đó lũ bạn tôi có một chiếc “từ điển điện tử Anh-Pháp-Việt” mang đến lớp tranh giành nhau như một món bảo bối. Nội dung trong chiếc “smart-dict” đó gồm có: từ điển Anh-Việt, từ điển Việt-Anh và từ điển Pháp-Việt, ngoài ra còn một vài ứng dụng như Calculator cơ bản, âm lịch, rắn săn mồi,… tất cả trong một bộ nhớ khiêm tốn khoảng 500MB. Trong số ít ỏi các ứng dụng đó tôi đặc biệt hứng thú với trò chơi “Đoán Số”, nội dung nó như sau:

Bài toán

Một mật mã gồm 4 chữ số đôi một khác nhau, mỗi lần nhập máy sẽ trả về kết quả $ [xA, yB] $ tương ứng:
- x là số chữ số đúng, đúng vị trí
- y là số chữ số có mặt trong mật mã nhưng sai vị trí
Ví dụ: Nếu mật mã là $ 0123$, số ta nhập là $ 0327$ thì kết quả trả về là $ [2A,1B] $
Câu hỏi là số lần thử ít nhất là bao nhiêu để chắc chắn tìm ra mật mã?

Sau N lần chơi thì tôi nhận ra rằng nhiều lắm chỉ đến lần thử thứ 6 là cho kết quả đúng ( [4A,0B] )
Tuy nhiên khi bắt tay vào xây dựng thuật toán tôi lại nhận ra rằng có trường hợp đặc biệt phải dùng đến lần thử thứ 7, như sau:
Giả thiết $6789 $ là mật mã:
Một cách “may mắn”
- Lần 1: nhập: 0789 kết quả [3A,0B]
Giả sử thần linh mách bảo ta rằng $0$ là vị trí chữ số sai
Khi đó ta phải thử với các chữ số thay thế là ${1,2,3,4,5,6}$
Như vậy phải dùng đến 6 lần thử nữa mới chắc chắn tìm ra mật mã!
Qua đó mới thấy trực giác đôi khi không đáng tin lắm

[perfectstrong]

Perfect!
Chứng minh tính đúng đắn cho một nhận định cảm quan quả nhiên là một điều phi thường! Như vậy với thuật toán H, ta luôn tìm ra cách phân tích một số nguyên dương thành tổng các số Fibonacci có độ dài tổng lớn nhất, nếu đó là tổng duy nhất thì perfect luôn!
Phán đoán thực chất là một chuỗi phép thử, có thể trực tiếp cũng có thể gián tiếp, có thể đúng cũng có thể sai, nhưng nhờ đó mà ta tìm ra hướng giải quyết bài toán.
Ngày trước, khoảng năm 1994-1995 gì đó, khi mà computer còn khá xa lạ, hiếm hoi và kém hấp dẫn. Nhà nào có điều kiện thì lắp điện thoại cố định, việc hiển thị số gọi đến còn là dịch vụ của nhà cung cấp thì “intelligent phone” còn là khái niệm ngoài vũ trụ và chưa được Apple đăng ký độc quyền. Lúc đó lũ bạn tôi có một chiếc “từ điển điện tử Anh-Pháp-Việt” mang đến lớp tranh giành nhau như một món bảo bối. Nội dung trong chiếc “smart-dict” đó gồm có: từ điển Anh-Việt, từ điển Việt-Anh và từ điển Pháp-Việt, ngoài ra còn một vài ứng dụng như Calculator cơ bản, âm lịch, rắn săn mồi,… tất cả trong một bộ nhớ khiêm tốn khoảng 500MB. Trong số ít ỏi các ứng dụng đó tôi đặc biệt hứng thú với trò chơi “Đoán Số”, nội dung nó như sau:

Bài toán

Một mật mã gồm 4 chữ số đôi một khác nhau, mỗi lần nhập máy sẽ trả về kết quả $ [xA, yB] $ tương ứng:
- x là số chữ số đúng, đúng vị trí
- y là số chữ số có mặt trong mật mã nhưng sai vị trí
Ví dụ: Nếu mật mã là $ 0123$, số ta nhập là $ 0327$ thì kết quả trả về là $ [2A,1B] $
Câu hỏi là số lần thử ít nhất là bao nhiêu để chắc chắn tìm ra mật mã?

Sau N lần chơi thì tôi nhận ra rằng nhiều lắm chỉ đến lần thử thứ 6 là cho kết quả đúng ( [4A,0B] )
Tuy nhiên khi bắt tay vào xây dựng thuật toán tôi lại nhận ra rằng có trường hợp đặc biệt phải dùng đến lần thử thứ 7, như sau:
Giả thiết $6789 $ là mật mã:
Một cách “may mắn”
- Lần 1: nhập: 0789 kết quả [3A,0B]
Giả sử thần linh mách bảo ta rằng $0$ là vị trí chữ số sai
Khi đó ta phải thử với các chữ số thay thế là ${1,2,3,4,5,6}$
Như vậy phải dùng đến 6 lần thử nữa mới chắc chắn tìm ra mật mã!
Qua đó mới thấy trực giác đôi khi không đáng tin lắm

Cảm ơn thầy Thanh đã theo dõi series tự biên tự diễn của em

 

Em có học tí lập trình về thuật toán $H'$, nhưng khi đi thi Tin học trẻ (bài 4 trong https://diendantoanh...ẵng-2010-2011/)thì lại gặp một bài như đề đã ra (phân tích dài nhất bằng các số hạng trong bảng, không nhất thiết là số Fibonacci), nên em tự "chế" ra cái thuật toán $H$ kia. May sao nó lại chạy được với bài test của giám khảo Giờ ngẫm lại thì lúc đó em gặp may quá. Có điều không biết nếu giới hạn trong mỗi các số Fibonacci thì $H$ có tối ưu không. Mãi giờ mới chứng minh được, mừng húm

 

Bài toán của thầy Thanh cũng rất thú vị Thầy mở một topic riêng để mọi người cùng thảo luận đi.

Bài viết đã được chỉnh sửa nội dung bởi perfectstrong: 20-01-2025 - 15:59

[perfectstrong]

Chà, tìm kiếm thêm một tí thì quả thật đã có tiền bối chứng minh cái này rồi

$H'$ thật sự có tên gọi là Zeckendorf encoding https://en.wikipedia...ndorf's_theorem

Còn $H$ là lazy Fibonacci representation Tác giả còn chứng minh cả tính duy nhất của phân tích.

https://www.tandfonl...7.1965.12431449

Một dãy số OEIS về số chữ số của phân tích này https://oeis.org/A095791

Một link khá hay về số Fibonacci có nói về cách phân tích Fibonacci https://r-knott.surr...cci/fibrep.html