Phân tích: Ace in the Hole

Đây là một bài toán khá khác thường: cần suy nghĩ rất nhiều từ đầu nhưng phần cài đặt lại tương đối ít.

Hãy coi bài toán như một trò chơi đối kháng. Ben chọn vị trí một lá bài, rồi Amy chọn giá trị của lá đó. Amy không được (a) dùng lại giá trị, (b) tạo một dãy con giảm độ dài 3, hoặc (c) đặt giá trị 1 trước lượt cuối. Ta cần hiểu Amy có thể đã quyết định như thế nào trong trò chơi. Trước hết nêu đáp án, sau đó chứng minh.

Định nghĩa một chiến lược đối kháng cho Amy như sau:

• Ở bất kỳ thời điểm nào, xét các lá Ben chưa xem. Giả sử vị trí của chúng là \(p_1<p_2<\cdots<p_m\) và các giá trị chưa dùng là \(v_1<v_2<\cdots<v_m\).
• Nếu Ben xem lá ở \(p_k\) với \(k<m\), Amy gán giá trị \(v_{k+1}\).
• Nếu Ben xem lá ở \(p_m\) và hoặc (a) \(m\le2\), hoặc (b) đã có một lá được lật ở vị trí nhỏ hơn \(p_m\) với giá trị nằm giữa \(v_{m-1}\) và \(v_m\), Amy gán \(v_m\). Nếu không, Amy gán một trong hai giá trị \(v_{m-1}\) và \(v_m\).

Ta khẳng định các điều kiện bài toán tương đương với việc Amy chọn giá trị bộ bài theo một chiến lược đối kháng. Khi chứng minh xong điều đó, tìm nghiệm lớn nhất theo thứ tự từ điển sẽ khá trực tiếp.

Không thể khai thác chiến lược đối kháng

Thách thức kỹ thuật chính là chứng minh chiến lược đối kháng thực sự buộc Ben xem mọi lá. Trong cuộc thi, dĩ nhiên không cần trình bày lập luận chặt chẽ đến mức này.

Bổ đề. Nếu các giá trị được gán theo chiến lược đối kháng thì bộ bài không có dãy con giảm độ dài 3.

Chứng minh. Theo dõi từng lần Ben xem một lá. Ở mỗi bước, gọi một lá là an toàn nếu Ben đã xem nó và hoặc (a) mọi lá ở vị trí lớn hơn cũng đã được xem, hoặc (b) mọi lá có giá trị lớn hơn cũng đã được xem. Giả sử các lá còn lại có vị trí \(p_1<p_2<\cdots<p_m\) và giá trị \(v_1<v_2<\cdots<v_m\). Đó là các lá không an toàn.

Ta khẳng định:

• Không thể gán các giá trị còn lại theo cách tạo ra một dãy con giảm độ dài 3 có chứa một lá an toàn.
• Nếu một lá không an toàn ở vị trí \(p_i\) đã được xem, giá trị của nó là \(v_{i+1}\).

Chứng minh khẳng định bằng quy nạp theo số lá Ben đã xem. Ban đầu mọi lá đều không an toàn và khẳng định hiển nhiên.

Giả sử Ben xem lá \(C\) tại vị trí \(p_k\).

• Trường hợp 1: \(k<m-1\). Vì Ben chưa xem lá ở \(p_m\) (nếu đã xem thì nó sẽ an toàn), giá trị của \(C\) tuân theo quy tắc đầu tiên. Cụ thể, nếu có \(q\) lá ở các vị trí nhỏ hơn \(p_k\) chưa được xem thì \(C\) nhận giá trị chưa lật nhỏ thứ \(q+1\). Vì mọi lá an toàn đã được lật, ta chỉ cần xét các lá không an toàn; giả thiết quy nạp cho thấy giá trị chưa lật nhỏ thứ \(q+1\) là \(v_{k+1}\). Do \(k+1<m\), tập lá an toàn không đổi ở bước này, nên giả thiết quy nạp tiếp tục đúng.

• Trường hợp 2: \(k=m-1\). Cùng lập luận như Trường hợp 1, \(C\) nhận \(v_m\). Tuy nhiên, tập lá an toàn thay đổi. Giả sử Ben đã xem các lá tại \(p_u,p_{u+1},\ldots,p_{m-2}\) nhưng chưa xem lá tại \(p_{u-1}\). Tất cả các lá này được đánh dấu an toàn vì có giá trị cao, còn các lá khác vẫn không an toàn. Ta cần chứng minh chúng không thể thuộc một dãy con giảm độ dài 3. Theo giả thiết quy nạp, có thể bỏ qua các lá đã an toàn từ trước. Các lá vừa trở thành an toàn được sắp tăng dần, chỉ có một lá không an toàn nằm sau chúng, và không lá không an toàn nào đứng trước có giá trị cao hơn. Vì vậy chúng không thể nằm trong dãy giảm độ dài 3, và giả thiết quy nạp lại được duy trì.

