Câu hỏi 41
Robot "Mag-o-matic" thao tác trên 101 chiếc cốc xếp thành một hàng, các vị trí được đánh số từ 1 đến 101. Mỗi chiếc cốc có thể chứa hoặc không chứa một quả bóng. Robot Mag-o-matic chỉ nhận các lệnh cơ bản dạng $(a ; b, c)$, được hiểu là
"xét chiếc cốc ở vị trí $a$: nếu nó chứa bóng thì đổi chỗ hai chiếc cốc ở các vị trí $b$ và $c$ (cùng với vật chứa bên trong nếu có), ngược lại thì chuyển sang lệnh tiếp theo"
(ở đây $a, b, c$ là các số nguyên từ 1 đến 101, với $b$ và $c$ khác nhau, nhưng không nhất thiết khác $a$). Một chương trình là một dãy hữu hạn các lệnh cơ bản, được cho trước, mà Mag-o-matic thực hiện lần lượt.
Một tập con $S \subseteq\{0,1,2, \ldots, 101\}$ được gọi là nhận diện được nếu tồn tại một chương trình mà, xuất phát từ một cấu hình ban đầu bất kỳ, cho ra một cấu hình cuối trong đó chiếc cốc ở vị trí 1 chứa bóng khi và chỉ khi số chiếc cốc chứa bóng là một phần tử của $S$.
a. Chứng minh rằng tập con của $\{0,1, \ldots, 101\}$ gồm các số lẻ là nhận diện được.
b. Tìm tất cả các tập con nhận diện được của $\{0,1, \ldots, 101\}$.
"xét chiếc cốc ở vị trí $a$: nếu nó chứa bóng thì đổi chỗ hai chiếc cốc ở các vị trí $b$ và $c$ (cùng với vật chứa bên trong nếu có), ngược lại thì chuyển sang lệnh tiếp theo"
(ở đây $a, b, c$ là các số nguyên từ 1 đến 101, với $b$ và $c$ khác nhau, nhưng không nhất thiết khác $a$). Một chương trình là một dãy hữu hạn các lệnh cơ bản, được cho trước, mà Mag-o-matic thực hiện lần lượt.
Một tập con $S \subseteq\{0,1,2, \ldots, 101\}$ được gọi là nhận diện được nếu tồn tại một chương trình mà, xuất phát từ một cấu hình ban đầu bất kỳ, cho ra một cấu hình cuối trong đó chiếc cốc ở vị trí 1 chứa bóng khi và chỉ khi số chiếc cốc chứa bóng là một phần tử của $S$.
a. Chứng minh rằng tập con của $\{0,1, \ldots, 101\}$ gồm các số lẻ là nhận diện được.
b. Tìm tất cả các tập con nhận diện được của $\{0,1, \ldots, 101\}$.