2014 FKMO #6

2019년 3월 26일 에 작성됨 FKMO(2014)

0 2018년 4월 30일

어떤 섬에 $n$개의 성이 있고, 각 성은 $A,B$나라 중 하나에 속한다고 하자. 각 성에는 그 나라의 장수가 $1$명씩 있다. 어느 두 성 사이에 다른 성을 지나지 않고 이동할 수 있는 길이 있으면 그 두 성이 이웃한다고 하자. 다음 두 명제가 필요충분조건임을 보여라.

명제 1: $B$나라의 장수들 중 일부가 각각 이웃한 $A$성 중 하나를 무작위로 골라 동시에 공격하더라도, $A$나라 장수들 중 일부를 이웃한 성들로 동시에 잘 움직여 방어를 하게 하면, $A$나라 각 성에 대하여, 그 성을 공격하는 $B$나라 장수의 수보다 그 성을 방어하는 $A$나라 장수의 수가 많거나 같게 할 수 있다.

명제 2: $A$나라 성들로 이루어진 임의의 집합 $X$에 대해, $X$에 속하거나 $X$ 중 적어도 하나에 이웃한 $A$나라 성의 개수가, $X$ 중 적어도 하나에 이웃한 $B$나라 성의 개수보다 많거나 같다.

 
    \
  • Liked by
Reply
Loading more replies