아래는 원문입니다.

( http://acm.pku.edu.cn/JudgeOnline/problem?id=1234 에서 가져옴)

Classmates stand in a circle facing inward, each with the direction left or right in mind. One of the students has a ball and begins by tossing it to another student. (It doesn't really matter which one.)When one catches the ball and is thinking left, she throws it back across the circle one place to the left (from her perspective) of the person who threw her the ball. Then she switches from thinking left to thinking right. Similarly, if she is thinking right, she throws the ball to the right of the person who threw it to her and then switches from thinking right to thinking left.

There are two exceptions to this rule: If one catches the ball from the classmate to her immediate left and is also thinking left, she passes the ball to the classmate to her immediate right, and then switches to thinking right. Similarly, if she gets the ball from the classmate to her immediate right and is thinking right, she passes the ball to the classmate to her immediate left, and then switches to thinking left.(Note that these rules are given to avoid the problem of tossing the ball to oneself.)

No matter what the initial pattern of left and right thinking is and who first gets tossed the ball,everyone will get tossed the ball eventually!


제가 이해한 대로 정리해본 건 아래와 같습니다.

n명의 사람들이 원을 이루면서 안쪽을 보고 있고, 맨 처음에 한 학생이 공을 하나 갖고 있습니다. 맨 처음 던지는 공은 어디로 던져져도 상관없지만, 그 다음부터는 공을 받은 사람이, 공을 자신에게 준 사람의 인접한 왼쪽이나 오른쪽으로 줍니다. 단, 모든 사람은 자신이 왼쪽으로 던질 지, 오른쪽으로 던질 지 미리 결정한 상태이며, 그 상태는 자신이 공을 던진 후에 즉시 반대로 바뀝니다. 이 규칙에는 예외가 있는데, 자신에게 자신이 공을 던지지 않기 위해서, 혹여나 이 규칙대로 했을 때 자신이 받게된다면, 자신이 없다고 생각하고 인접한 사람에게 규칙대로 던져줍니다.

이 때 원을 만드는데 참여한 모든 사람이 게임이 어떤 상태로 시작되건간에 무조건 공을 던질 기회가 생긴다는 사실을 증명하고 싶습니다. 또는 간단한 스케치도 고맙습니다. 아는 사람에게 증명을 제시해주고 싶은데, 깔끔한 방법이 잘 안 떠오르네요.

고맙습니다.