Zadania z kółek matematycznych lub obozów przygotowujących do OM. Problemy z minionych olimpiad i konkursów matematycznych.
Regulamin forum
Wszystkie tematy znajdujące się w tym dziale powinny być tagowane tj. posiadać przedrostek postaci [Nierówności], [Planimetria], itp.. Temat może posiadać wiele różnych tagów. Nazwa tematu nie może składać się z samych tagów.
Udowodnij kombinatorycznie: \(\displaystyle{ \sum_{k=0}^{n} {n \choose k} (m-1)^{n-k} = m^{n} }\) \(\displaystyle{ \sum_{k=0}^{n} k(n+1-k)= {n+2 \choose 3} }\)
Chodzi tu o określenie lewej i prawej strony jako historii
Złapaliśmy \(\displaystyle{ n}\) antyszczepionkowców i chcemy ich zamknąć w \(\displaystyle{ m}\) celach, przy czym zakładamy, że cele są na tyle obszerne, by w każdej zmieścili się w razie potrzeby wszyscy schwytani denialiści rozumu.
Z jednej strony możemy więźniów rozmieścić na \(\displaystyle{ m^{n}}\) sposobów, zwykłe wariacje z powtórzeniami (możemy też spojrzeć na to tak, że dla każdego z \(\displaystyle{ n}\) więźniów mamy do wyboru \(\displaystyle{ m}\) lokalizacji).
Z drugiej strony wyróżnijmy pewną celę, na przykład tę, w której najbardziej wieje sandałem z masłem. W tej celi znajdzie się \(\displaystyle{ k}\) antyszczepionkowców, \(\displaystyle{ 0\le k\le n}\), których wybieramy na \(\displaystyle{ {n\choose k}}\) sposobów. Następnie pozostałych \(\displaystyle{ n-k}\) więźniów rozmieszczamy w pozostałych \(\displaystyle{ m-1}\) celach na \(\displaystyle{ (m-1)^{n-k}}\) sposobów (znów wariacje z powtórzeniami).
Stąd się bierze suma po lewej stronie.
2)
Ukryta treść:
Mamy \(\displaystyle{ n+2}\) strony encyklopedii i chcemy przeczytać dokładnie \(\displaystyle{ 3}\), bo po prostu mamy taki kaprys (przypominam sobie, jak czytałem encyklopedię, zamiast bawić się z rówieśnikami, bo nikt mnie nie lubił).
Z jednej strony oczywiście mamy \(\displaystyle{ {n+2\choose 3}}\) możliwości wyboru trzech stron spośród \(\displaystyle{ n+2}\).
Z drugiej strony spójrzmy na to tak:
ustalmy środkową spośród trzech stron, które przeczytamy. Będzie ona miała numer \(\displaystyle{ k+1, \ 0\le k\le n+1}\).
Przed nią jest \(\displaystyle{ k}\) stron, a za nią \(\displaystyle{ n+2-(k+1)=n-k+1}\) stron, czyli poprzedzającą stronę do przeczytania wybieramy na \(\displaystyle{ k}\) sposobów, a ostatnią stronę do przeczytania – na \(\displaystyle{ n+1-k}\) sposobów. Łącznie mamy wtedy \(\displaystyle{ k(n+1-k)}\) możliwości wyboru trzech stron, przy ustalonej środkowej.