Dirichlet, zasada włączeń i wyłączeń

[anielkasa]

Prosiłabym o pomoc z tymi zadaniami. Siedzę nad nimi już jakiś czas i nic nie mogę wymyślić.

1. Danych jest \(\displaystyle{ 10}\) odcinków, których długości są większe niż \(\displaystyle{ 1}\) i mniejsze niż \(\displaystyle{ 55}\). Udowodnij, że wśród nich istnieją takie trzy, że da się z nich zbudować trójkąt.

2. Niech A będzie podzbiorem zbioru \(\displaystyle{ \{1,2..,149,150\}}\) złożonym z \(\displaystyle{ 25}\) liczb. Wykaż, że istnieją dwie take rozłączne pary elementów zbioru \(\displaystyle{ A}\), mające takie same sumy.
//Tutaj mniej-więcej wiem jak zrobić tylko mam problem z ilością par. W odpowiedziach jest, że jest \(\displaystyle{ 300}\) takich par, ale skąd to się wzięło?

3. Udowodnij, że w grupie \(\displaystyle{ 10}\) osób w wieku od \(\displaystyle{ 1}\) do \(\displaystyle{ 60}\) lat istnieją dwie rozłączne podgrupy o takiej samej sumie wieku.

4. Dane są liczby \(\displaystyle{ a_{1} , a_{2} ,..., a_{11}}\). Wykaż że taki istnieje niezerowy ciąg \(\displaystyle{ x_{1} , x_{2} ,..., x_{11}}\) o wyrazach ze zbioru \(\displaystyle{ \{-1,0,1\}}\), że liczba \(\displaystyle{ a_{1} \cdot x_{1} + a_{2} \cdot x_{2} +...+ a_{11} \cdot x_{11}}\) jest równa \(\displaystyle{ 0 \mod 2016}\).

5. Ile jest permutacji słowa KANKAN takich, że żadne dwie identyczne litery nie stoją obok siebie.
//Myślałam, że rozwiązanie to \(\displaystyle{ \frac{6!-3 \cdot 5!+3 \cdot 4!-3!}{2! \cdot 2! \cdot 2!}}\)
Bo \(\displaystyle{ 6!}\) to wszystkie możliwości. Potem łączymy dwie takie same litery w pare i wtedy permutujemy \(\displaystyle{ 5}\) elementów (a takich możliwości jest \(\displaystyle{ 3}\)). Itd. korzystając z zasady włączeń i wyłączeń. A na koniec dzielimy to przez \(\displaystyle{ 2! \cdot 2! \cdot 2!}\) bo dwie litery A nie są rozróżnialne. Gdzie jest błąd w moim rozumowaniu?

6. Ile jest liczb 4-cyfrowych, które można utworzyć z liczb \(\displaystyle{ 3,4,5,6,7}\) mniejszych niż \(\displaystyle{ 5000}\).
//\(\displaystyle{ 3 \cdot 5 \cdot 5 \cdot 5}\) (bo pierwszą liczbe musimy wybrać ze zbioru \(\displaystyle{ 5,6,7}\) a reszte dowolnie). Czy dobrze myśle?

Będę BARDZO, ale to bardzo wdzięczna za pomoc w tych zadaniach. Za niedługo mam egzamin a tak strasznie tego nie ogarniam

[arek1357]

W piątym będzie:

\(\displaystyle{ \frac{6!}{2! \cdot 2! \cdot 2!}-3 \cdot \frac{5!}{2! \cdot 2! \cdot 2! \cdot 1!}+3 \cdot \frac{4!}{2! \cdot 1! \cdot 1!}-3!=30}\)

[anielkasa]

Faktycznie, głupi błąd zrobiłam. xd Dzięki
Ktoś pomógłby z resztą?

[arek1357]

W odpowiedziach jest, że jest 300 takich par, ale skąd to się wzięło?

\(\displaystyle{ {25 \choose 2}=300}\)

[anielkasa]

W pierwszym podziel sobie na przedziały(szuflady):