• Trường hợp 3: \(k=m\). Giả sử \(C\) nhận giá trị \(v_t\). Ta biết Ben chưa xem lá mang \(v_m\), nếu không lá ấy đã an toàn. Nếu Ben cũng đã xem lá mang \(v_{m-1}\), điều kiện đối kháng cấm \(C\) nhận giá trị nhỏ hơn \(v_{m-1}\). Nếu chưa, cả \(v_{m-1}\) và \(v_m\) đều chưa lật, và điều kiện đối kháng buộc \(C\) nhận \(v_{m-1}\) hoặc \(v_m\).

• Nếu \(t=m-1\), \(C\) được đánh dấu an toàn nhưng không lá nào khác được đánh dấu. Ben không thể đã xem lá ở \(p_{m-1}\), vì lá đó sẽ mang \(v_m\) và đã an toàn. Hơn nữa, \(C\) không thể thuộc dãy giảm độ dài 3: không lá không an toàn nào có vị trí lớn hơn và nhiều nhất chỉ một lá không an toàn có giá trị cao hơn.
• Nếu \(t=m\), một số lá bổ sung \(p_u,p_{u+1},\ldots,p_{m-2}\) cũng có thể trở thành an toàn. Các lá mới an toàn được sắp tăng dần, chỉ có một lá không an toàn nằm sau bất kỳ lá nào trong số đó, và không lá không an toàn đứng trước nào có giá trị cao hơn. Vì thế không dãy giảm độ dài 3 nào chứa chúng. Giả thiết quy nạp một lần nữa được duy trì.

Trong mọi trường hợp, giả thiết quy nạp đúng sau mỗi bước, nên bổ đề được chứng minh.

Suy ra ngay rằng Ben cần đủ \(N\) lần đoán nếu các lá được gán theo chiến lược đối kháng. Dù Ben xem những lá nào, Amy vẫn có thể tiếp tục chiến lược và tránh lộ cả dãy giảm độ dài 3 lẫn lá giá trị 1. Đặc biệt, Ben không bao giờ có thể kết thúc sớm.

Có thể khai thác các thứ tự không đối kháng

Lập luận trước quan trọng về mặt kỹ thuật, nhưng khi thực sự giải bài ta thường bắt đầu từ phía ngược lại: chỉ ra Ben khai thác chiến lược kém thế nào. Ta sẽ chứng minh rằng nếu Amy từng lệch khỏi chiến lược đối kháng, Ben có thể tìm lá 1 mà không cần đủ \(N\) lượt.

Trước tiên tập trung vào lá đầu tiên Ben xem.

Quan sát 1. Nếu Ben xem lá \(i<N\), Amy phải gán nó giá trị \(i+1\).

Lý do. Giả sử Ben thấy \(j\ne i+1\). Ta khẳng định lá 1 không thể ở vị trí \(N\). Thật vậy, nếu nó ở đó, điều kiện không có dãy giảm độ dài 3 kéo theo (a) mọi lá ở vị trí nhỏ hơn \(i\) phải có giá trị trong \([2,j-1]\), và (b) mọi lá ở vị trí từ \(i+1\) đến \(N-1\) phải có giá trị trong \([j+1,N]\). Nếu \(j<i+1\), khoảng \([2,j-1]\) không có đủ giá trị; nếu \(j>i+1\), khoảng \([j+1,N]\) không có đủ giá trị.

Vì vậy, nếu Amy gán giá trị khác \(i+1\), Ben không cần xem lá \(N\). Nhưng ta biết Ben thực sự phải xem mọi lá, nên Amy buộc phải gán \(i+1\).

Quan sát 2. Nếu Ben xem lá \(N\), Amy phải gán \(N-1\) hoặc \(N\).

Lý do. Giả sử Ben thấy \(j<N-1\). Nếu \(N=3\), Ben vừa tìm thấy lá 1, mâu thuẫn ngay. Nếu không thì \(N\ge4\); ta chỉ ra Ben có thể tìm lá 1 trong ít hơn \(N-1\) lần xem tiếp theo, cũng là mâu thuẫn.

