TRÒ CHƠI VỚI CÁC CON SỐ 2, 0, 1, 7
Nhân dịp đầu năm mới 2017, hai bạn Tí và Tèo chơi trò chơi bốc bi liên quan đến các chữ số 2, 0, 1, 7 như sau:
Trên bàn có 17 viên bi, hai người thay phiên nhau bốc, mỗi lần có thể bốc 1, 2, hoặc 7 viên bi. Ai đến lượt mình đi không còn bi để bốc (còn 0 viên) thì thua. Tí là người đi trước.
Biết rẳng cả hai bạn rất thông minh, đến lượt mình luôn biết cách bốc có lợi nhất cho mình.
Hỏi ở lần đi đầu tiên Tí phải bốc bao nhiêu viên (1 hay 2 hay 7) để bạn ấy chắc chắn thắng?
----------------------
Các bạn trình bày lời giải dầy đủ của mình vào ô Gửi ý kiến phía dưới. 05 bạn có lời giải hay và sớm nhất sẽ được cộng/thưởng 1 tháng VIP của Online Math. Đáp án và giải thưởng sẽ được công bố vào Thứ Sáu ngày 3/2/2017 (tức ngày 7 Tết ta). Bài toán 140 sẽ lên mạng ngay sau khi trao giải Bài toán 139.
---------------------
LỜI GIẢI
Cách 1: giải bằng cách tính ngược từ dưới lên.
Ta có nhận xét ban đầu:
- Nếu còn 0 viên bi thì người nào đến lượt đi sẽ thua. Vậy trạng thái 0 là thua
- Nếu còn 1, 2 hoặc 7 viên bi thì người nào đến lượt đi thì chỉ cần bốc nốt số bi này sẽ thẳng. Vậy trạng thái 1 hoặc 2 hoăc 7 là thắng.
Kí hiệu các trạng thái thắng là màu xanh, thua là màu đỏ thì ta có:
Ta sẽ xác định màu cho các trạng thái 3, 4, ... theo 2 qui tắc sau:
Qui tắc 1: Trạng thái thắng là trạng thái mà tồn tại ít nhất một cách đi để chuyển về trạng thái thua (màu đỏ) (dồn cho đối phương thua)
Qui tắc 2: Trạng thái thua là trạng thái mà mọi cách bốc đều chuyển về trạng thái thắng (màu xanh) (nói cách khác đi theo cách nào thì đối phương cũng thắng - giả thiết là cả hai đều rất thông minh).
Như vậy:
- Nếu còn 3 viên thì có 2 cách đi hợp lệ là bốc 1 hoặc 2 viên (không đủ 7 viên để bốc), khi đó đống bi còn lại là 1 hoặc 2 viên đều là trạng thái thắng (màu xanh). Suy ra 3 là trạng thái thua (màu đỏ).
- Nếu còn 4 viên thì có một cách đi bốc 1 viên để còn lại 3 viên (màu đỏ). Vậy 4 là trạng thái thắng (màu xanh).
- Nếu còn 5 viên thì có một cách đi bốc 2 viên còn lại 3 viên (màu đỏ). Vậy 5 cũng là trạng thái thắng (màu xanh).
- Nếu còn 6 viên thì cả hai cách đi hợp lệ là bốc 1 hoặc 2 viên đều chuyển về trạng thái màu xanh (5 hoặc 4). Vậy 6 là trạng thái thua - màu đỏ.
Cứ như vậy ta xác định các trạng thái tiếp theo 8, 9, .. cho đến 17 (chú ý rằng khi còn trên 8 viên có thêm cách bốc 7 viên ngoài cách bốc 1 hoặc 2 viên) như hình dưới đây:
Vậy 17 là trạng thái thắng (màu xanh) và Tí là người đi trước nên Tí thắng. Cách đi tối ưu là theo Qui tắc 1 ở trên, Tí phải bốc để trạng thái tiếp theo là thua (màu đỏ). Xét 3 cách đi:
- Cách đi bốc 1 viên còn lại 16 viên (màu xanh)
- Cách đi bốc 2 viên còn lại 15 viên (màu đỏ)
- Cách đi bốc 7 viên còn lại 10 viên (màu xanh)
Suy ra ban đầu Tí phải bốc 2 viên để dồn Tèo về trạng thái đỏ (trạng thái thua).
Cách 2:
Ta sẽ chứng minh rằng nếu A đến lượt mình đi mà số bi còn lại là các số không chia hết cho 3 thì A có cách chơi luôn thắng.
Thật vậy, khi số bi không chia hết cho 3, (giả sử dư 1 hoặc 2) thì A chỉ việc bốc số dư này để số bi còn lại chia hết cho 3. Đến lượt đối phương B đi thì cho dù B có bốc 1, 2 hoặc 7 viên thì số bi còn lại sẽ không chia hết cho 3. A luôn bốc để sao cho số bi còn lại là một số chia hết cho 3 và cuối cùng dồn B còn 0 viên.
Ban đầu số bi là 17 viên (17 chia 3 dư 2) nên Tí sẽ bốc 2 viên để số bi còn lại là một số chia hết cho 3. Và cho dù Tèo bốc thế nào thì Tí luôn luôn bốc số bi phù hợp để sao cho đến lượt Tèo đi thì số bi là số chia hết cho 3.
