XXIX OM - III - Zadanie 4

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} $.

Komentarze

Dodaj nową odpowiedź