Phân tích: Number Game

Hãy bắt đầu bằng cách tập trung vào một ván duy nhất. Với \(A\) và \(B\), không mất tính tổng quát, ta có thể giả sử \(A \ge B\). Làm thế nào để xác định đây có phải là một thế thắng hay không? (Không thể có ván hòa vì \(A+B\) luôn giảm.) Một thế là thế thắng khi và chỉ khi trong một nước đi, ta có thể đưa đối thủ vào một thế thua. Đây là một sự thật quan trọng trong trò chơi tổ hợp, vì vậy hãy chắc chắn rằng bạn hiểu tại sao nó đúng!

Những nhận xét, từ dễ đến không dễ

Một nhận xét hiển nhiên là \((A,A)\) là một thế thua.

Nhận xét tiếp theo khó hơn nhiều, trừ khi bạn đã từng tiếp xúc với trò chơi tổ hợp:

Nếu \(A \ge 2B\), thì \((A,B)\) là một thế thắng.

Để giải thích, trong một thế như vậy, giả sử \(k\) là số lượng \(B\) lớn nhất có thể trừ khỏi \(A\), tức là

và

Ta chưa biết \((A-kB,B)\) là thế thắng hay thế thua. Nhưng chỉ có hai khả năng. Nếu nó là thế thua thì rất tốt: ta trừ \(kB\) khỏi \(A\) và trao thế xấu đó cho đối thủ. Mặt khác, nếu nó là thế thắng, ta trừ \((k-1)B\) khỏi \(A\); đối thủ không còn lựa chọn nào khác ngoài việc trừ thêm một \(B\), qua đó trả cho ta thế thắng \((A-kB,B)\). Do đó, trong cả hai trường hợp, \((A,B)\) đều là thế thắng!

Mở rộng thêm

Nhận xét trên cho ta một thuật toán khá nhanh để xác định người thắng trong một ván \((A,B)\). Thay vì dùng quy hoạch động để giải mọi bài toán con \((A',B')\) với \(A' \le A\) và \(B' \le B\), vốn là cách phân tích phổ biến nhất cho kiểu trò chơi này, ta có thể làm như sau:

Vòng 1: Nếu \(A \ge 2B\), đây là thế thắng và ta đã xong. Nếu không, ta chỉ có một lựa chọn: trừ \(B\) khỏi \(A\), rồi trao cho đối thủ thế \((B,A-B)\).

Vòng 2: Nếu \(B \ge 2(A-B)\), đây là thế thắng của đối thủ. Nếu không, lựa chọn duy nhất của đối thủ là trừ (A-B) khỏi \(B\), rồi trao lại cho ta thế \((A-B,2B-A)\).

Vòng 3: Nếu \(A-B \ge 2(2B-A)\), đây lại là thế thắng của ta. Nếu không, ta sẽ biến nó thành \((2B-A,2A-3B)\).

Và cứ tiếp tục như vậy. Điều này dẫn đến thuật toán sau để giải hiệu quả một ván \((A,B)\), với giả sử \(A \ge B\):

  bool winning(int A, int B) {
    if (B == 0) return true;
    if (A >= 2*B) return true;
    return !winning(B, A-B);
  }

Nghe có quen không? Một mối liên hệ bạn có thể nhận ra là Number Game rất giống thuật toán Euclid để tìm ước chung lớn nhất. Không khó để thấy rằng thuật toán này, giống như Euclid, sẽ chỉ cần đệ quy nhiều nhất \(O(\log A)\) lần.

Đáng tiếc, ta vẫn không thể chạy thuật toán cho mọi cặp \((A,B)\) có thể có! Để giải bài toán, ta cần xử lý nhiều thế cùng lúc. Hãy đi qua các vòng tương tự, nhưng tưởng tượng rằng \(B\) được cố định và ta xét đồng thời mọi giá trị \(A\):

• Vòng 1: \((A,B)\). Nếu \(A \ge 2B\), tức \(A/B \ge 2\), thì \((A,B)\) là thế thắng.
• Vòng 2: \((B,A-B)\). Nếu \(B \ge 2(A-B)\), tức \(A/B \le 3/2\), thì \((A,B)\) là thế thua.
• Vòng 3: \((A-B,2B-A)\). Nếu \(A-B \ge 2(2B-A)\), tức \(A/B \ge 5/3\), thì \((A,B)\) là thế thắng.
• Vòng 4: \((2B-A,2A-3B)\). Nếu \(2B-A \ge 2(2A-3B)\), tức \(A/B \le 8/5\), thì \((A,B)\) là thế thua.

