Một trò chơi với các hòn bi màu
Ngô Quang Hưng | 22 tháng 06, 2008 | 
Bản để in
Mấy tháng nay tôi đang giải một bài toán rất thú vị. Sau đây là mô tả bằng ngôn ngữ bình dân một trường hợp (rất) đặc biệt của nó.
Tí và Tèo chơi trò chơi sau đây:
- Cho trước các tham số nguyên dương m và n cho trò chơi
- Khi bắt đầu trò chơi: có một dãy dài n cái hộp rỗng xếp thành hàng ngang
- Tèo có bi thuộc về k màu khác nhau, mỗi màu có vô số viên
- Trò chơi được chia thành nhiều lượt. Mỗi lượt đi thì Tí đi trước.
- Tí chỉ được làm một trong hai tác vụ: Hoặc là chọn một hộp X nào đó, hoặc là chọn một viên bi nào đó đang nằm trong một trong các hộp.
- Đến lượt Tèo: nếu Tí chọn hộp X, thì Tèo phải bỏ vào X một viên bi có màu khác tất cả các viên bi trong X và khác tất cả các viên bi trong (các) hộp kề X (nếu không làm được thì Tèo “bị chặn“); nếu Tí chọn một viên bi thì Tèo lấy viên bi đó ra khỏi hộp.
- Nếu tổng số bi trong X và hộp bên trái đã là m thì Tí không được chọn hộp X
- Nếu tổng số bi trong X và hộp bên phải đã là m thì Tí không được chọn hộp X
Câu hỏi là: giả sử Tí cực thông minh, tổng số màu bi k (chứ không phải tổng số bi) mà Tèo cần ít nhất là bao nhiêu để không bị chặn.
Nếu xếp các hộp thành hình tròn thay vì xếp hàng ngang thì sao?
Bài toán tôi đang giải phức tạp hơn nhiều. Các hộp được xếp theo một đồ thị cho trước (là các cạnh đồ thị). Các cạnh kề chung một đỉnh là các hộp “kề” nhau. Tí khi chọn hộp còn được chọn cân nặng cho viên bi mà Tèo phải bỏ vào. Tèo phải làm sao để tổng cân nặng các viên bi cùng màu kề cùng một đỉnh nhiều nhất là 1 kg. Còn nhiều biến thể khác cho bài này. Giải được mỗi biến thể đều viết paper được.
Thiển ý của cháu như thế này: nếu Tí muốn bắt bí Tèo thì cách đơn giản nhất là cứ chọn đi chọn lại riết 1 hộp nào đó cho đến lúc Tèo bị “dính chưởng”. Vì số loại bi tối đa Tí có thể bỏ liên tục vào 1 hộp là m nên số loại bi tối thiểu Tèo cần đến là m nốt :-/. Chắc là cháu sai lầm ở đâu phải không
Bạn sai lầm vì ko để ý yêu cầu:
# Nếu tổng số bi trong X và hộp bên trái đã là m thì Tí không được chọn hộp X
# Nếu tổng số bi trong X và hộp bên phải đã là m thì Tí không được chọn hộp X
Vì nếu Tí chọn mãi 1 hộp X, đến lần thứ m hộp X có m bi, Tí ko thể đc chọn X và cả 2 hộp kề X nữa. Do đó Tèo vẫn chưa bị chặn
@anh Hưng: em nghĩ mãi vẫn chưa hiểu ứng dụng bài toán này trong thực tế
@Kiều Phương: các hộp xếp thành vòng tròn hay thẳng hàng thì tôi không biết ứng dụng, nhưng nếu các hộp xếp theo một cấu trúc đồ thị tổng quát thì có nhiều ứng dụng. Đại khái nó là một dạng bài dynamic resource scheduling without conflict.
Ối trời ơi cái đoạn ở giữa dấu nhỏ hơn và lớn hơn của cháu đi đâu mất rồi? Xin lỗi để cháu đánh lại.
@Kiều Phương: OK đấy là trong trường hợp k bằng m thì dễ thấy Tí không có cách nào chặn Tèo cả. Nhưng nếu k nhỏ hơn m thì làm thế nào để chặn Tèo đây? Đơn giản nhất là cứ chọn đi chọn lại 1 hộp X nào đó và cách này chắc chắn luôn hiệu nghiệm. Tóm lại k phải lớn hơn hoặc bằng m để Tèo không thể bị chặn. Vậy, min k bằng m.
Thấy kỳ kỳ :-S
@ Ngọc Minh: Lý luận của bạn thiếu chính xác ở chỗ này:
“Nếu có điều kiện X, thì A sẽ xảy ra
Vậy kết luận, để A xảy ra phải có X”
lý do: (có thể) có điều kiện Y, A vẫn xảy ra. Và như thế, kết luận phải là “Để A xảy ra, cần có X hoặc Y hoặc Z…..”
Để đoạn lý luận “min k=m” là đúng, bạn cần chứng minh thêm là “Không thể có trường hợp Y nào (Y khác X) để A vẫn xảy ra hết”