Phân tích

Test set 1

Độ khó của bài toán bắt nguồn từ việc các cối xay có thể quay hết một vòng. Nếu một cối xay có 5 cánh và vào buổi sáng ta thấy cánh số 2 hướng xuống, điều đó có nghĩa là 2 con chuột đã xoay nó, hay là 7 con, hay 12 con? Tổng quát, nếu một cối xay có \(B\) cánh và ta thấy nó ở vị trí \(P\), điều duy nhất có thể khẳng định chắc chắn là đã có một số lượng chuột bằng \(P + K \times B\) (với một số nguyên \(K\)) tác động vào nó trong đêm.

Vì vậy, ta có thể suy luận rằng nên lắp số cánh lớn nhất có thể (tức 18) cho mỗi cối xay, rồi hy vọng không cối nào trong số đó bị nhiều hơn 17 con chuột ghé thăm; khi ấy, tổng số lần xoay của tất cả các cối xay bằng tổng số chuột. Hóa ra đây là một hy vọng hợp lý! Rất khó tính trực tiếp xác suất không cối nào trong 18 cối bị xoay quá 17 lần trong một đêm, nhưng một mô phỏng nhanh cho biết rằng ngay cả ở trường hợp xấu nhất với 100 con chuột, xác suất điều này xảy ra là khoảng \(0{,}00017\). Vì có thể lặp lại cùng thí nghiệm 365 lần và lấy kết quả lớn nhất tìm được, xác suất trả lời sai (do nhận phải kết quả gây hiểu lầm trong cả 365 lần) nhỏ đến mức không đáng kể.

Test set 2

Trong Test set 2, ta chỉ có 7 đêm để làm việc và số chuột có thể khá lớn, nên không thể trông chờ một cách hợp lý rằng các cối xay sẽ không quay hết vòng. Vậy phải làm gì? Ta có thể cân nhắc dùng số cánh khác nhau cho từng cối xay trong cùng một đêm, nhưng khó thấy cách đó đem lại lợi ích gì.

Giả sử trong một đêm, ta thử lắp hai cánh cho mọi cối xay. Ban đầu, cách này có vẻ không hữu ích — chẳng phải dữ liệu thu được gần như chỉ là nhiễu sao? Tuy nhiên, ta có thể nhận thấy rằng nếu số chuột là lẻ thì tổng số lượt xoay (trên tất cả các cối xay) sẽ là lẻ, còn nếu số chuột là chẵn thì tổng đó sẽ là chẵn. Do đó, ta có một cách xác định tính chẵn lẻ của số chuột, bất kể chúng đã xoay các cánh như thế nào!

Ta có thể mở rộng ý tưởng này để tìm số lượng chuột theo modulo của bất kỳ số nào do ta chọn trong khoảng từ 2 đến 18. Tuy nhiên, vì chỉ có 7 đêm, ta nên lựa chọn các số một cách cẩn thận. Một ý tưởng đầy hứa hẹn là chọn toàn số nguyên tố; có đúng bảy số nguyên tố trong phạm vi có thể dùng: 2, 3, 5, 7, 11, 13 và 17. Khi đó, ta có thể thử áp dụng cấu trúc do định lý phần dư Trung Hoa gợi ý để xác định duy nhất số lượng chuột. Tuy nhiên, phương pháp này chỉ hoạt động với mọi số lượng chuột không vượt quá \(2 \times 3 \times \ldots \times 17 = 510510\); nó không thể phân biệt 510511 con chuột với 1 con chuột! Ta gặp rắc rối vì có thể có đến \(10^6\) con chuột.

Nhận xét cuối cùng cần có là định lý phần dư Trung Hoa chỉ yêu cầu các modulo đôi một nguyên tố cùng nhau, chứ không nhất thiết từng modulo phải là số nguyên tố. Vì vậy, ta có thể dùng 16 thay cho 2 và 9 thay cho 3. Điều này cho phép xác định mọi số lượng chuột không vượt quá \(5 \times 7 \times 9 \times 11 \times 13 \times 16 \times 17 = 12252240\), dư sức bao phủ phạm vi cần thiết. (Chẳng hạn, ta cũng có thể dùng các số từ 12 đến 18; chi tiết xin dành cho bạn đọc.)

Lưu ý rằng ta thực sự không cần thực hiện phép tính nào dựa trên định lý phần dư Trung Hoa; vì số đáp án có thể có tương đối nhỏ, ta có thể kiểm tra lần lượt tất cả cho đến khi tìm được số có phần dư thích hợp đối với từng modulo đã chọn.

Phụ lục cho Test set 1

Để chứng minh rằng xác suất có ít nhất một cối xay bị xoay quá 17 lần là khoảng \(0{,}00017\), ta có thể giải một bài toán liên quan:

Đếm số mảng số nguyên độ dài L sao cho mỗi phần tử của mảng là một trong các số \(1, 2, \ldots, \mathbf{U}\) và mỗi số xuất hiện nhiều nhất B lần trong mảng.

Bài toán liên quan này tương đương với việc đếm các phân hoạch số nguyên có ràng buộc về kích thước của từng phần trong phân hoạch.

Ta có thể giải bài toán liên quan này bằng quy hoạch động. Trước hết, ta chọn số lần U xuất hiện trong mảng; giả sử nó xuất hiện \(K\) lần, với \(0 \leq K \leq \min(\mathbf{B}, \mathbf{L})\). Khi đã biết \(K\), ta phải chọn vị trí đặt \(K\) giá trị đó. Dùng tổ hợp, ta thấy có C(L, K) cách chọn. Với mỗi cách, ta có thể coi L\(-K\) vị trí còn lại là một mảng phải chứa các số \(1, 2, \ldots, \mathbf{U}-1\) sao cho không số nào xuất hiện quá B lần; đây là một bài toán con của bài toán ban đầu nên ta có thể đệ quy. Cộng kết quả trên mọi giá trị \(K\) có thể, ta thu được tổng số mảng hợp lệ.

Nếu giải bài toán trên với \(\mathbf{L}=100\), \(\mathbf{U}=18\), \(\mathbf{B}=17\), ta thấy có

336647783248234011860927063629187654598455062446560501834487820535956663161762533555609870639313859125191714928476256971520000

(hay xấp xỉ \(3{,}366 \times 10^{125}\)) mảng mà không số nào xuất hiện quá 17 lần. Các mảng này có thể biểu diễn cối xay mà mỗi con chuột lựa chọn trong một cấu hình tốt, trên tổng số \(18^{100}\) cấu hình có thể. Từ đó ta thu được xác suất đã nêu ở trên.

Dựa trên phân tích chính thức của Google Code Jam.