Câu hỏi 103
Tòa nhà chính của ETH Zürich là một hình chữ nhật được chia thành các ô vuông đơn vị. Mỗi cạnh của một ô vuông là một bức tường, trong đó một số bức tường có cửa. Tường bao ngoài của tòa nhà chính không có cửa nào. Một số thí sinh SMO bị lạc trong tòa nhà chính. Họ chỉ có thể đi từ ô này sang ô khác qua các cửa. Giả sử giữa hai ô bất kỳ của tòa nhà chính luôn có một đường đi được.
Cyril muốn các thí sinh tìm lại được nhau bằng cách dẫn tất cả họ đến cùng một ô. Để làm điều đó, anh có thể đưa cho họ các chỉ dẫn sau qua bộ đàm: Bắc, Đông, Nam hoặc Tây. Sau mỗi chỉ dẫn, mọi thí sinh đồng thời cố gắng đi một ô theo hướng đó. Nếu bức tường tương ứng không có cửa thì người đó đứng yên.
Chứng minh rằng Cyril có thể đạt được mục tiêu sau hữu hạn chỉ dẫn, bất kể lúc đầu các thí sinh đứng ở những ô nào.
Cyril muốn các thí sinh tìm lại được nhau bằng cách dẫn tất cả họ đến cùng một ô. Để làm điều đó, anh có thể đưa cho họ các chỉ dẫn sau qua bộ đàm: Bắc, Đông, Nam hoặc Tây. Sau mỗi chỉ dẫn, mọi thí sinh đồng thời cố gắng đi một ô theo hướng đó. Nếu bức tường tương ứng không có cửa thì người đó đứng yên.
Chứng minh rằng Cyril có thể đạt được mục tiêu sau hữu hạn chỉ dẫn, bất kể lúc đầu các thí sinh đứng ở những ô nào.