Hãy nhập câu hỏi của bạn vào đây, nếu là tài khoản VIP, bạn sẽ được ưu tiên trả lời.
Ta phân tích các trường hợp nhỏ sau:
Nếu trên bàn có từ 1 đến 5 cái kẹo thì hiển nhiên Lan sẽ lấy hết số kẹo đó và thắng.
Nếu trên bàn có 6 cái kẹo thì sao? Cho dù Lan đi như thế nào cũng sẽ thua vì Lan chỉ được bốc 1 đến 5 viên nên Lan sẽ luôn chừa lại ít nhất 1 viên và nhiều nhất 5 viên cho Khoa và do đó Lan thua.
Nếu trên bàn có từ 7 đến 11 viên? Khi đó Lan sẽ bốc kẹo sao cho trên bàn chỉ còn lại 6 viên - chính là trường hợp ban nãy nhưng người bốc lúc này là Khoa - người mà chắc chắn sẽ thua do phân tích ở trên => Lan thắng.
Nếu trên bàn có 12 viên? Khi đó dù Lan bốc thế nào thì Khoa cũng sẽ bốc kẹo để đưa số kẹo trên bàn lại về 6 viên => Lan thua.
Như vậy, ta dễ dàng rút ra được quy luật: Nếu tại thời điểm Lan bốc kẹo, số kẹo trên bàn là bội số của 6 thì Lan thua và ngược lại.
a) Với trường hợp \(n=10\), khi đó Lan chỉ cần bốc 4 viên để số kẹo trên bàn còn lại 6 viên => Lan thắng theo phân tích trên.
b) Với trường hợp n quá lớn như trên thì ta cần nhớ dãy số chia hết cho 6 sau: \(6\rightarrow12\rightarrow18\rightarrow24\rightarrow...\). Do vậy, khi \(n=74\), Lan cần phải bốc 2 viên kẹo để chuyển số kẹo về 72 là một bội của 6. Khi đó dù Khoa bốc thế nào thì Lan vẫn có thể đưa số kẹo về một bội khác của 6 (chẳng hạn ở lượt tiếp theo Khoa bốc 5 viên, đưa số kẹo về 67 thì Lan chỉ cần bốc 1 viên để đưa số kẹo về 66 là một bội của 6). Cứ tiếp tục như vậy, thì Lan là người sẽ đưa số kẹo về 6 và là người giành chiến thắng.
Khi kết thúc trò chơi thì cả hai hộp đều không còn bi. Để thắng cuộc thì lượt cuối cùng Hồng phải bốc hết số bi trong một hộp, vfa phải đảm bảo rằng khi đó hộp của Hà cũng đã hết bi.
Từ đó cách chơi để Hồng thắng là phải làm cho số bi ở hai hộp bằng nhau và mỗi khi Hà bốc bao nhiêu viên ở một hộp thì Hồng sẽ bốc bấy nhiêu viên ở hộp còn lại. Để làm được như vậy và tránh bị Hà chiếm lấy cơ hội, lượt đầu tiên buộc Hồng phải bốc 23 viên bi ở hộp chứa 123 viên bi để đảm bảo hai hộp lúc này có số bi bằng nhau (cùng là 100 viên).
Nếu Hồng không bố theo cách trên, thì Hà hoàn toàn có cơ hội làm cho số bi ở hai hộp bằng nhau trước Hồng, và khi đó Hà trở thành người thắng cuộc.
Vậy cách bốc bi để Hồng chắc chắn thắng là duy nhất.
Tổng quát : Nếu hai hộp ban đầu có số bi khác nhau thì người bốc trước sẽ luôn thắng nếu lượt đầu tiên bốc ở hộp nhiều hơn số bi chênh lệch giữa hai hộp. Nếu hai hộp ban đầu có số bi bằng nhau thì người bốc sau luôn luôn thắng nếu bốc số bi bằng với số bi của người bốc trước mình.
Đầu tiên Hồng bốc 23 viên bi ở hộp 123 viên để cho hai hộp có số bi bằng nhau. Sau đó bạn còn lại bốc bao nhiêu viên bi ở hộp bên nào thì Hồng chỉ cần bốc bấy nhiêu viên bi ở hộp còn lại
Chơi như sau :
Lượt 1 lấy 1 viên bi. Những lượt sau lấy số bi bằng 5-*số bi người thứ 2 lấy lượt trước*
Hướng dẫn giải:
Ta giải bài toán bằng cách đi ngược từ dưới lên. Vì tổng số kẹo là 25 nên nếu cuối cùng một người bốc được số lẻ viên kẹo sẽ thua, do người kia sẽ bốc được một số chẵn viên kẹo.
Ta ký hiệu mỗi trạng thái đến lượt An hay Bình đi bằng hai tham số (CL, k), trong đó CL là tính chẵn lẻ của số kẹo mà người chơi đang có, k là số kẹo còn lại trên bàn. Ta viết f(CL, k) = 1 nếu người đi có chiến thuật thắng từ trạng thái này. Trong trường hợp ngược lại f(CL, k) = 0. Mục đích của chúng ta là cần tính F(C, 25). Nếu giá trị này bằng 1 thì An thắng, ngược lại nếu giá trị này bằng 0 thì Bình thắng.
Ví dụ f(C, 1) = 0 vì người đi đang có số chẵn viên kẹo và bắt buộc phải bốc viên kẹo cuối cùng, kết thúc cuộc chơi. f(C, 2) = 1 vì người đi đang có số chẵn viên kẹo và có thể bốc 2 viên kẹo cuối cùng để giành chiến thắng. Cũng như vậy f(C, 3) = 1 (bốc 2). Tương tự như thế thì f(L, 1) = 1 (bốc 1), F(L, 2) = 1 (bốc 1), F(L, 3) = 1 (bốc 3).
Để tính f(C, 4) ta để ý rằng lúc này đối thủ đang có số lẻ viên kẹo. Nếu ta bốc 1, 2 hoặc 3 viên thì sẽ đưa đối thủ đến các trạng thái (L, 3), (L, 2), (L, 1) tương ứng, và đều là các trạng thái thắng của đối thủ. Suy ra f(C, 4) = 0. Với f(L, 4) ta bốc 3 viên, đưa đối thủ vào trạng thái thua (C, 1) và giành chiến thắng.
Tiếp tục, để tính f(C, 5) ta để ý rằng lúc này đối thủ đang có số chẵn viên kẹo. Do đó ta bốc 1 viên và đưa đối thủ vào trạng thái (C, 4) là trạng thái thua, như vậy f(C,5) = 1. Ngược lại từ (L, 5) ta chỉ có thể đưa về (L, 4), (L, 3), (L, 2) là các trạng thái thắng, suy ra f(L, 5) = 0.
Nói tóm lại, một trạng thái là thua nếu mọi cách đi đều đưa về trạng tháng thắng (cho đối thủ), một trạng thái là thắng nếu có một cách đi đưa về trạng thái thua (cho đối thủ). Bằng lý luận này, ta lập được bảng giá trị sau.
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |
| C | 0 | 1 | 1 | 0 | 1 | 1 | 1 | 1 | 0 |
| L | 1 | 1 | 1 | 1 | 0 | 1 | 1 | 0 | 1 |
| 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | |
| C | 1 | 1 | 0 | 1 | 1 | 1 | 1 | 0 | 1 |
| L | 1 | 1 | 1 | 0 | 1 | 1 | 0 | 1 | 1 |
| 19 | 20 | 21 | 22 | 23 | 24 | 25 | |||
| C | 1 | 0 | 1 | 1 | 1 | 1 | 0 | ||
| L | 1 | 1 | 0 | 1 | 1 | 0 | 1 |
Như vậy f(C, 25) = 0, tức là Bình có chiến thuật thắng.
(Đây là bài toán khá khó trong lý thuyết thuật toán và trò chơi).
Ta giải bài toán bằng cách đi ngược từ dưới lên. Vì tổng số kẹo là 25 nên nếu cuối cùng một người bốc được số lẻ viên kẹo sẽ thua, do người kia sẽ bốc được một số chẵn viên kẹo.
Ta ký hiệu mỗi trạng thái đến lượt An hay Bình đi bằng hai tham số (CL, k), trong đó CL là tính chẵn lẻ của số kẹo mà người chơi đang có, k là số kẹo còn lại trên bàn. Ta viết f(CL, k) = 1 nếu người đi có chiến thuật thắng từ trạng thái này. Trong trường hợp ngược lại f(CL, k) = 0. Mục đích của chúng ta là cần tính F(C, 25). Nếu giá trị này bằng 1 thì An thắng, ngược lại nếu giá trị này bằng 0 thì Bình thắng.
Ví dụ f(C, 1) = 0 vì người đi đang có số chẵn viên kẹo và bắt buộc phải bốc viên kẹo cuối cùng, kết thúc cuộc chơi. f(C, 2) = 1 vì người đi đang có số chẵn viên kẹo và có thể bốc 2 viên kẹo cuối cùng để giành chiến thắng. Cũng như vậy f(C, 3) = 1 (bốc 2). Tương tự như thế thì f(L, 1) = 1 (bốc 1), F(L, 2) = 1 (bốc 1), F(L, 3) = 1 (bốc 3).
Để tính f(C, 4) ta để ý rằng lúc này đối thủ đang có số lẻ viên kẹo. Nếu ta bốc 1, 2 hoặc 3 viên thì sẽ đưa đối thủ đến các trạng thái (L, 3), (L, 2), (L, 1) tương ứng, và đều là các trạng thái thắng của đối thủ. Suy ra f(C, 4) = 0. Với f(L, 4) ta bốc 3 viên, đưa đối thủ vào trạng thái thua (C, 1) và giành chiến thắng.
Tiếp tục, để tính f(C, 5) ta để ý rằng lúc này đối thủ đang có số chẵn viên kẹo. Do đó ta bốc 1 viên và đưa đối thủ vào trạng thái (C, 4) là trạng thái thua, như vậy f(C,5) = 1. Ngược lại từ (L, 5) ta chỉ có thể đưa về (L, 4), (L, 3), (L, 2) là các trạng thái thắng, suy ra f(L, 5) = 0.
Nói tóm lại, một trạng thái là thua nếu mọi cách đi đều đưa về trạng tháng thắng (cho đối thủ), một trạng thái là thắng nếu có một cách đi đưa về trạng thái thua (cho đối thủ). Bằng lý luận này, ta lập được bảng giá trị sau.
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |
| C | 0 | 1 | 1 | 0 | 1 | 1 | 1 | 1 | 0 |
| L | 1 | 1 | 1 | 1 | 0 | 1 | 1 | 0 | 1 |
| 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | |
| C | 1 | 1 | 0 | 1 | 1 | 1 | 1 | 0 | 1 |
| L | 1 | 1 | 1 | 0 | 1 | 1 | 0 | 1 | 1 |
| 19 | 20 | 21 | 22 | 23 | 24 | 25 | |||
| C | 1 | 0 | 1 | 1 | 1 | 1 | 0 | ||
| L | 1 | 1 | 0 | 1 | 1 | 0 | 1 |
Như vậy f(C, 25) = 0, tức là Bình có chiến thuật thắng.
(Đây là bài toán khá khó trong lý thuyết thuật toán và trò chơi).
a. Để Lan bốc được cái kẹo cuối cùng thì số kẹo còn lại trong lượt cuối của Khoa bốc phải bằng 6 để số kẹo còn lại trong khi Khoa bốc luôn nằm trong khả năng của Lan.
Khoa lấy 1 - Lan lấy 5
Khoa lấy 2 - Lan lấy 4
Khoa lấy 3 - Lan lấy 3
Khoa lấy 4 - Lan lấy 2
Khoa lấy 5 - Lan lấy 1
Số kẹo Lan phải bốc trong lượt đầu là: 10 - 6 = 4 cái
Vậy Lan phải bốc 4 cái trong lượt đầu
b. Để Lan thắng thì số kẹo lượt trước Khoa bốc luôn là bội của 6
để số kẹo còn lại trong lượt cuối Khoa bốc chắc chắn bằng 6 thì Lan sẽ thắng
Bội của 6 gần 74 là 72 nên Lan cần bốc 2 viên trong lượt đầu (74-72=2) và các lần tiếp theo bốc sao cho số kẹo còn lại trước lượt Nam bốc luôn phải bằng 6