임의의 일대일대응 $f :\{1, 2, \ldots, n\}\to\{1, 2,\ldots, n\}$ ($n$은 양의 정수)에 대하여, 네 집합 $A$, $B$, $C$, $D$를 다음과 같이 정의하자. \[ A=\{i \mid i \gt f(i)\}\]\[ B=\{(i,j)\mid i\lt j \le f(j)\lt f(i)\text{ 또는 } f(j)\lt f(i) \lt i\lt j\}\]\[ C=\{(i,j)\mid i\lt j \le f(i)\lt f(j)\text{ 또는 } f(i)\lt f(j) \lt i\lt j\}\]\[ D=\{ (i,j)\mid i\lt j \text{이고 } f(i)\gt f(j)\}\] 다음 등식이 성립함을 보여라. (단, $|X|$는 집합 $X$의 원소의 개수이다.)\[ |A|+2|B|+|C|=|D|\]
(2013년 3월 24일, 4시간 30분)