Câu hỏi 15
Với mỗi tập hợp hữu hạn $X$, kí hiệu $|X|$ là số phần tử của $X$. Định nghĩa
$$
S_n = \sum |A \cap B|,
$$
trong đó tổng được lấy trên tất cả các cặp có thứ tự $(A, B)$ sao cho $A$ và $B$ là các tập con của $\{1, 2, 3, \dots, n\}$ với $|A| = |B|$. Ví dụ, $S_2 = 4$ vì tổng được lấy trên các cặp tập con
$$
(A, B) \in \{(\emptyset, \emptyset), (\{1\}, \{1\}), (\{1\}, \{2\}), (\{2\}, \{1\}), (\{2\}, \{2\}), (\{1, 2\}, \{1, 2\})\},
$$
cho $S_2 = 0 + 1 + 0 + 0 + 1 + 2 = 4$. Đặt $\frac{S_{2022}}{S_{2021}} = \frac{p}{q}$, trong đó $p$ và $q$ là các số nguyên dương nguyên tố cùng nhau. Tìm số dư khi chia $p+q$ cho 1000.
$$
S_n = \sum |A \cap B|,
$$
trong đó tổng được lấy trên tất cả các cặp có thứ tự $(A, B)$ sao cho $A$ và $B$ là các tập con của $\{1, 2, 3, \dots, n\}$ với $|A| = |B|$. Ví dụ, $S_2 = 4$ vì tổng được lấy trên các cặp tập con
$$
(A, B) \in \{(\emptyset, \emptyset), (\{1\}, \{1\}), (\{1\}, \{2\}), (\{2\}, \{1\}), (\{2\}, \{2\}), (\{1, 2\}, \{1, 2\})\},
$$
cho $S_2 = 0 + 1 + 0 + 0 + 1 + 2 = 4$. Đặt $\frac{S_{2022}}{S_{2021}} = \frac{p}{q}$, trong đó $p$ và $q$ là các số nguyên dương nguyên tố cùng nhau. Tìm số dư khi chia $p+q$ cho 1000.