Trò chơi Toán học: NIM

[HLN1994]

Lịch sử trò chơi

NIM là một trò chơi khá đơn giản. Cơ sở lý thuyết của trò chơi này được xây dựng bởi Giáo sư Toán học Charles Bouton tại Đại học Harvard năm 1901. Người ta cho rằng NIM bắt đầu từ Trung Quốc, một số khác lại cho rằng NIM là từ mượn của tiếng Đức của động từ “nimm” ( có nghĩa là “lấy” ). Các loại game tương tự NIM đã tồn tại hàng nhiều thập kỷ trên Trái Đất và người Châu Âu đề cập đến trò chơi này vào thế kỷ XV.

Cách chơi

NIM là một trò chơi gồm có hai người chơi, trò chơi sẽ gồm nhiều đống sỏi ( hoặc bất cứ vật gì cũng được, thông thường có 3,4 hoặc 5 đống sỏi ). Mỗi đống sỏi sẽ có một số lượng tùy ý và cả hai người chơi đều biết rõ số lượng sỏi trong mỗi đống. Từng người chơi sẽ lần lượt chọn một đống sỏi và bốc ra trong đống đó một só lượng sỏi tùy ý nhưng phải bốc ít nhất 01 viên. Người bốc được viên sỏi cuối cùng sẽ là người chiến thắng. Nếu chỉ còn 01 đống còn sỏi và đống đó còn hơn 01 viên sỏi thì không được bốc hết.

Ví dụ: trò chơi bắt đầu bằng 03 đống sỏi, có số lượng lần lượt là: 3, 7 và 11.




Chiến thuật để chiến thắng

Có chiến thuật nào để chiến thắng không nhỉ ?
Để trả lời câu hỏi này, trước hết đặt ra một khái niệm về tổng NIM:
+Chuyển đổi số sỏi ra từng đống nhị phân.
+Thêm vào bên trái những số nhị phân các số 0 để cho các chữ số có cùng số chữ số.
+Đếm số chữ số 1 tại mỗi cột. Nếu có chẵn chữ số 1 thì cột đó tổng NIM là 1 và ngược lại.
Ví dụ:
Giả sử có 03 đống sỏi lần lượt là 3, 7 và 11.
+Đổi qua hệ nhị phân ta được 11, 111 và 1011.
+Thêm vào các ký tự 0 ta có: 0011, 0111, 1011.
+Tổng NIM tính được như sau:
0011 + 0111 + 1011 = 1100

Chiến thuật chiến thắng là phải bốc sao cho sau khi bốc xong tổng NIM sẽ chỉ là các ký tự 0.

Các bạn sẽ thấy A đã sử dụng chiến thuật này để thắng B





Chiến thuật này sẽ đảm bảo chiến thắng cho người chơi? Tuy vậy, trong khi chơi thì rõ ràng chiến thuật này thật khó thực hiện đúng vì chúng ta không có đủ thời gian để tính NIM. Do đó, trong khi chơi thực sự, ai là người nhanh trí hơn sẽ là người chiến thắng.

P/s: Nếu các bạn đã hiểu và thành thạo trò chơi toán học NIM xin mời bạn thử sức với bài tập sau:

Bốc sỏi

Hai bạn Nam và Mai cùng chơi một trò chơi với n đống sỏi. Luật chơi như sau:

*Hai bạn sẽ lần lượt đi. Bạn Mai là người đi trước
*Trong mỗi lượt đi, bạn đi sẽ được quyền bốc một số sỏi bất kỳ từ một đống nhất định và phải bốc tối thiểu là 1 viên sỏi.
*Bạn nào bốc phải viên sỏi cuối cùng là người thua cuộc

Bạn hãy giúp Mai xác định xem bạn ấy có thể thắng được trong trò chơi hay không

Dữ liệu vào

Dòng đầu tiên chứa một nguyên t là số bộ test. Các dòng sau là t bộ test.

Mỗi bộ test bao gồm:

*Dòng đầu tiên chứa một số nguyên n (n<=100) là số đống sỏi
*Dòng thứ hai gồm n số nguyên a1, a2, a3,... , an, ngăn cách nhau bởi một khoảng trắng. Số nguyên ai cho biết số lượng viên sỏi có trong đống thứ i (1<=ai<=100)

Kết quả

Với mỗi bộ test, in ra 1 nếu bạn Mai thắng, -1 nếu bạn Mai thua

Ví dụ

Dữ liệu mẫu
2
4
30 4 19 75
3
1 4 5


Kết qủa
1
-1

(Nguồn bài tập: http://vnoi.info/index.php?option=co...oblem=NK05MNIM)

Chúc các bạn thành công
Nguồn từ: http://chuyenhvt.net

Các bài viết cùng chuyên mục:

• Mọi người gợi ý hướng làm bài này với! đề...
• Tài liệu học tập cho lớp chuyên Tin
• Tin buồn
• Đề thi HSGQG Môn Tin học ngày thứ hai 2011
• Đề thi HSGQG Môn Tin học ngày thứ nhất 2011
• Trò chơi Toán học: NIM
• Ứng dụng phương pháp quy nạp toán học
• Phỏng vấn Conankudo-Siêu khủng+Buồn cười
• Dành cho khối 10 chuyên Tin nhập môn!!!
• Ai code AC được bài này không???