Câu hỏi 79
Cho một song ánh $f:\{1,2,\dots,n\}\to\{1,2,\dots,n\}$ với số nguyên dương $n$. Định nghĩa
$$A=\{i\mid i\gt f(i)\},$$
$$\begin{aligned}B=\{(i,j)\mid&\ i\lt j\le f(j)\lt f(i)\\&\text{hoặc }f(j)\lt f(i)\lt i\lt j\},\end{aligned}$$
$$\begin{aligned}C=\{(i,j)\mid&\ i\lt j\le f(i)\lt f(j)\\&\text{hoặc }f(i)\lt f(j)\lt i\lt j\},\end{aligned}$$
$$D=\{(i,j)\mid i\lt j\text{ và }f(i)\gt f(j)\}.$$
Chứng minh $|A|+2|B|+|C|=|D|$, trong đó $|X|$ là số phần tử của $X$.
$$A=\{i\mid i\gt f(i)\},$$
$$\begin{aligned}B=\{(i,j)\mid&\ i\lt j\le f(j)\lt f(i)\\&\text{hoặc }f(j)\lt f(i)\lt i\lt j\},\end{aligned}$$
$$\begin{aligned}C=\{(i,j)\mid&\ i\lt j\le f(i)\lt f(j)\\&\text{hoặc }f(i)\lt f(j)\lt i\lt j\},\end{aligned}$$
$$D=\{(i,j)\mid i\lt j\text{ và }f(i)\gt f(j)\}.$$
Chứng minh $|A|+2|B|+|C|=|D|$, trong đó $|X|$ là số phần tử của $X$.