Câu hỏi 5
(FRG 5) Có $2^n$ từ độ dài $n$ trên bảng chữ cái $\{0,1\}$. Chứng minh rằng thuật toán sau sinh ra dãy $w_0,w_1,\ldots,w_{2^n-1}$ gồm tất cả các từ ấy, sao cho hai từ liên tiếp bất kỳ khác nhau đúng một chữ số.
(1) $w_0=00\ldots0$ (gồm $n$ chữ số không).
(2) Giả sử $w_{m-1}=a_1a_2\ldots a_n$, $a_i\in\{0,1\}$. Gọi $e(m)$ là số mũ của $2$ trong phân tích $n$ thành tích các thừa số nguyên tố, và đặt $j=1+e(m)$. Thay chữ số $a_j$ trong từ $w_{m-1}$ bằng $1-a_j$. Từ thu được là $w_m$.
(1) $w_0=00\ldots0$ (gồm $n$ chữ số không).
(2) Giả sử $w_{m-1}=a_1a_2\ldots a_n$, $a_i\in\{0,1\}$. Gọi $e(m)$ là số mũ của $2$ trong phân tích $n$ thành tích các thừa số nguyên tố, và đặt $j=1+e(m)$. Thay chữ số $a_j$ trong từ $w_{m-1}$ bằng $1-a_j$. Từ thu được là $w_m$.