Bài toán
Trò chơi bốc sỏi (Dành cho học sinh Tiểu học)
Trên mặt đất có một đống sỏi có 101 viên. Hai em học sinh Hoàng và Huy chơi trò chơi như sau: Mỗi em đến lượt đi phải bốc ra từ đống sỏi trên tối thiểu là 1 viên và tối đa là 4 viên. Người thua là người phải bốc viên sỏi cuối cùng. Giả sử Hoàng là người được bốc trước, Huy bốc sau. Các em thử nghĩ xem ai là người thắng cuộc, Hoàng hay Huy? Và người thắng cuộc phải suy nghĩ gì và thực hiện các bước đi của mình ra sao?
Cách giải bài toán
Để giải quyết bài toán này, ta cần xem xét trường hợp số lượng viên sỏi ban đầu là chẵn hay lẻ.
Nếu số lượng viên sỏi ban đầu là số chẵn, thì người chơi đầu tiên (Hoàng) sẽ luôn có chiến lược thắng bằng cách lấy đi số lượng viên sỏi còn lại khiến cho số viên sỏi còn lại sau lượt của người chơi thứ hai (Huy) là số lẻ. Bởi vì bất kỳ lượt bốc viên sỏi nào của Huy cũng sẽ giảm số viên sỏi còn lại xuống một số lẻ, điều này đưa Hoàng vào vị trí cuối cùng là người bốc viên sỏi cuối cùng và thua cuộc.
Nếu số lượng viên sỏi ban đầu là số lẻ, thì Hoàng sẽ bốc một số viên sỏi (từ 1 đến 4) và giữ cho số viên sỏi còn lại là số chẵn. Huy sẽ bốc số viên sỏi còn lại, khiến số viên sỏi còn lại sau lượt của Huy là số lẻ. Vì Huy phải bốc viên sỏi cuối cùng, và số viên sỏi đó là số lẻ, nên Hoàng sẽ thắng cuộc.
Vì vậy, nếu số lượng viên sỏi ban đầu là số chẵn, thì người chơi đầu tiên (Hoàng) sẽ thua cuộc nếu đối thủ của họ chơi đúng chiến lược. Nếu số lượng viên sỏi ban đầu là số lẻ, thì người chơi đầu tiên (Hoàng) sẽ thắng cuộc nếu họ chơi đúng chiến lược.
Cài đặt bài toán với Python
stones = 101
turn = 1 # Hoàng bốc trước
while stones > 0:
if turn == 1:
# Hoàng bốc
stones_taken = int(input("Hoàng bốc bao nhiêu viên sỏi? "))
while stones_taken < 1 or stones_taken > 4 or stones_taken > stones:
print("Vui lòng bốc từ 1 đến 4 viên sỏi và không nhiều hơn số viên sỏi còn lại.")
stones_taken = int(input("Hoàng bốc bao nhiêu viên sỏi? "))
else:
# Huy bốc
stones_taken = int(input("Huy bốc bao nhiêu viên sỏi? "))
while stones_taken < 1 or stones_taken > 4 or stones_taken > stones:
print("Vui lòng bốc từ 1 đến 4 viên sỏi và không nhiều hơn số viên sỏi còn lại.")
stones_taken = int(input("Huy bốc bao nhiêu viên sỏi? "))
stones -= stones_taken
# Đổi lượt
turn = 3 - turn
# Kiểm tra người thắng cuộc
if turn == 1:
print("Huy thắng cuộc!")
else:
print("Hoàng thắng cuộc!")
Cài đặt bài toán với C++
#include <iostream>
using namespace std;
int main() {
int stones = 101;
int turn = 1; // Hoàng bốc trước
int stones_taken;
while (stones > 0) {
if (turn == 1) {
// Hoàng bốc
cout << "Hoàng bốc bao nhiêu viên sỏi? ";
cin >> stones_taken;
while (stones_taken < 1 || stones_taken > 4 || stones_taken > stones) {
cout << "Vui lòng bốc từ 1 đến 4 viên sỏi và không nhiều hơn số viên sỏi còn lại." << endl;
cout << "Hoàng bốc bao nhiêu viên sỏi? ";
cin >> stones_taken;
}
} else {
// Huy bốc
cout << "Huy bốc bao nhiêu viên sỏi? ";
cin >> stones_taken;
while (stones_taken < 1 || stones_taken > 4 || stones_taken > stones) {
cout << "Vui lòng bốc từ 1 đến 4 viên sỏi và không nhiều hơn số viên sỏi còn lại." << endl;
cout << "Huy bốc bao nhiêu viên sỏi? ";
cin >> stones_taken;
}
}
stones -= stones_taken;
// Đổi lượt
turn = 3 - turn;
}
// Kiểm tra người thắng cuộc
if (turn == 1) {
cout << "Huy thắng cuộc!" << endl;
} else {
cout << "Hoàng thắng cuộc!" << endl;
}
return 0;
}