Câu hỏi 54
Một trò chơi điện tử chiến thuật có bản đồ gồm hữu hạn thị trấn. Mỗi thị trấn có $k$ hướng, đánh số từ 1 đến $k$. Một thị trấn được chỉ định là điểm xuất phát, một thị trấn là đích. Từ điểm xuất phát, nhân vật thực hiện một dãy hữu hạn bước đi. Mỗi bước chọn một hướng tại thị trấn hiện tại; lựa chọn ấy xác định thị trấn tiếp theo và một lượng điểm dương nhận được.
Hai trò chơi tương đương nếu với mỗi dãy hướng giúp nhân vật đi từ điểm xuất phát đến đích trong một trò, nhân vật cũng làm được như vậy trong trò kia, đồng thời nhận cùng tổng điểm ở hai trò.
Vào sinh nhật, John nhận hai trò chơi chiến thuật, một có $N$ thị trấn, một có $M$ thị trấn. John cho rằng chúng tương đương. Marry tin rằng không, và Marry đúng. Chứng minh cô ấy có thể đưa ra một dãy nhiều nhất $N + M$ hướng chứng tỏ hai trò thật sự không tương đương.
Stefan Gerdjikov, Bulgaria
Hai trò chơi tương đương nếu với mỗi dãy hướng giúp nhân vật đi từ điểm xuất phát đến đích trong một trò, nhân vật cũng làm được như vậy trong trò kia, đồng thời nhận cùng tổng điểm ở hai trò.
Vào sinh nhật, John nhận hai trò chơi chiến thuật, một có $N$ thị trấn, một có $M$ thị trấn. John cho rằng chúng tương đương. Marry tin rằng không, và Marry đúng. Chứng minh cô ấy có thể đưa ra một dãy nhiều nhất $N + M$ hướng chứng tỏ hai trò thật sự không tương đương.
Stefan Gerdjikov, Bulgaria