Bài toán đấu trí: Bốc sỏi- Bốc diêm

Bài toán đấu trí : Bốc sỏi, Bốc diêm


Trò BỐC SỎI

Bài 1: ( Dạng Cổ điển )
Một đống sỏi có 30 viên đặt trên bàn. Hai bạn Anh (A) và Bằng (B) chơi trò “bốc sỏi ” với luật quy định là: Mỗi bạn đến lượt đi phải bốc ra từ đống sỏi trên: tối thiểu 1 viên và tối đa không quá một nửa ( ½) số sỏi đang còn trên bàn. Người bốc phải viên sỏi cuối cùng là người thua. Hỏi người muốn thắng cuộc phải thực hiện các bước đi như thế nào ?

Giải: Xét hai tình huống theo sơ đồ:
Tình huống thứ nhất (A & B đều bốc tối đa )



Tình huống thứ hai: sau lần thứ I, B không bốc tối đa mà chỉ bốc 5
ở lần II để dồn cho lần “áp chót” còn 3 viên buộc A thế bất lợi




Như vậy đây là cuộc chơi có “đấu trí” giữa A và B mà 2 lượt cuối cùng (Áp chót & chót) có tính chất quyết định thắng-thua. Ai dồn “đối phương” chịu nhận bốc số sỏi còn lại ở lần “áp chót” là 3 thì sẽ thắng

Bài 1 phát triển: ( trich trong 100 bài thi “Tin học với nhà trường”)

Một đống sỏi có 101 viên. Hai bạn An (A) và Bình (B) chơi trò “bốc sỏi ” như sau: Mỗi bạn đế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 bốc phải viên sỏi cuối cùng là người thua . Giả sử bạn An (A) là người được bốc trước, B bốc sau. Hỏi người muốn thắng cuộc phải thực hiện các bước đi như thế nào ?

Giải & Bàn luận

* Cách suy luận để người thứ hai (B) thắng:

Số sỏi ban đầu có 101= (100 + 1) viên, quy về số có dạng 5k+1, nghĩa là số đó nếu chia 5 sẽ còn dư 1. Nếu A bốc trước, mà số sỏi của A phải lấy là từ 1 đến 4 viên do đó sau lượt đi đầu tiên, số sỏi còn lại sẽ lớn hơn 96. B sẽ bốc tiếp theo, sao cho số sỏi còn lại phải là 96, nghĩa là số dạng 5k+1. Tương tự như vậy, Nếu B luôn luôn chủ động để sau lần bốc của mình số sỏi còn lại là 5k+1. Lần cuối cùng số sỏi còn lại chỉ là 1 => A bắt buộc phải bốc viên cuối cùng và chịu thua.

*Phân tích “Chiến thuật” đơn giản để giành chiến thắng như sau:
Người muốn thắng phải dồn “đối phương” chịu nhận lần “áp chót” số sỏi còn lại 6 viên. Vì “đối phương” chỉ lấy được tối đa 4 viên => còn 2 viên thì bên nào bốc đi 1 viên, buộc bên thua phải nhận viên cuối cùng.
Vậy “Chiến thuật” giành chiến thắng là sau lần thứ nhất bên nào để lại số sỏi chia hết cho 6 thì mỗi lượt tiếp sau chỉ cần lấy số sỏi sao cho cộng với số “đối phương” đã lấy bằng 6 viên.
Trường hơp thứ nhất: Đầu tiên A lấy 4 thì B lấy 1, A lấy 3 thì B lấy 2 ... còn 96 viên. Các lần tiếp theo: A lấy 4 thì B lấy 2, A lấy 3 thì B lấy 3 ... => B thắng
Trường hợp thứ hai : Nếu B không biết chiến thuật trên nên chỉ lấy số sỏi cộng lại là 5; 4; 3;...A lấy lần tiêp đấy 2 bù lại cho số cộng bằng 6 => A thắng.
“Chiến thuật” này áp dụng khi điều kiện bốc của 2 người vẫn như trên, nhưng số sỏi ban đầu có thể không phải là 101.
Thí dụ: Số sỏi ban đầu là 50, Ai phải bốc viên sỏi cuối cùng ?
A muốn thắng thì lần đầu bốc 2 còn 48 (chia hết cho 6), liền đó B không thể bốc > 4 viên mà chỉ được bốc 4, 3 hoặc 2 viên; A cần bốc bù 2,3, 4 viên. Cứ như thế A sẽ thắng.
Tuy nhiên, nếu B cũng biết chiến thuật chỉ bốc 1 viên nên A chỉ có thể bốc 1,2 3 hoặc 4=> số còn lại lần lượt là 46, 45, 44, 43. đến đây thì thế chủ động thuộc về B. Tiếp theo B chỉ cần bốc 4, 3, 2, 1 cho số còn lai là 42 => B sẽ thắng.
Như thế, Trò chơi này là cuộc đấu trí rất hay. Ai giành đươc thế chủ động dồn “đối phương” chịu nhận bốc số sỏi còn lại chia hết cho 6 => người đó sẽ thắng. Do đó “Chiến thuật” dồn nhau đến số 6 rất quan trọng (Cần bí mật đấy!)