Và cứ tiếp tục như vậy.

Điều này cho ta một lời giải đủ nhanh. Với mỗi \(B\), ta xét mọi \(A\) theo cách trên, và trong \(O(\log 10^6)\) vòng, ta có thể phân loại tất cả các giá trị \(A\).

Đơn giản hóa

Phương pháp trên hoàn toàn đúng, nhưng có thể làm cho đơn giản hơn. Trước hết, trong danh sách trên có điều gì trông quen thuộc không? Các số Fibonacci xuất hiện khắp nơi! Gọi \(F(i)\) là số Fibonacci thứ \(i\). Có thể dùng quy nạp để chỉ ra rằng phân tích trước thực chất nói rằng:

• Vòng \(2t-1\): Nếu
  [
  A/B \ge F(2t+1)/F\(2t\),
  ]
  thì \((A,B)\) là thế thắng.
• Vòng \(2t\): Nếu
  [
  A/B \le F(2t+2)/F(2t+1),
  ]
  thì \((A,B)\) là thế thua.

Hóa ra cả (F(2t+1)/F\(2t\)) lẫn (F(2t+2)/F(2t+1)) đều tiến tới tỉ lệ vàng

khi \(t\) tăng. Điều này cho ta một đặc trưng rất đơn giản của mọi thế thắng!

Định lý: \((A,B)\) là một thế thắng khi và chỉ khi

Với định lý này, việc giải bài toán trở nên dễ dàng. Duyệt qua từng giá trị \(B\), rồi đếm xem có bao nhiêu giá trị \(A\) thỏa (A ≥ \varphi B).

Vì sao lại là tỉ lệ vàng?

Một khi đã tình cờ tìm ra phát biểu của định lý, việc chứng minh thực ra khá dễ. Đây là một cách: dùng quy nạp toán học, giả sử ta đã chứng minh định lý cho mọi \(A\) và \(B\) nhỏ hơn. Nếu \(A \ge 2B\), thì \((A,B)\) là thế thắng như đã thảo luận. Nếu không, ta sẽ để lại cho đối thủ thế \((B,A-B)\). Khi đó, \((A,B)\) thắng khi và chỉ khi \((B,A-B)\) thua. Theo giả thiết quy nạp, điều này tương đương với

hay

Vì

điều này chứng minh \((A,B)\) thắng khi và chỉ khi (A ≥ \varphi B), đúng như yêu cầu.

Sau đây là một góc nhìn hình học khác. Bạn bắt đầu với một tờ giấy hình chữ nhật kích thước \(A\) nhân \(B\), với \(A \ge B\), rồi cắt khỏi nó một hình vuông \(B\) nhân \(B\). Nếu hình chữ nhật là hình chữ nhật vàng, nghĩa là \(A=\varphi B\), thì hình chữ nhật còn lại cũng là hình chữ nhật vàng. Trong trò chơi của ta, \(A\) và \(B\) là số nguyên, nên hình chữ nhật không bao giờ là hình chữ nhật vàng. Ta gọi nó là mỏng nếu \(A>\varphi B\), và gọi là béo trong trường hợp còn lại. Từ một hình chữ nhật mỏng, bạn luôn có thể cắt để thu được một hình chữ nhật béo; còn từ một hình chữ nhật béo, bạn chỉ có thể cắt thành một hình chữ nhật mỏng. Chúng lần lượt tương ứng với các thế thắng và thế thua.

Hình các hình chữ nhật vàng từ Wikipedia.

Những cách tiếp cận khác

Có nhiều con đường dẫn tới lời giải bài toán này; phần phân tích của chúng tôi chỉ tập trung vào một trong số đó. Một cách khác là bắt đầu bằng một phương pháp chậm hơn và tính xem những \((A,B)\) nào là thế thắng đối với các giá trị (A,B) nhỏ. Quan sát kết quả, bạn có thể dễ dàng đoán rằng \((A,B)\) thắng khi và chỉ khi \(A \ge xB\) với một giá trị \(x\) nào đó; việc còn lại chỉ là tìm ra \(x\)!

Thông tin thêm

Thuật toán Euclid — Số Fibonacci — Tỉ lệ vàng.

Nguồn

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