\(\displaystyle{ (1-11)}\)

\(\displaystyle{ <11-21)}\)

\(\displaystyle{ <21-31)}\)

\(\displaystyle{ <31-41)}\)

\(\displaystyle{ <41-51)}\)

\(\displaystyle{ <51-55)}\)

I teraz zauważ, że pozostałe boki muszą wpadać to tych szuflad...

Nie za bardzo wiem co mam z tym teraz zrobić. :/

W odpowiedziach jest, że jest 300 takich par, ale skąd to się wzięło?

\(\displaystyle{ {25 \choose 2}=300}\)

Aha, czyli po prostu wyliczamy ilość par a nie ilość par par, tak?

[Premislav]

Zadanie trzecie:
możliwych sum lat (może to niegramatyczne, ale trudno) jest nie więcej niż \(\displaystyle{ 600}\), gdyż taka suma musi być równa co najmniej \(\displaystyle{ 1}\), a nie może przekraczać sumy wszystkich elementów (maksymalnie \(\displaystyle{ 60\cdot 10}\), gdyż jest dziesięć osób i żadna nie starsza niż \(\displaystyle{ 60}\) lat).
Natomiast na ile sposobów możemy wybrać dwie rozłączne, niepuste grupy spośród dziesięciu osób?
Dużo więcej, nawet gdybyśmy uparli się, by podzielić grupę \(\displaystyle{ 10}\) osób na dwie rozłączne niepuste podgrupy, to wyjdzie tego \(\displaystyle{ 2^{10}-1=1023}\) (wybieramy niepusty podzbiór, jego dopełnienie to ta druga grupa).

Zadanie czwarte jest jakieś trochę trudne, albo czegoś nie zauważyłem.

[arek1357]

Każdy z pozostałych czterech odcinków musi się znaleźć w którejś ze szuflad...


W zadaniu czwartym jak weźmiemy jakieś \(\displaystyle{ a_{i}}\) - niewymierne i niewspółmierne to raczej nie styknie...

bo pierwszą liczbe musimy wybrać ze zbioru 5,6,7 a reszte dowolnie

Chyba na odwrót...

[anielkasa]

Każdy z pozostałych czterech odcinków musi się znaleźć w którejś ze szuflad..

Czyli istnieje taka szuflada w której będą minimum 2 odcinki. Tylko nie rozumiem za bardzo co to nam daje. :/

Chyba na odwrót...

Faktycznie, mój błąd.

[arek1357]

Jeżeli natomiast w zadaniu czwartym założymy, że liczby są całkowite to możemy je zapisać jako:

\(\displaystyle{ a_{i}=2016s_{i}+r_{i}, 0\le r_{i} \le 2015}\)

I teraz możemy sobie działaś w zbiorze reszt:

\(\displaystyle{ r_{1},r_{2},r_{3},...,r_{11}}\)

I nie widzę tu na razie , żeby zawsze suma tych reszt lub przeciwne do nich zawsze się zerowało...

[a4karo]

4 Ciągów zero - jedynkowych jest \(\displaystyle{ 2^{11}>2016}\),wiec istnieją dwa różne ciągi o tych samych resztach. Co z tego wynika?

[kerajs]

1)
Przyjąłbym 8 szuflad:
\(\displaystyle{ (1,2) \ , \ <2,3) \ , \ <3,5) \ , \ <5,8) \ , \ <8,13) \ , \ <13,21) \ , \ <21,34) \ , \ <34,55)}\)
trójkąt można zbudować z:
a) trzech odcinków z tej samej szuflady.
b) dwóch odcinków z jednej szuflady i odcinka z drugiej, leżącej najbliżej lewej strony pierwszej.
Niezależnie od rozkładu 10 odcinków w szufladach zawsze przynajmniej jedna z powyższych sytuacji zajdzie.

[arek1357]

W drugim masz największą sumę 299, a najmniejszą 3, natomiast w zbiorze 25 elementowym masz możliwe 300 par i co z tego wynika?...