지하철역이 $3$개 이상인 도시가 있다. 이 도시에서 같은 지하철역을 두 번 이상 지나지 않고도 총 $L+1$개 이상의 지하철역을 지나는 경로가 있다면 다음 중 하나는 반드시 성립함을 보여라.(단, 지하철은 양방향으로 모두 운행한다.)
(i) 서로 다른 세 개의 지하철역 $A$, $B$, $C$가 존재하여 $C$를 지나지 않고 $A$에서 $B$로 가는 경로가 없다.
(ii) 적당한 지하철역에서 출발하여 같은 지하철역을 두 번 이상 지나지 않고 출발했던 지하철역으로 되돌아오는 방법 중 지하철역 $\lceil\sqrt{2L}\rceil $개 이상을 지나는 방법이 있다. 단, $\lceil x\rceil$는 $x$보다 작지 않은 정수 중 가장 작은 것이다.
태그 보관물: 경로
2013 미국 TSTST 3번문제
$x=m$, $y=n$ ($m$, $n$은 정수)인 직선들을 그려 평면을 무한한 크기의 바둑판 형태로 자르자. 어떤 칸의 오른쪽 위 모서리의 $x$, $y$ 좌표 모두 짝수라면 그 칸을 검정으로 칠하고 그렇지 않다면 흰색으로 칠하여 전체 칸의 총 $1/4$이 검정색이 되게 하자. 두 홀수 $r$, $s$를 생각하자. 어떤 흰 칸 내부에서 $rx-sy$가 무리수가 되는 점 $(x,y)$를 생각하자. 이 점 $(x,y)$에서 빛을 기울기 $r/s$로 발사하는데, 흰 칸은 통과하고 검은 칸을 만나면 반사한다고 하자. 이때 이 빛이 지나가는 경로는 닫힌 폐곡선을 이루게 된다는 것을 증명하라.
(2013년 6월 21일, 4시간 반동안 3문제, 출처)