Zbiory indeksów
-
mol_ksiazkowy
- Użytkownik
- Posty: 13433
- Rejestracja: 9 maja 2006, o 12:35
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 3429 razy
- Pomógł: 809 razy
Zbiory indeksów
Dane są niepuste zbiory \(\displaystyle{ A_1,..,A_{n+1} }\) podzbiory\(\displaystyle{ \{1,...,n \}}\). Udowodnić, że istnieją takie niepuste i rozłączne zbiory indeksów \(\displaystyle{ I, J}\) że \(\displaystyle{ \bigcup_{i \in I } A_i =\bigcup_{j \in J } A_j }\)
-
arek1357
Re: Zbiory indeksów
Wszystkich takich sum jest maksymalni tyle ile podzbiorów niepustych zbioru:
\(\displaystyle{ \left\{ 1,2,3,...,n,n+1\right\} }\) czyli: \(\displaystyle{ 2^{n+1}-1 }\)
\(\displaystyle{ \bigcup_{s \in I}^{n} A_{s}}\)
Ale: \(\displaystyle{ A_{s}}\) to podzbiory zbioru: \(\displaystyle{ \left\{ 1,2,3,...,n\right\} }\)
więc różnych może być co najwyżej:
\(\displaystyle{ 2^n-1 }\)
znaczy, że jakieś się pokrywają...
\(\displaystyle{ \left\{ 1,2,3,...,n,n+1\right\} }\) czyli: \(\displaystyle{ 2^{n+1}-1 }\)
\(\displaystyle{ \bigcup_{s \in I}^{n} A_{s}}\)
Ale: \(\displaystyle{ A_{s}}\) to podzbiory zbioru: \(\displaystyle{ \left\{ 1,2,3,...,n\right\} }\)
więc różnych może być co najwyżej:
\(\displaystyle{ 2^n-1 }\)
znaczy, że jakieś się pokrywają...