XXIX OM - III - Zadanie 4

Zawody matematyczne:

XXIX OM, 1977-1978

Etap:

III

Niech $X$ będzie zbiorem $n$ -elementowym. Udowodnić, że suma liczb elementów zbiorów $A \cap B$ rozciągnięta na wszystkie pary uporządkowane $(A, B)$ podzbiorów zbioru $X$ równa jest $n\cdot 4^{n-1}$ .

Rozwiązanie

Niech $a$ będzie ustalonym elementem zbioru $X$ . Liczba podzbiorów zbioru $X$ zawierających element $a$ jest równa liczbie wszystkich podzbiorów zbioru $(n-1)$ -elementowego $X- \{a\}$ , to znaczy jest równa $2_{n-1}$ . Wobec tego liczba takich par $(A, B)$ podzbiorów zbioru $X$ , że $a \in A \cap B$ , jest równa $(2^{n-1})^2 =4^{n-1}$ .

Inaczej mówiąc, w sumie, o której jest mowa w zadaniu, element $a$ jest liczony $4^{n-1}$ razy. Ponieważ zbiór $X$ ma $n$ elementów, więc cała ta suma jest równa $n \cdot 4^{n-1}$ .