폴리매스

(로고는 지나가던 사람님이 만들어 주셨습니다. 사람님 너무 보고싶고 그리웠습니다ㅠㅠㅠㅠㅠ)

가로로 n칸 세로로 m칸이 있는 전체 직사각형 모양인 바둑판이 있다. 이 바둑판에 지나가던 사람이 코딩한 로봇들을 배치한다. 한 칸에 들어갈 수 있는 로봇의 수는 제한이 없다고 한다. 두 칸이 접하는 곳에 있는 선분은 빨간색이거나 파란색인데, 직사각형 바깥 가장자리의 선분은 모두 빨간색이라고 한다.

로봇에게 위, 아래, 왼쪽, 오른쪽이라는 4가지 명령어를 줄 수 있다. 명령어를 주면 모든 로봇은 같은 명령을 동시에 수행하고자 지시받은 방향으로 한 칸 이동하되, 그 사이의 선분이 빨강색인 경우는 그 로봇은 이동하지 않고 제 자리를 지킨다. 이러한 명령어는 원하는 만큼 줄 수 있다.

임의의 로봇에 대해 그 로봇을 원하는 칸으로 이동할 수 있는 명령어 유한개의 나열이 존재한다고 하자. 이때, 모든 로봇을 같은 칸으로 모으도록 하는 명령어 유한개의 나열이 반드시 존재함을 증명하라.