[Kombinatoryka] Podzbiory - równe sumy

[KPR]

Dane są niepuste podzbiory \(\displaystyle{ A_1,A_2,\dots A_{n+1}}\) zbioru \(\displaystyle{ n}\)-elementowego. Udowodnij, że istnieją takie niepuste rozłączne zbiory indeksów \(\displaystyle{ I,J \subset \{1,2,\dots,n+1\}}\), że \(\displaystyle{ \bigcup\limits_{i\in I} A_i=\bigcup\limits_{i\in J} A_i}\)

[Swistak]

Wygląda na zbyt łatwe i zbyt grube:

Ukryta treść:    

Wystarczy udowodnić, że istnieją takie 2 dowolne zbiory indeksów, że zachodzi ta równość, bo aby otrzymać rozłączność wystarczy wywalić ich część wspólną. Każdy zbiór może mieć moc od 0 do n, zatem sumy, które rozpatrujemy w tezie nie mogą przekroczyć \(\displaystyle{ n(n+1)}\), zatem mogą przyjąć max \(\displaystyle{ n^2+n+1}\) wartości. Natomiast zbiorów indeksów jest \(\displaystyle{ 2^{n+1}}\) i nie chcę mi się sprawdzać kiedy, no ale z grubsza zachodzi \(\displaystyle{ 2^{n+1}>n^2+n+1}\), co wygląda na trochę podejrzane, bo to nieskończenie grube szacowanie i w ogóle rozwiązanie takie bardzo standardowe xd.

[KPR]

Ukryta treść:    

Hej hej, nie możemy wywalić części wspólnej. Przykład: \(\displaystyle{ A={1,2},B={1},C{2}}\). suma A i B jest równa sumie B i C, ale A nie jest równe C. A w ogóle to coś pomieszałeś, jakbyś nie wiedział, co to suma

[Swistak]

A lol, bo to w sensie ile należy do co najmniej jednego, a nie suma mocy każdego z osobna xD. Istotnie taka suma już nie jest addytywna . Mówiłem, że wygląda podejrzanie xD.

[limes123]

Kazdemu zbiorowi przypisujemy wektor w_i (i=1,...,n+1), ktory na i-tym miejscu ma 1 jesli zawiera i-ty element i 0 w przeciwnym wypadku. Wektorow jest n+1, czyli \(\displaystyle{ \sum_{i=1}^{n+1}c_iw_i=0}\) dla pewnych ci wymiernych. Teraz przerzucamy na prawa strone te wi ktore maja ci ujemne, dodatnie zostaja po lewej stronie. Latwo sie przekonac, ze indeksy po prawej i po lewej stronie mozna wziac za I, J.