Trong một lọ chứa n cái kẹo (n € N*) hai bạn làm và khoa chơi một trò chơi như sau : hai bạn luân phiên lấy kẹo trong lọ bỏ ra ngoài , mỗi lần chỉ đc lấy 1;2;3;4hoặc5 cái kẹo. Người đc cái kẹo cuối cùng trong lọ là người thắng cuộc . Nếu lần là người đi trc : a) Với n=10 , hãy chỉ ra cách chơi của Lần để Lần là người thắng cuộc. b) Với n=74, hãy chỉ ra cách chơi để lần là ng thắng cuộc
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.
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
Để tìm chiến thuật chơi để An là người thắng cuộc, ta cần xem xét các trường hợp có thể xảy ra.
Trong trường hợp này, số viên kẹo trong hai túi là 18 và 21. Ta có thể tạo bảng để phân tích các trường hợp:
| Lượt chơi | Túi 1 (18 viên) | Túi 2 (21 viên) |
|-----------|----------------|----------------|
| 1 | 17 | 20 |
| 2 | 16 | 19 |
| 3 | 15 | 18 |
| 4 | 14 | 17 |
| 5 | 13 | 16 |
| 6 | 12 | 15 |
| 7 | 11 | 14 |
| 8 | 10 | 13 |
| 9 | 9 | 12 |
| 10 | 8 | 11 |
| 11 | 7 | 10 |
| 12 | 6 | 9 |
| 13 | 5 | 8 |
| 14 | 4 | 7 |
| 15 | 3 | 6 |
| 16 | 2 | 5 |
| 17 | 1 | 4 |
| 18 | 0 | 3 |
Dựa vào bảng trên, ta nhận thấy rằng nếu An chơi một cách thông minh, an sẽ luôn giữ số viên kẹo trong hai túi ở cùng một mức. Điều này đảm bảo rằng Bình sẽ không thể lấy hết kẹo từ một túi nào đó và An sẽ luôn có cơ hội lấy kẹo từ túi còn lại.
Vì vậy, chiến thuật chơi của An là giữ số viên kẹo trong hai túi ở cùng mức. Khi Bình lấy đi một viên kẹo từ một túi, An sẽ lấy đi một viên kẹo từ túi còn lại để duy trì số viên kẹo ở cùng mức.
Với chiến thuật này, An sẽ luôn là người thắng cuộc vì An có thể điều khiển trò chơi sao cho Bình không thể lấy hết kẹo từ một túi nào đó.
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).
jerry 13 kẹo
tom 12 kẹo
jerry 11 kẹo
tom 10 kẹo
jerry 9 kẹo
tom 8 kẹo
...............
jerry có
1+1+1+1+1+1+1=7 viên kẹo
bài mày giống của tao ihet cả đoạn tom và jerry nữa nhưng của tao là lớp 6
Ta xét 1 bất biến rất thú vị như sau:
Ta viết số các bông hoa trong mỗi nhóm dưới dạng nhị phân:
\(1=1_2\), \(2=10_2\), \(3=11_3\) và tổng S của các số này được tính theo quy tắc sau:
\(S=01+10+11=00\) (nếu hàng có chẵn số 1 thì KQ bằng 0 còn nếu có lẻ số 1 thì KQ bằng 1)
Ta có 2NX:
NX1: Nếu đến lượt chơi của 1 người nào đó mà tổng S đang bằng 0 thì do dù có chơi như thế nào, tổng S cũng sẽ khác 0.
NX2: Nếu đến lượt chơi của 1 người nào đó mà tổng S đang khác 0 thì luôn có 1 nước đi cho người đó để đưa tổng S về lại bằng 0. (đây chính là chiến thuật để thắng trò chơi)
Trong trò chơi này, ta thấy tổng S ban đầu bằng 0 nên theo NX1, dù An có bốc như thế nào thì tổng S cũng sẽ khác 0. Kế đó, sử dụng NX2, Bình luôn có thể bốc để cho tổng S về lại bằng 0 và cứ tiếp tục như thế, Bình là người sẽ đưa được số sỏi về trạng thái (0,0,0) (vì khi đó \(S=0\))
Cuối cùng là số hoa chứ không phải số sỏi đâu. Trò chơi này chính là 1 phiên bản của trò chơi Nim, bạn có thể tìm hiểu trên mạng.