2015 FKMO #3

2019년 1월 20일 에 작성됨 FKMO(2015)

0 2018년 4월 29일

지하철역이 $3$개 이상인 도시가 있다. 이 도시에서 같은 지하철역을 두 번 이상 지나지 않고도 총 $L+1$ 개 이상의 지하철역을 지나는 경로가 있다면 다음 중 하나는 반드시 성립함을 보여라. (단, 지하철역은 양방향으로 모두 운행한다.)

(i) 서로 다른 세 개의 지하철역 $A,B,C$가 존재하여 $C$를 지나지 않고 $A$에서 $B$로 가는 경로가 없다.

(ii) 적당한 지하철역에서 출발하여 같은 지하철역을 두 번 이상 지나지 않고 출발했던 지하철역으로 되돌아오는 방법 중 지하철역 $\left \lceil \sqrt{2L}\right \rceil$개 이상을 지나는 방법이 있다. 단,  $\lceil x \rceil$는 $x$보다 작지 않은 정수 중 가장 작은 것이다.

 
    \
  • Liked by
Reply
Loading more replies