Vị trí thắng, vị trí thua
Đề thi học sinh giỏi rất hay có bài hai người chơi: lần lượt bốc sỏi, đi quân cờ, viết số, ai không đi được nữa thì thua. Câu hỏi luôn là: nếu cả hai đều chơi giỏi nhất, người đi trước thắng hay người đi sau thắng? Bài này dạy cách trả lời bằng một ý rất đơn giản, rồi biến nó thành chương trình.
Trò chơi bốc sỏi
Phần tiêu đề “Trò chơi bốc sỏi”Có n viên sỏi. Hai bạn An (đi trước) và Bình lần lượt bốc 1, 2 hoặc 3 viên. Ai bốc viên cuối cùng thì thắng (nói cách khác: đến lượt mà không còn sỏi để bốc thì thua).
Gọi một số sỏi là vị trí thua nếu người phải đi ở vị trí đó chắc chắn thua (dù đi thế nào, đối thủ chơi giỏi vẫn thắng), và vị trí thắng nếu ngược lại. Có hai quy tắc:
- Vị trí là thắng nếu có ít nhất một nước đi tới vị trí thua (đẩy đối thủ vào thế thua).
- Vị trí là thua nếu mọi nước đi đều tới vị trí thắng (hoặc không có nước đi nào).
Bắt đầu từ 0 viên (không đi được: thua) rồi điền dần:
| n | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|---|
| Kết quả | thua | thắng | thắng | thắng | thua | thắng | thắng | thắng | thua |
- n = 1, 2, 3: bốc hết, đối thủ còn 0 viên (thua). Vậy là thắng.
- n = 4: bốc 1, 2, 3 thì còn 3, 2, 1, đều là vị trí thắng cho đối thủ. Vậy 4 là thua.
- n = 5, 6, 7: bốc sao cho còn 4. Vậy là thắng.
Quy luật: n chia hết cho 4 thì người đi trước thua. Chiến lược của người thắng: luôn bốc sao cho số sỏi còn lại chia hết cho 4. Đối thủ bốc x viên thì mình bốc 4 - x viên.
Tính bằng quy hoạch động
Phần tiêu đề “Tính bằng quy hoạch động”Khi chưa đoán được quy luật, cứ làm đúng như bảng trên bằng chương trình: thang[i] cho biết vị
trí i là thắng hay thua. Ví dụ mỗi lượt được bốc 1, 3 hoặc 4 viên:
def bang_thang_thua(n, nuoc_di): thang = [False] * (n + 1) # thang[0] = False: không đi được thì thua for i in range(1, n + 1): thang[i] = any(i >= k and not thang[i - k] for k in nuoc_di) return thang
thang = bang_thang_thua(14, [1, 3, 4])print([i for i in range(15) if not thang[i]]) # [0, 2, 7, 9, 14]#include <iostream>#include <vector>using namespace std;
int main() { int n = 14; vector<int> nuocDi = {1, 3, 4}; vector<bool> thang(n + 1, false); // thang[0] = false: không đi được thì thua for (int i = 1; i <= n; i++) for (int k : nuocDi) if (i >= k && !thang[i - k]) thang[i] = true; for (int i = 0; i <= n; i++) if (!thang[i]) cout << i << " "; // 0 2 7 9 14 cout << endl; return 0;}Mỗi vị trí xét hết các nước đi, nên với n vị trí và k kiểu nước đi, chương trình làm khoảng n × k phép tính.
Tìm chu kỳ khi n rất lớn
Phần tiêu đề “Tìm chu kỳ khi n rất lớn”Với n tới 1018 thì không lập bảng tới n được. Nhìn bảng ở trên: các vị trí thua của trò chơi bốc 1, 3, 4 là 0, 2, 7, 9, 14, 16, … lặp lại sau mỗi 7 vị trí. Vậy chỉ cần xét n % 7: thua khi n % 7 bằng 0 hoặc 2.
Vì sao chắc chắn lặp lại? Kết quả ở vị trí i chỉ phụ thuộc vào kết quả của k vị trí ngay trước (k là số bốc nhiều nhất). Nếu một đoạn k kết quả liên tiếp xuất hiện lại, mọi thứ sau đó sẽ lặp lại y hệt. Có hữu hạn đoạn k kết quả (nhiều nhất 2k), nên chắc chắn sẽ có đoạn lặp. Cách làm trong thi: lập bảng vài trăm vị trí đầu, in ra để nhìn quy luật, rồi chứng minh hoặc kiểm tra quy luật đó bằng chương trình.
Chiến lược đối xứng
Phần tiêu đề “Chiến lược đối xứng”Có hai đống sỏi, mỗi lượt được bốc bao nhiêu viên cũng được từ một đống. Nếu hai đống bằng nhau thì người đi sau thắng: đối thủ bốc bao nhiêu ở đống nào, mình bốc đúng chừng đó ở đống kia. Hai đống luôn bằng nhau sau lượt của mình, nên mình không bao giờ là người hết nước đi trước.
Nếu hai đống khác nhau thì người đi trước bốc để hai đống bằng nhau, rồi chơi đối xứng. Ý “bắt chước đối thủ” giải được nhiều bài trông rất khó (xem phần luyện tập).
Lưu ý về luật chơi
Phần tiêu đề “Lưu ý về luật chơi”- Đọc kỹ ai thắng: “ai lấy viên cuối thì thắng” khác hẳn “ai lấy viên cuối thì thua”. Với luật thứ hai, vị trí 0 viên lại là thắng (đối thủ vừa lấy viên cuối nên đối thủ thua), và cả bảng thay đổi.
- “Chơi tối ưu” nghĩa là cả hai đều biết hết và đi nước tốt nhất. Kết quả chỉ phụ thuộc vị trí ban đầu, không phụ thuộc may rủi.
Khi có nhiều đống sỏi, mỗi lượt chọn một đống để chơi, thì cần công cụ mạnh hơn: trò chơi Nim và số Grundy (bài tiếp theo của chuyên đề).
Luyện tập
Phần tiêu đề “Luyện tập”Gồm 20 bài, chia thành 4 nhóm từ dễ đến khó. Mỗi bài có một dữ liệu kiểm tra: các bạn chạy chương trình của mình với dữ liệu đó rồi so với đáp số.
Nhóm 1. Bốc sỏi, tìm quy luật
Phần tiêu đề “Nhóm 1. Bốc sỏi, tìm quy luật”Bài 1. Bốc từ 1 đến k viên
Phần tiêu đề “Bài 1. Bốc từ 1 đến k viên”Có n viên sỏi, hai người lần lượt bốc, mỗi lượt bốc từ 1 đến k viên. Ai bốc viên cuối cùng thì thắng. Nhập n, k (1 ≤ n, k ≤ 1018). Nếu cả hai chơi tối ưu, in ra TRƯỚC nếu người đi trước thắng, SAU nếu người đi sau thắng.
Ví dụ: nhập 10 3 thì in ra TRƯỚC.
Kiểm tra: nhập 1000000 6.
Bài 2. Nước đi đầu tiên
Phần tiêu đề “Bài 2. Nước đi đầu tiên”Vẫn trò chơi ở bài 1. Nhập n, k (1 ≤ n, k ≤ 1018). Nếu người đi trước thắng, in ra số viên người đó phải bốc ở lượt đầu để chắc chắn thắng (nếu có nhiều cách, in số nhỏ nhất). Nếu người đi trước thua, in ra 0.
Ví dụ: nhập 10 3 thì in ra 2.
Kiểm tra: nhập 999983 10.
Bài 3. Ai lấy viên cuối thì thua
Phần tiêu đề “Bài 3. Ai lấy viên cuối thì thua”Có n viên sỏi, mỗi lượt bốc từ 1 đến k viên, nhưng lần này ai bốc viên cuối cùng thì thua. Nhập n, k (1 ≤ n, k ≤ 1018). In ra TRƯỚC hoặc SAU.
Ví dụ: nhập 5 3 thì in ra SAU.
Kiểm tra: nhập 1000001 6.
Bài 4. Bốc từ a đến b viên
Phần tiêu đề “Bài 4. Bốc từ a đến b viên”Có n viên sỏi, mỗi lượt phải bốc ít nhất a viên và nhiều nhất b viên. Nếu số sỏi còn lại ít hơn a thì người đến lượt không đi được và thua. Nhập n, a, b (1 ≤ a ≤ b ≤ 109, 0 ≤ n ≤ 1018). In ra TRƯỚC hoặc SAU.
Ví dụ: nhập 6 2 3 thì in ra SAU.
Kiểm tra: nhập 1000000 3 7.
Bài 5. Bốc 1, 3 hoặc 4 viên
Phần tiêu đề “Bài 5. Bốc 1, 3 hoặc 4 viên”Có n viên sỏi, mỗi lượt bốc đúng 1, 3 hoặc 4 viên. Ai không bốc được thì thua. Nhập n (0 ≤ n ≤ 1018). In ra TRƯỚC hoặc SAU.
Ví dụ: nhập 7 thì in ra SAU.
Kiểm tra: nhập 1000000.
Nhóm 2. Quy hoạch động thắng thua
Phần tiêu đề “Nhóm 2. Quy hoạch động thắng thua”Bài 6. Tập nước đi tùy ý
Phần tiêu đề “Bài 6. Tập nước đi tùy ý”Dòng đầu là n, m (0 ≤ n ≤ 106, 1 ≤ m ≤ 10). Dòng thứ hai có m số nguyên dương khác nhau s1, …, sm (không quá 100): mỗi lượt được bốc đúng si viên với i nào đó. Ai không bốc được thì thua. In ra TRƯỚC hoặc SAU.
Ví dụ:
| Nhập | In ra |
|---|---|
14 31 3 4 | SAU |
Kiểm tra: nhập
1000000 42 5 7 11Bài 7. Tập nước đi, n rất lớn
Phần tiêu đề “Bài 7. Tập nước đi, n rất lớn”Như bài 6, nhưng 0 ≤ n ≤ 1018 và các si không quá 20. In ra TRƯỚC hoặc SAU.
Ví dụ:
| Nhập | In ra |
|---|---|
1000000000000000000 31 3 4 | TRƯỚC |
Kiểm tra: nhập
123456789012345678 42 5 7 11Bài 8. Bốc số chính phương
Phần tiêu đề “Bài 8. Bốc số chính phương”Có n viên sỏi, mỗi lượt bốc một số viên là số chính phương (1, 4, 9, 16, …). Ai không bốc được thì thua. Nhập n (0 ≤ n ≤ 105). In ra TRƯỚC hoặc SAU.
Ví dụ: nhập 2 thì in ra SAU.
Kiểm tra: nhập 100000.
Bài 9. Trừ đi một ước
Phần tiêu đề “Bài 9. Trừ đi một ước”Trên bảng có số n. Mỗi lượt, người chơi chọn một ước d của số đang có, với 1 ≤ d nhỏ hơn số đó, rồi thay số đó bằng (số đó - d). Ai không đi được (khi số trên bảng là 1) thì thua. Nhập n (1 ≤ n ≤ 1018). In ra TRƯỚC hoặc SAU.
Ví dụ: nhập 2 thì in ra TRƯỚC.
Kiểm tra: nhập 2026.
Bài 10. Đếm vị trí thua
Phần tiêu đề “Bài 10. Đếm vị trí thua”Dòng đầu là N, m (1 ≤ N ≤ 106, 1 ≤ m ≤ 10). Dòng thứ hai là tập nước đi s1, …, sm như bài 6. Có bao nhiêu số n từ 1 đến N mà người đi trước thua?
Ví dụ:
| Nhập | In ra |
|---|---|
14 31 3 4 | 4 |
Kiểm tra: nhập
1000000 32 3 7Nhóm 3. Các trò chơi khác
Phần tiêu đề “Nhóm 3. Các trò chơi khác”Bài 11. Nhân lên đến đích
Phần tiêu đề “Bài 11. Nhân lên đến đích”Bắt đầu với số p = 1. Hai người lần lượt nhân p với một số nguyên từ 2 đến 9. Người đầu tiên làm cho p ≥ n thì thắng. Nhập n (2 ≤ n ≤ 1018). In ra TRƯỚC hoặc SAU.
Ví dụ: nhập 10 thì in ra SAU.
Kiểm tra: nhập 1000000000000000000.
Bài 12. Quân vua về góc
Phần tiêu đề “Bài 12. Quân vua về góc”Quân vua đứng ở ô (x, y) trên bàn cờ rất lớn (ô góc là (0, 0)). Mỗi lượt, người chơi di chuyển vua sang trái 1 ô, xuống dưới 1 ô, hoặc chéo xuống trái 1 ô (không ra ngoài bàn). Ai không đi được (vua ở (0, 0)) thì thua. Nhập x, y (0 ≤ x, y ≤ 1018). In ra TRƯỚC hoặc SAU.
Ví dụ: nhập 2 2 thì in ra SAU.
Kiểm tra: nhập 1000 2026.
Bài 13. Đồng xu xếp vòng tròn
Phần tiêu đề “Bài 13. Đồng xu xếp vòng tròn”n đồng xu xếp thành vòng tròn. Mỗi lượt, người chơi lấy đi 1 đồng xu, hoặc 2 đồng xu nằm cạnh nhau (hai đồng xu cạnh nhau ban đầu, ở giữa không có chỗ trống). Ai lấy đồng xu cuối cùng thì thắng. Nhập n (1 ≤ n ≤ 1018). In ra TRƯỚC hoặc SAU.
Ví dụ: nhập 5 thì in ra SAU.
Kiểm tra: nhập 12.
Bài 14. Trừ đi một chữ số
Phần tiêu đề “Bài 14. Trừ đi một chữ số”Trên bảng có số n. Mỗi lượt, người chơi chọn một chữ số khác 0 của số đang có và trừ số đó đi chữ số ấy. Ai làm số trên bảng thành 0 thì thắng. Nhập n (1 ≤ n ≤ 1018). In ra TRƯỚC hoặc SAU.
Ví dụ: nhập 10 thì in ra SAU.
Kiểm tra: nhập 987654.
Bài 15. Bẻ thanh sô cô la
Phần tiêu đề “Bài 15. Bẻ thanh sô cô la”Thanh sô cô la có m × n ô. Mỗi lượt, người chơi chọn một miếng và bẻ nó dọc theo một đường kẻ thành hai miếng nhỏ hơn. Ai không bẻ được nữa (mọi miếng đều chỉ còn 1 ô) thì thua. Nhập m, n (1 ≤ m, n ≤ 109). In ra TRƯỚC hoặc SAU.
Ví dụ: nhập 2 3 thì in ra TRƯỚC.
Kiểm tra: nhập 999999999 1000000000.
Bài 16. Lấy xu ở hai đầu
Phần tiêu đề “Bài 16. Lấy xu ở hai đầu”n đồng xu xếp thành hàng, đồng thứ i có giá trị ai. Hai người lần lượt lấy một đồng ở đầu trái hoặc đầu phải của hàng. Mỗi người muốn tổng giá trị mình lấy được lớn nhất. Dòng đầu là n (1 ≤ n ≤ 1000), dòng sau là a1, …, an (không quá 109). In ra tổng giá trị người đi trước lấy được khi cả hai chơi tối ưu.
Ví dụ:
| Nhập | In ra |
|---|---|
43 9 1 2 | 11 |
Kiểm tra: nhập
85 3 7 10 8 1 6 2Nhóm 4. Vận dụng
Phần tiêu đề “Nhóm 4. Vận dụng”Bài 17. Hai đống sỏi
Phần tiêu đề “Bài 17. Hai đống sỏi”Có hai đống sỏi a viên và b viên. Mỗi lượt, người chơi chọn một đống và bốc bao nhiêu viên cũng được (ít nhất 1). Ai bốc viên cuối cùng thì thắng. Nhập a, b (0 ≤ a, b ≤ 1018). In ra TRƯỚC hoặc SAU.
Ví dụ: nhập 3 3 thì in ra SAU.
Kiểm tra: nhập 26 25.
Bài 18. Trò chơi trên đồ thị
Phần tiêu đề “Bài 18. Trò chơi trên đồ thị”Đồ thị có hướng không có chu trình, n đỉnh đánh số 1 đến n và m cạnh. Một quân cờ đứng ở đỉnh s. Mỗi lượt, người chơi di chuyển quân theo một cạnh có hướng xuất phát từ đỉnh đang đứng. Ai không đi được thì thua. Dòng đầu là n, m, s (1 ≤ n ≤ 105, 0 ≤ m ≤ 2 × 105). m dòng sau, mỗi dòng u v là cạnh từ u đến v. In ra TRƯỚC hoặc SAU.
Ví dụ:
| Nhập | In ra |
|---|---|
4 4 11 21 32 43 4 | SAU |
Kiểm tra: nhập
6 7 11 21 32 43 54 65 63 4Bài 19. Không bốc lặp lại
Phần tiêu đề “Bài 19. Không bốc lặp lại”Có n viên sỏi, mỗi lượt bốc từ 1 đến k viên, nhưng không được bốc đúng bằng số viên đối thủ vừa bốc ở lượt ngay trước (lượt đầu tiên thì tự do). Ai không đi được thì thua. Nhập n, k (1 ≤ n ≤ 2000, 1 ≤ k ≤ 20). In ra TRƯỚC hoặc SAU.
Ví dụ: nhập 4 3 thì in ra SAU.
Kiểm tra: nhập 2000 20.
Bài 20. Quân mã về góc
Phần tiêu đề “Bài 20. Quân mã về góc”Bàn cờ N × N, các ô đánh số (x, y) với 1 ≤ x, y ≤ N. Quân mã đứng ở ô (x, y). Mỗi lượt chỉ được đi một trong bốn nước: (x - 2, y + 1), (x - 2, y - 1), (x + 1, y - 2), (x - 1, y - 2), và phải ở trong bàn. Ai không đi được thì thua. Nhập N, x, y (1 ≤ x, y ≤ N ≤ 1000). In ra TRƯỚC hoặc SAU.
Ví dụ: nhập 15 5 4 thì in ra TRƯỚC.
Kiểm tra: nhập 1000 777 999.
© 2026 Bumbii Academy. Toàn bộ nội dung thuộc bản quyền của Bumbii Academy, nghiêm cấm sao chép dưới mọi hình thức khi chưa được cho phép.