폴리매스

1400번째 문제 기념 문제입니다.

X와 Y는 서로 대화하기를 좋아합니다. 하지만 이 대화가 너무 시끄럽던 Z는 내일부터 X와 Y를 서로 다른 방에 가둬 놓기로 했습니다.

물론 Z는 인간적이라 방에만 갇혀 있으면 답답해 할 X, Y를 배려해 심심할 때마다 한 번씩 둘 중 한 명을 무작위로 선정하여 1분간 휴식을 취하기 위해 밖에 나올 수 있게 허락하기로 했습니다.

하지만 이것도 대화의 욕구를 막을 수는 없는 법. X와 Y는 Z가 모르는 곳에 1*N 크기 격자판과 돌 하나가 있는 것을 찾아냈습니다. 이걸로 대화를 할 수 있을까요?

아래는 조건입니다.

X와 Y는 내일까지는 작전을 세울 수 있으며, Z가 휴식자를 고를 때 10번 연속 같은 사람이 당첨되는 일이 없습니다.

X와 Y는 돌 외 다른 방법으로 정보를 듣거나 줄 수 없으며, X나 Y 중 한 명이 휴식을 취하러 방 밖으로 나가더라도 나머지 한 명은 이 사실을 알지 못합니다.

돌을 이용하여 대화를 하는 데에 시간 제한은 없습니다.

돌은 격자 칸 중 한 곳에 위치해야 하며, 여러 곳에 걸치거나 칸 밖으로 나갈 수 없습니다. X와 Y는 돌이 어느 칸 위에 있는지만으로 의사소통을 해야 하며, 돌이 칸 중앙에 있는지, 경계에 가까이 있는지 등의 요소로는 의사소통을 할 수 없습니다.

1) 대화를 성공적으로 하려면 N이 최소 얼마 이상이어야 할까요?

2) N이 1)번 소문제의 최솟값일 때, 대화 전략을 세워 봅시다.