Chủ đề này có 5 trả lời

[camap291]

Một chiếc hộp có 49 viên bi. Hai người thi bốc bi với nhau. Mỗi lần bốc từ 1 đến 4 viên. Người bốc cuối là người thua cuộc. Hãy chỉ và giải thích cách bốc để người bốc đầu tiên luôn luôn thắng.
( bài nì nằm trong đề thi tuyển tin ở trường em đó, khó wá , làm...lụi luôn.) Ai giải được mà dễ hiểu thì sẽ ... có thưởng

Bài viết đã được chỉnh sửa nội dung bởi camap291: 29-09-2007 - 10:10

[hieu_pbc]

Lần đầu bốc 3 viên bi
từ lần bốc thứ 2 trở đi bốc 5-x viên bi(x là số viên bi đối thủ bốc lần trước)
cuối cùng đến lượt đối thủ chỉ còn 1 viên->thắng

[camap291]

uhm, trường mình cũng giải ra như vậy đó. Nhưng mờ mình hiểu sơ sơ hà, sao lại lấy 5 trừ đi nhỉ ? bik là cuối cùng phải còn 1 bi đó, Còn cách nào khác không ?

[tommyrader]

Đúng là bài này khá hay. Tuy nhiên, mình cũng giống bạn, còn mơ hồ ở chỗ 5-x .

[Duck_Pro]

Để thắng được thì ta phải có cách điều chỉnh số bi sao cho người kia không thể nào bốc được viên bi cuối cùng. Để được như vậy thì ta phải bốc được viên bi cuối cùng --> trước đó (ở lượt người kia trên bàn phải ít nhất là 5 viên bi) --> cứ thế suy luận ngược lại là ra mà.

[Ham_Toan]

Một chiếc hộp có 49 viên bi. Hai người thi bốc bi với nhau. Mỗi lần bốc từ 1 đến 4 viên. Người bốc cuối là người thua cuộc. Hãy chỉ và giải thích cách bốc để người bốc đầu tiên luôn luôn thắng.

Bài toán tổng quát:
Cho n viên bi, mỗi lầ bốc tứ 1-> m viên bi. Tìm chiến thuật để người đầu tiên luôn thắng

Giải: Mấu chốt, luôn chừa lại viên cuối cùng cho người kia bốc ! => Người nào để lại số bi chia m+1 dư 1 thì người đó luôn thắng (nếu biết chơi).
+ m >= (n - 1): Người đi trước lấy (n-1) viên.
+ m < (n-1):
* n chia (m+1) dư 1: Nếu người sau biết chơi, thì người sau luôn thắng.
* Trường hợp còn lại:
Để Sau khi người đầu tiên bốc còn lại cuối cùng 1 viên bi ở lượt thứ k, thì tại lượt (k-1), sau khi người đầu tiên bốc phải để lại (m + 1) + 1 viên bi !
........
Người đầu tiên bốc phải luôn đẩ lại Số viên bi có số lượng a sao cho a chia (m+1) dư 1.

Vậy đầu tiên người đi trước bốc (n-1) mod (m+1) viên bi (Số dư khi chia n-1 cho m+1).
Sau đó hễ người sau bốc x viên bi thì người đầu sẽ bốc (m+1-x) viên bi (để số bi còn lại luôn chia cho (m+1) dư 1