Test Set 1

Bất kể ta định làm gì, giám khảo xoay ngẫu nhiên trong Test Set này vẫn có thể phá hỏng kế hoạch. Nhưng ta có thể chống lại tính ngẫu nhiên bằng chính tính ngẫu nhiên.

Trước hết, nếu giám khảo từng báo rằng bản ghi có tám bit \(1\), ta gần như đã thắng, miễn còn ít nhất một lượt tương tác. Chỉ cần gửi 11111111; dù giám khảo xoay thế nào, kết quả XOR cũng là 00000000. Vì vậy, nếu được báo rằng bản ghi có nhiều hơn bốn bit \(1\), ta nên nhắm đến tám bit \(1\) thay vì không bit \(1\) nào.

Tạm giả sử giám khảo cho biết bản ghi có \(b\) bit \(1\), với \(1\le b\le4\); các trường hợp còn lại được xử lý đối xứng như trên. Ta chọn đều ngẫu nhiên một chuỗi có đúng \(b\) bit \(1\) rồi gửi chuỗi đó. Khi ấy cách giám khảo xoay chuỗi không còn quan trọng: mọi chuỗi xoay thu được cũng có xác suất được ta chọn ngay từ đầu như nhau.

Các kết quả có thể là gì? Giả sử \(b=2\). Ta có xác suất

lật đúng cả hai bit \(1\) và do đó chiến thắng; xác suất

lật một trong hai bit \(1\) cùng một bit \(0\) vô can, nên quay lại trạng thái \(b=2\); và xác suất

bỏ lỡ cả hai bit \(1\) rồi tạo thêm hai bit \(1\), đưa ta đến \(b=4\). Thoạt nhìn điều này chưa hứa hẹn, nhưng hãy tiếp tục.

Phân tích tương tự tại \(b=4\) cho thấy ta đi đến một trong các giá trị \(b=0,2,4,6,8\) với xác suất lần lượt là

Như đã nói, ở \(b=6\) về bản chất giống \(b=2\): ta có thể dùng hai bit \(1\) để cố lật hai bit \(0\) và đạt 11111111. Tương tự, \(b=8\) về cơ bản tốt như \(b=0\). Gộp \(b=6\) vào \(b=2\) và \(b=8\) vào \(b=0\), xác suất chuyển sang \(b=0,2,4\) lần lượt là \(1/35,16/35,18/35\).

Nếu \(b\) chẵn, ta bị giữ trong “vũ trụ \(b\) chẵn”, bước ngẫu nhiên theo các xác suất chuyển trên cho đến khi đạt \(b=0\), đạt \(b=8\), hoặc hết lượt đoán. Nếu ban đầu chưa ở vũ trụ \(b\) chẵn, một lượt gửi chuỗi có đúng \(\min(b,8-b)\) bit \(1\) đặt ngẫu nhiên sẽ đưa ta vào đó; phần chứng minh được để lại như một bài tập. Do vậy, chiến lược là dùng tối đa hai lượt để vào trạng thái \(b\) chẵn, tối đa \(297\) lượt bước ngẫu nhiên, và tối đa một lượt cuối để biến 11111111 thành 00000000 nếu cần.

Xác suất thành công trong \(297\) lượt là bao nhiêu? Trước khi thắng tại 00000000 hoặc 11111111, ta luôn ở một trong hai trạng thái: \(b=2\) (gộp cả \(b=6\)) hoặc \(b=4\). Ở trạng thái đầu, xác suất chuyển đến trạng thái thắng là \(1/28\); ở trạng thái sau là \(1/35\). Để lập luận đơn giản, hãy bi quan giả sử ta luôn mắc ở trạng thái kém thuận lợi hơn là \(b=4\). Khi đó, để không thắng ta vẫn phải trượt phép thử xác suất \(1/35\) cả \(297\) lần. Xác suất ấy là

Vì vậy chiến lược thành công với xác suất ít nhất \(99.98\%\), và đây còn là một cận dưới quá thận trọng.

Nếu muốn biết xác suất thực, ta có thể tiếp tục thận trọng giả sử hành trình luôn bắt đầu tại \(b=4\), rồi lấy ô trên cùng bên trái của

thu được khoảng \(0.99993\approx99.993\%\).

Dĩ nhiên ta vẫn phải vượt qua cả 100 bộ test của Test Set 1, nên xác suất nhỏ hơn một chút: khoảng \(0.99993^{100}\approx0.993\). Tuy vậy, \(99.3\%\) vẫn khá tốt; nếu không may thất bại, ta dễ dàng có một lần thử độc lập khác bằng cách đổi hạt giống ngẫu nhiên trong mã, vì nguồn ngẫu nhiên ấy do ta kiểm soát.

Test Set 2

Trong Test Set 2, giám khảo không hành xử ngẫu nhiên mà có thể và sẽ chọn các độ xoay để ngăn ta đạt mục tiêu. Vì vậy cần một chiến lược được bảo đảm đưa bản ghi về toàn bit \(0\).

