Câu 4 (5 điểm). Bạn An chơi trò chơi ghi lên bảng các bộ ba số theo thứ tự từ trái sang phải. Ban đầu trên bảng ghi sẵn bộ ba số $(1,1,1)$. Ở mỗi lượt chơi, An thực hiện một trong hai thao tác sau với bộ ba số $(x,y,z)$ hiện có:
(i) Xóa bộ ba số $(x,y,z)$ và viết lên bảng bộ ba số $(y,z,x+z)$.
(ii) Xóa bộ ba số $(x,y,z)$ và viết lên bảng bộ ba số $(x+z+1,x+y+z+1,x+y+2z+1)$.
a) Chứng minh An cần đúng 4 lượt chơi để có thể viết lên bảng bộ ba số $(a,b,6)$.
b) Tìm số tự nhiên $k$ nhỏ nhất sao cho tồn tại một cách chơi để sau $k$ lượt, An có thể viết lên bảng bộ ba số $(c,d,129)$.

a) Xét lượt đầu tiên, nếu sử dụng thao tác loại 2 thì ta có bộ số $(3,4,5)$ và từ đây số ngoài cùng bên phải sẽ luôn tăng ít nhất 3 đơn vị nên không thể viết được số 6. Như vậy lượt đầu An phải sử dụng loại 1 và viết bộ số $(1,1,2)$.
Từ trạng thái này, nếu sử dụng thao tác loại 2 sẽ tăng số ngoài cùng bên phải lên ít nhất 5. Do đó, nếu sử dụng thao tác loại 2 trong các trạng thái tiếp theo thì An không thể viết được số 6.
Tóm lại, An chỉ sử dụng thao tác loại 1 và sau đúng 4 lượt chơi, các bộ số trên bảng lần lượt là: $(1,1,2)\to (1,2,3)\to (2,3,4)\to (3,4,6)$.

b) Xét dãy số ${\left(a_k\right)}_{k\ge 1}$ xác định bởi: $a_1=a_2=a_3=1$ và $a_{k+3}=a_{k+2}+a_k$ với mọi $k\ge 1$.

Nhận xét 1. Một số nguyên dương $n$ bất kỳ biểu diễn được một cách duy nhất dưới dạng tổng các số hạng phân biệt của dãy ${\left(a_k\right)}_{k\ge 1}$, trong đó chỉ số của hai số cách nhau ít nhất 3 đơn vị và không có số hạng nào là $a_1$, $a_2$. Ta chứng minh nhận xét bằng quy nạp mạnh.
Trường hợp $n=1=a_3$ : đúng.
Giả sử mệnh đề đúng với mọi số nguyên dương nhỏ hơn $n$. Gọi $a_k$ là số hạng với chỉ số $k$ lớn nhất thỏa mãn $a_k\le n$. Trong biểu diễn của $n$ phải có $a_k$, vì bằng quy nạp ta có $a_{k-1}+a_{k-4}+\dots <a_k$. Khi đó xảy ra 2 trường hợp: hoặc $n=a_k$ là biểu diễn duy nhất; hoặc $n>a_k$ và tồn tại biểu diễn cho $n-a_k$. Để ý rằng số $n-a_k$ nhỏ hơn $a_{k-2}$, vì nếu ngược lại $n\ge a_k+a_{k-2}=a_{k+1}$, mâu thuẫn với cách chọn $a_k$. Do đó, trong biểu diễn của $n-a_k$ không chứa $a_{k-1}$, $a_{k-2}$ và ta thu được biểu diễn thỏa mãn yêu cầu cho $n$.
Với mọi $n$, biểu diễn $n=\sum a_{k_i}$ trong Nhận xét 1 tương ứng với một dãy nhị phân thỏa mãn đồng thời 2 điều kiện sau đây:
1. Độ dài của dãy bằng $k_j$, trong đó $k_j$ là chỉ số lớn nhất sao cho $a_{k_j}\le n$;
2. Vị trí thứ $k_i$ (tính từ trái sang phải) nhận giá trị 1 nếu và chỉ nếu $a_{k_i}$ có trong biểu diễn của $n$.
Ta gọi dãy nhị phân tương ứng là biểu diễn chuẩn và ký hiệu là $\bar{n}$.

Nhận xét 2. Với mỗi số tự nhiên $n$, xét biểu diễn $n=\sum a_{k_i}$ và ánh xạ $f(n)=\sum a_{k_i-1}$. Khi đó, bộ số trên bảng sẽ luôn có dạng $\left(f\left(f(n)\right),f(n),n\right)$.
Thật vậy, bộ số ban đầu có dạng $\left(a_1,a_2,a_3\right)=\left(f\left(f(1)\right),f(1),1\right)$. Giả sử bộ số $(x,y,z)$ thỏa mãn $z=\sum a_{k_i+2}$, $y=\sum a_{k_i+1}$, $x=\sum a_{k_i}$, ta kiểm tra cả hai loại thao tác đều có bộ số ở dạng trên.
Với loại 1, ta có $f(x+z)=f\left(\sum \left(a_{k_i+2}+a_{k_i}\right)\right)=f\left(\sum a_{k_i+3}\right)=\sum a_{k_i+2}=z$.
Với loại 2, ta có $f(x+y+2z+1)=f\left(\sum a_{k_i+5}+a_3\right)=\sum a_{k_i+4}+a_2=x+y+z+1$, và $f(x+y+z+1)=f\left(\sum a_{k_i+4}+a_2\right)=\sum a_{k_i+3}+a_1=x+z+1$.

Nhận xét 3. Từ tính toán ở Nhận xét 2, thao tác loại 1 tương đương với việc thêm một số 0 vào bên trái biểu diễn chuẩn của $z$ trong $(x,y,z)$ trên bảng, còn thao tác loại 2 tương đương với việc thêm 001 vào bên trái biểu diễn chuẩn của $z$.
Quay lại bài toán, để ý rằng bộ số ban đầu ta quy ước là $\left(a_1,a_2,a_3\right)$ ứng với biểu diễn chuẩn $(100,010,001)$. Do đó, bài toán tương đương với việc tìm $k$ nhỏ nhất để sau $k$ bước thêm 0 hoặc thêm 001 vào đuôi của $\overline{a_3}=001$ để được 129.
Đến đây, ta tính được 15 số hạng đầu tiên của dãy ${\left(a_k\right)}_{k\ge 1}$ là
$$1,1,1,2,3,4,6,9,13,19,28,41,60,88,129.$$
Ta suy ra biểu diễn chuẩn của 129 là 000000000000001, nên cần đúng 12 biến đổi loại 1.
Vậy $k=12$.