Tạm quên thông tin Ben đã có: \(N-1\) giá trị còn lại nằm trong \(N-1\) vị trí phía trước. Theo Quan sát 1, nếu Ben xem vị trí \(i\), nó phải mang giá trị nhỏ thứ \(i+1\) trong các giá trị còn lại; nếu không, ta đã biết Ben có thể tìm lá 1 mà không xem hết. Vì vậy, nếu Ben xem mọi vị trí trừ \(N-3\) và \(N-1\), anh phải thấy:

Hai lá chưa biết mang 1 và \(N-1\) theo một thứ tự nào đó. Nhưng lá áp chót không thể mang \(N-1\), nếu không sẽ có dãy giảm \(N,N-1,j\). Do đó 1 phải ở vị trí ấy, và Ben không cần xem lá thứ tư tính từ cuối. Chứng minh hoàn tất.

Chỉ còn một trường hợp khó. Tại một thời điểm, giả sử các lá chưa lật ở \(p_1<p_2<\cdots<p_m\), với các giá trị \(v_1<v_2<\cdots<v_m\). Giả sử đã có một lá được lật ở vị trí nhỏ hơn \(p_m\), có giá trị nằm giữa \(v_{m-1}\) và \(v_m\). Ta phải chứng minh rằng nếu Ben xem \(p_m\), Amy buộc phải gán \(v_m\).

Lý do. Giả sử Amy không làm vậy, và xét lần đầu tiên cô lệch khỏi quy tắc. Gọi \(C\) là lá ở \(p_m\), và \(C'\) là lá đã lật đứng trước \(C\), có giá trị giữa \(v_{m-1}\) và \(v_m\).

Cho đến lúc này Amy đã theo chiến lược đối kháng, nên có thể dùng mệnh đề quy nạp trong bổ đề đầu để chia bộ bài thành lá an toàn và không an toàn. Có một lá chưa lật đứng sau \(C'\) — chính là \(C\) — và có một giá trị chưa lật lớn hơn giá trị \(C'\) — chính là \(v_m\) — nên \(C'\) phải không an toàn.

Gọi các lá không an toàn có vị trí \(q_1,q_2,\ldots,q_r\) và giá trị \(w_1,w_2,\ldots,w_r\). Vì \(v_{m-1}\) chưa lật, nó thuộc một lá không an toàn, nên \(v_{m-1}=w_u\) với một \(u\) nào đó. Đồng thời, \(C'\) có giá trị \(w_t\) với \(t>u\) và nằm ở vị trí \(p_{t-1}\).

Giả sử Amy gán cho \(C\) giá trị \(v_{m-1}=w_u\). Khi đó lá ở \(q_{u-1}\) phải chưa lật, nếu không nó đã có cùng giá trị. Như đã lập luận, lá ở \(q_{r-1}\) cũng phải chưa lật; nếu đã lật, nó sẽ mang \(w_r\) và đã an toàn.

Ben có thể khai thác bằng cách xem mọi lá trừ \(q_{u-1}\) và \(q_{r-1}\). Dễ kiểm tra rằng cuối cùng chỉ còn hai giá trị 1 và \(w_{u+1}\). Nhưng lá ở \(q_{r-1}\) không thể mang \(w_{u+1}\), nếu không ta có dãy giảm \(w_t,w_{u+1},w_u\). Vì thế lá này phải mang 1, và Ben có thể bỏ qua lá ở \(q_{u-1}\). Phần cuối của chứng minh hoàn tất.

Tìm nghiệm lớn nhất theo thứ tự từ điển

Cuối cùng ta có thể nói về lời giải. Ở mỗi bước, chiến lược của Amy gần như hoàn toàn xác định. Câu hỏi duy nhất là khi được chọn, cô nên gán \(v_m\) hay \(v_{m-1}\) cho lá ở \(p_m\).

Hai lựa chọn tạo ra hai thứ tự bộ bài giống hệt nhau, ngoại trừ \(v_m\) và \(v_{m-1}\) bị hoán đổi. Để thứ tự bộ bài lớn nhất theo thứ tự từ điển, ta muốn \(v_m\) xuất hiện sớm hơn, vì vậy phải luôn ưu tiên dùng \(v_{m-1}\) tại \(p_m\).

Chỉ vậy thôi: cài đặt chiến lược đối kháng và mỗi khi được chọn thì luôn ưu tiên \(v_{m-1}\) hơn \(v_m\). Dĩ nhiên, để đi đến kết luận đơn giản này cần rất nhiều lập luận!

Nguồn

Bản dịch đầy đủ dựa trên phân tích chính thức của Google Code Jam 2011 - Ace in the Hole, thuộc kho Google Coding Competitions (Apache-2.0).