Câu hỏi 83
Ở tâm mỗi ô của một bảng $12\times12$ có một viên sỏi. Hai người chơi, Người tô màu và Người búng sỏi, chơi trò chơi sau.
Người tô màu chọn một số màu rồi tô mỗi viên sỏi bằng một trong các màu đó. Người búng sỏi chọn hai viên cùng màu mà giữa chúng không có viên sỏi nào chắn, di chuyển một viên đến vị trí của viên kia rồi lấy đi viên bị thay thế. Người búng sỏi tiếp tục làm như vậy cho đến khi không còn cặp nào hợp lệ. Người tô màu lấy các viên sỏi còn lại. Ai có nhiều sỏi hơn thì thắng. Số màu ít nhất mà Người tô màu cần để chắc chắn thắng, bất kể Người búng sỏi chơi thế nào, là bao nhiêu?
Giải thích: giả sử các viên sỏi đủ nhỏ và nằm đúng tại tâm các ô. Với ba viên sỏi $x,y,z$, ta nói $y$ chắn $x$ và $z$ nếu tâm ô chứa $y$ nằm trên đoạn thẳng nối tâm hai ô chứa $x$ và $z$. Gọi thao tác của Người búng sỏi là một lần búng. Trong ví dụ dưới đây, các viên màu đỏ có thể được búng, các viên màu xanh lá không thể được búng, còn đối với các viên màu vàng và xanh dương, có những cặp búng được và có những cặp không búng được.
Người tô màu chọn một số màu rồi tô mỗi viên sỏi bằng một trong các màu đó. Người búng sỏi chọn hai viên cùng màu mà giữa chúng không có viên sỏi nào chắn, di chuyển một viên đến vị trí của viên kia rồi lấy đi viên bị thay thế. Người búng sỏi tiếp tục làm như vậy cho đến khi không còn cặp nào hợp lệ. Người tô màu lấy các viên sỏi còn lại. Ai có nhiều sỏi hơn thì thắng. Số màu ít nhất mà Người tô màu cần để chắc chắn thắng, bất kể Người búng sỏi chơi thế nào, là bao nhiêu?
Giải thích: giả sử các viên sỏi đủ nhỏ và nằm đúng tại tâm các ô. Với ba viên sỏi $x,y,z$, ta nói $y$ chắn $x$ và $z$ nếu tâm ô chứa $y$ nằm trên đoạn thẳng nối tâm hai ô chứa $x$ và $z$. Gọi thao tác của Người búng sỏi là một lần búng. Trong ví dụ dưới đây, các viên màu đỏ có thể được búng, các viên màu xanh lá không thể được búng, còn đối với các viên màu vàng và xanh dương, có những cặp búng được và có những cặp không búng được.