2013 국제수학올림피아드 Short List C3

미친 물리학자가 어느날 실험실에서 이몬이라는 새로운 물질을 우연히 발견하게 되었따. 실험실에 있는 두 이몬끼리는 서로 엮일 수 있으며, 하나의 이몬은 여러 이몬과 엮일 수 있다. 이 물리학자는 아래와 같은 두 가지 방법의 연산을 실험실에 있는 이몬에게 적용할 수 있는 방법을 찾았다.

(i) 홀수개의 다른 이몬과 엮인 이몬은 파괴할 수 있다.
(ii) 각 이몬 $I$에 대해 그 사본 $I’$을 생성하여 전체 실험실 내 이몬을 두 배로 늘릴 수 있다. 이때 두 사본 $I’$, $J’$은 그 원본 $I$, $J$까 엮여있을때만 엮이게 되며, 각각의 사본 $I’$는 원본 $I$와 엮이게 되고, 이 외의 다른 식으로 엮인 관계가 생기거나 사라지지 않는다.

이때 이 물리학자가 이 연산들을 적절한 순서로 잘만 적용하면 서로 엮인 이몬이 없는 상태가 되도록 만들 수 있음을 보여라.

GD Star Rating
loading...