지하철역이 $3$개 이상인 도시가 있다. 이 도시에서 같은 지하철역을 두 번 이상 지나지 않고도 총 $L+1$개 이상의 지하철역을 지나는 경로가 있다면 다음 중 하나는 반드시 성립함을 보여라.(단, 지하철은 양방향으로 모두 운행한다.)
(i) 서로 다른 세 개의 지하철역 $A$, $B$, $C$가 존재하여 $C$를 지나지 않고 $A$에서 $B$로 가는 경로가 없다.
(ii) 적당한 지하철역에서 출발하여 같은 지하철역을 두 번 이상 지나지 않고 출발했던 지하철역으로 되돌아오는 방법 중 지하철역 $\lceil\sqrt{2L}\rceil $개 이상을 지나는 방법이 있다. 단, $\lceil x\rceil$는 $x$보다 작지 않은 정수 중 가장 작은 것이다.
태그 보관물: 회로
2013 미국 TSTST 5번문제
소수 $p$가 있다. 꼭지점이 $1000p$개인 완전그래프의 각 선에 정수값이 적혀있다면, 선에 적힌 수의 합이 $p$의 배수가 되는 (같은 꼭지점을 두 번 지나지 않는) 회로가 존재함을 증명하라.
(2013년 6월 23일, 4시간 반동안 3문제, 출처)
2012 중국여자수학올림피아드 6번문제
한 나라에 $n$개($n\ge 3$)의 도시와 두 개의 항공사가 있다. 임의의 두 도시 사이에는 이 두 도시를 오가는 항공편이 있고, 그 항공편은 모두 한 항공사가 운영한다. 한 여성 수학자가 한 도시에서 출발하여 그 도시로 돌아오는 여행을 하는데, 중간에 두 개 이상의 다른 도시를 각각 한번씩 거쳐서 돌아온다. 그 수학자가 어떤 도시에서 출발하든, 어떠한 경로를 택하든 상관없이 항상 두 항공사를 모두 이용하게 된다고 한다. 이러한 상황이 존재하도록 항공사를 배치할 수 있는 $n$ 중 가장 큰 값을 구하여라.
(2012년 8월 11일, 광저우, 둘째날 4시간동안 5~8번 문제)