Một cách là xét trạng thái hiện tại. Định nghĩa trạng thái là tập tất cả các giá trị mà bản ghi có thể đang mang. Nhận xét then chốt là hai giá trị là phép xoay vòng của nhau thì tương đương, nên có thể loại các bản sao xoay vòng khỏi tập. Sau lượt trao đổi đầu tiên, ta biết số bit \(1\) trong bản ghi; vì thế mọi giá trị khả dĩ trong một trạng thái đều có cùng số bit \(1\).

Liệt kê mọi giá trị theo số bit \(1\), đồng thời bỏ các giá trị là phép xoay vòng của giá trị khác, ta được:

• 0 bit: \(\{00000000\}\).
• 1 bit: \(\{00000001\}\).
• 2 bit: \(\{00000011,00000101,00001001,00010001\}\).
• 3 bit: \(\{00000111,00001011,00001101,00010011,00010101,00011001,00100101\}\).
• 4 bit: \(\{00001111,00010111,00011011,00011101,00100111,00101011,00101101,00110011,00110101,01010101\}\).
• 5 bit: \(\{00011111,00101111,00110111,00111011,00111101,01010111,01011011\}\).
• 6 bit: \(\{00111111,01011111,01101111,01110111\}\).
• 7 bit: \(\{01111111\}\).
• 8 bit: \(\{11111111\}\).

Tập lớn nhất, ứng với 4 bit \(1\), chỉ có 10 phần tử. Do đó có nhiều nhất \(2^{10}=1024\) trạng thái khác nhau khi có 4 bit bật. Số lượng này đủ nhỏ để xét mọi trạng thái bằng một quy trình tương tự BFS bắt đầu từ trạng thái toàn bit \(0\).

Cụ thể, ta duy trì tập các trạng thái mà ta biết có thể ép đi tới toàn bit \(0\); ban đầu tập chỉ chứa trạng thái đã giải 00000000. Với một trạng thái \(A\), thử mọi giá trị \(V\) có thể và mô phỏng kết quả của cả tám độ xoay mà giám khảo có thể chọn. Nhóm các kết quả theo số bit \(1\) để thu được những trạng thái mà \(A\) có thể chuyển tới khi dùng \(V\). Nếu tất cả các trạng thái kết quả đều đã được xử lý, ta biết rằng tại \(A\) có thể dùng \(V\) để tiến gần hơn đến việc đưa bản ghi về toàn bit \(0\).

Nếu lặp quy trình trên, cuối cùng mọi trạng thái khả dĩ đều được xử lý. Nhờ đó ta có chỉ dẫn phải cung cấp giá trị \(V\) nào với mỗi trạng thái hiện tại. Lời giải thay thế và chứng minh bên dưới cho thấy việc này luôn khả thi đối với bản ghi \(8\) bit.

Lời giải thay thế

Ta có thể giải bài toán mà không cần biết số bit \(1\) sau các tương tác, ngoại trừ tín hiệu cho biết cuối cùng đã đạt 00000000.

Trước hết xét bản ghi chỉ có 1 bit. Vì giá trị ban đầu được biết là khác \(0\), ta ép nó về \(0\) bằng cách gửi 1. Gọi dãy này là \(P[0]\):

1

Tiếp theo xét bản ghi 2 bit, không phải toàn bit \(0\). Ban đầu giả sử hai bit giống nhau. Nếu đúng, gửi 11 sẽ ép bản ghi về toàn bit \(0\). Nếu sau đó vẫn chưa về toàn bit \(0\), giả sử ban đầu là sai: bit trái và bit phải khác nhau. Khi ấy gửi 10 có thể làm chúng giống nhau; nếu vẫn chưa toàn bit \(0\), gửi thêm 11. Gọi dãy này là \(P[1]\):

11    // P[0] + P[0]
10    // P[0] + 0
11    // P[0] + P[0]

Tổng quát, giả sử bản ghi có \(2^k\) bit và không phải toàn bit \(0\). Giả sử \(2^{k-1}\) bit bên trái giống hệt \(2^{k-1}\) bit bên phải. Nếu đúng, ta có thể dùng \(P[k-1]\), nhưng nối mỗi chỉ dẫn với chính nó, để ép bản ghi về toàn bit \(0\). Nếu vẫn chưa về toàn bit \(0\), giả sử hai nửa giống nhau là sai.

Khi đó, dùng chỉ dẫn đầu tiên trong \(P[k-1]\) rồi nối thêm \(2^{k-1}\) ký tự 0. Sau đó lặp lại toàn bộ \(P[k-1]\), với mỗi bước được nhân đôi như trước. Miễn vẫn chưa đạt toàn bit \(0\), tiếp tục quy trình này với chỉ dẫn kế tiếp trong \(P[k-1]\).

Đoạn Python sau thể hiện chính xác quy trình sinh \(P[3]\) cho bản ghi \(8\) bit:

def appendzero(s):
  return s + '0' * len(s)

def expand(s):
  return s + s

def P(k):
  if k == 0:
      return ['1']
  seq = P(k - 1)
  seq_with_zero = [appendzero(s) for s in seq]
  seq_with_copy = [expand(s) for s in seq]
  res = seq_with_copy[:]
  for ins in seq_with_zero:
      res += [ins]
      res += seq_with_copy
  return res

print(P(3))

Lời giải này được dịch đầy đủ từ bản phân tích chính thức của Google Code Jam 2022, Vòng 1B.