[Zasada podwójnego przeliczania] Uzasadnienie mocy zbioru

[pelas_91]

3. Niech A będzie pewną rodziną 100-elementowych podzbiorów zbioru \(\displaystyle{ {1,2,3,...,1000}}\). Wykorzystując technikę podwójnego przeliczania pokaż, że jeśli każda liczba \(\displaystyle{ k \in {1,2,3,...,1000}}\) należy do przynajmniej 10 zbiorów z A, to w A jest co najmniej 100 zbiorów.

Proszę o wskazówkę

[norwimaj]

Niech \(\displaystyle{ \mathcal{A}=\{A_1,A_2,\ldots,A_n\}}\) będzie \(\displaystyle{ n}\)-elementową rodziną zbiorów. Ile jest takich par \(\displaystyle{ (k,A_i)}\), że \(\displaystyle{ k\in A_i}\)?