Đáp án bài toán nhặt đậu thách thức suy luận

Đề bài:

Alice và Bob chơi trò chơi lấy hạt đậu với 2009 hạt đậu trên bàn. Ở mỗi lượt, Alice và Bob có thể lấy đi một, hai, hoặc ba hạt đâu.

Theo thứ tự, Alice sẽ lấy đậu đầu tiên rồi đến Bob và lại quay lại Alice, cứ tiếp tục luân phiên như vậy đến khi số hạt đậu trên bàn hết. Người cầm những hạt đậu cuối cùng sẽ chiến thắng.

Bạn nghĩ ai có thể chiến thắng trò chơi này và chiến thắng bằng cách nào?

Ảnh minh họa

Đáp án: Alice có thể chiến thắng.

Để có thể chiến thắng, Alice cần áp dụng chiến thuật sau:

Vì là người được lấy đầu tiên nên Alice sẽ lấy một hạt đậu. Khi đó, số hạt đậu còn lại trên bàn là 2008 hạt.

Sau lượt lấy đầu tiên của Alice sẽ đến lượt Bob. Bob có thể lấy một, hai, hoặc ba hạt. Gọi số hạt Bob lấy là a với a = 1; 2 hoặc 3.

Bây giờ, bất kể Bob lấy bao nhiêu hạt thì Alice chỉ cần lấy (4 - a) hạt đậu ở lượt tiếp theo của mình và cứ làm như vậy trong những lần tiếp theo.

Như vậy, trừ đi lần đầu Alice lấy, cứ ở chu kỳ mỗi Bob lấy rồi đến Alice lấy tiếp theo, 2008 hạt đậu sẽ giảm 4 hạt.

Khi chỉ còn 4 hạt đậu trên bàn cũng là lúc đến lượt của Bob và Bob chỉ được lấy tối đa 3 hạt nên trên bàn chắc chắn sẽ còn ít nhất 1 hạt đậu hoặc nhiều nhất 3 hạt đậu. Số hạt đậu này vừa đúng bằng số hạt Alice có thể lấy mà không phạm luật nên Alice sẽ có những hạt đậu cuối cùng trên tay.

Nếu áp dụng chiến thuật này, Alice chắc chắn sẽ giành chiến thắng.

Thanh Tâm

XEM THÊM http://ift.tt/2eFKc3W