본문바로가기
함께 풀고 싶은 문제
직접 문제를 올려 폴리매스 출제자에 이름을 올리세요!
출제 TOP 304.01 10시 ~ 04.08 10시 기준
[함께 풀고 싶은 문제] 경찰과 도둑 2
인간의 이중성 2020.02.21

경찰이 도둑을 잡고 있다. 도둑은 n개의 은신처 중 하나에 숨어 있으며, 경찰은 이 사실을 알고 있다. 이 은신처 A1, ... , An이 무작위로 배열되어 있고 이 은신처들의 일부는 선으로 연결되어 있다고 할 때, 하루가 지나면 도둑은 한 선분으로 연결된 은신처로 이동한다. 경찰은 꼭 인접한 은신처로 이동할 필요는 없다. 은신처를 옮기는 도중에 경찰이 도둑을 잡는 경우는 없다고 할 때, 다음을 증명하시오.(경찰은 하루에 한 은신처만 수색할 수 있다.)

 

"모든 i, j에 대해, Ai, Aj를 연결하는 모든 경로들의 길이는 전부 홀수이거나 짝수이다. 이 때 필요한 경찰의 최소 수가 \frac{n}{2}이하임을 보이시오."

(단, i, j의 값에 따라 경로의 길이의 홀짝성은 변할 수 있음)

이 문제 어떠셨나요?

유익해요

0

웃겨요

0

신기해요

0

어려워요

0