Problem z silnią
-
- Użytkownik
- Posty: 1923
- Rejestracja: 30 lis 2013, o 13:26
- Płeć: Kobieta
- Lokalizacja: Warszawa
- Podziękował: 22 razy
- Pomógł: 326 razy
Problem z silnią
Takie zadanko
Wykaż, że 101 posłów z których żaden nie wstrzymuje sie od głosu, może przegłosować ustawię większością zwyklą na \(\displaystyle{ 2^{100}}\) sposobów
Zaczęłam tak
\(\displaystyle{ \frac{101!}{51!50!} = \frac{(2 \cdot 50+1)!}{(50+1)!50!}= \frac{(2 \cdot {50})!(2 \cdot 50+1)}{50!(50+1)50!}= \frac{2^{50} \cdot 50! \cdot 101}{50! \cdot 51 \cdot 50!}}\) no i tu utknęlam...te jedne silnie sie skróca, ale co z resztą?
Tak mi sie zdaje, że żle te silnie rozpisałam...ale nie wiem, jak to zrobić.
Wykaż, że 101 posłów z których żaden nie wstrzymuje sie od głosu, może przegłosować ustawię większością zwyklą na \(\displaystyle{ 2^{100}}\) sposobów
Zaczęłam tak
\(\displaystyle{ \frac{101!}{51!50!} = \frac{(2 \cdot 50+1)!}{(50+1)!50!}= \frac{(2 \cdot {50})!(2 \cdot 50+1)}{50!(50+1)50!}= \frac{2^{50} \cdot 50! \cdot 101}{50! \cdot 51 \cdot 50!}}\) no i tu utknęlam...te jedne silnie sie skróca, ale co z resztą?
Tak mi sie zdaje, że żle te silnie rozpisałam...ale nie wiem, jak to zrobić.
-
- Użytkownik
- Posty: 47
- Rejestracja: 20 lip 2010, o 16:32
- Płeć: Mężczyzna
- Lokalizacja: Imielin
- Pomógł: 7 razy
Problem z silnią
Może większość zwykła to nie jest tylko stosunek głosów \(\displaystyle{ 51:50}\).
Wypadałoby pewnie przeliczyć sumę wszystkich innych możliwości tj.
\(\displaystyle{ {101 \choose 51} + {101 \choose 52} + \ldots + {101 \choose 101}}\)
A to może na przykład wynikać z dwóch prostych tożsamości:
\(\displaystyle{ \sum_{k=0}^{n} {n \choose k} = 2^{n}}\)
oraz
\(\displaystyle{ {n \choose k} = {n \choose {n-k}}}\)
Wypadałoby pewnie przeliczyć sumę wszystkich innych możliwości tj.
\(\displaystyle{ {101 \choose 51} + {101 \choose 52} + \ldots + {101 \choose 101}}\)
A to może na przykład wynikać z dwóch prostych tożsamości:
\(\displaystyle{ \sum_{k=0}^{n} {n \choose k} = 2^{n}}\)
oraz
\(\displaystyle{ {n \choose k} = {n \choose {n-k}}}\)
- Premislav
- Użytkownik
- Posty: 15687
- Rejestracja: 17 sie 2012, o 13:12
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 196 razy
- Pomógł: 5220 razy
Re: Problem z silnią
Na poziomie podstawowym nie ma takich zadań, bo jest on przeznaczony dla debili (a nie powinien być, debile nie potrzebują trygonometrii, a myśleć i tak się nie nauczą) oraz dla ludzi niezainteresowanych matematyką w żadnym szerszym zakresie (im też trygonometria czy logarytmy się nie przydadzą, co innego rozwój myślenia, ale nie jestem pewien, czy mielenie schematycznych zadań temu celowi służy). A wzór dwumianowy Newtona miałem w liceum na rozszerzeniu, z tego co wiem, od tego czasu program uległ (jak by nie było) poszerzeniu, a nie obcięciu.
Rozwiązanie zaproponowane przez użytkownika Marian517 to najlepsze, co dostrzegam (nie znaczy to, że prostszego nie ma, w każdym razie ja nie widzę).
Rozwiązanie zaproponowane przez użytkownika Marian517 to najlepsze, co dostrzegam (nie znaczy to, że prostszego nie ma, w każdym razie ja nie widzę).
- Premislav
- Użytkownik
- Posty: 15687
- Rejestracja: 17 sie 2012, o 13:12
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 196 razy
- Pomógł: 5220 razy
Re: Problem z silnią
1. Właśnie ze wzoru dwumianowego Newtona:
\(\displaystyle{ \sum_{k=0}^{n}{n \choose k}a^{n-k} b^{k}={n \choose 0}a^nb^0+{n \choose 1}a^{n-1}b^{1}+\ldots+{n \choose n}a^ 0 b^n=(a+b)^n}\)
dla \(\displaystyle{ a=b=1}\).
2. Przez interpretację kombinatoryczną: zliczasz podzbiory zbioru o \(\displaystyle{ n}\) elementach. Z jednej strony taki podzbiór możesz utworzyć na \(\displaystyle{ 2^n}\) sposobów, bo dla każdego elementu decydujesz, czy wejdzie on w skład podzbioru, czy nie (po dwie możliwości, a ogólnie masz \(\displaystyle{ n}\) elementów). Z drugiej strony wybierasz \(\displaystyle{ k}\) spośród \(\displaystyle{ n}\) elementów zbioru na \(\displaystyle{ {n \choose k}}\) sposobów. Masz więc: \(\displaystyle{ {n \choose 0}=1}\) zbiorów pustych, \(\displaystyle{ {n \choose 1}=n}\) zbiorów jednoelementowych, \(\displaystyle{ {n \choose 2}}\) zbiorów dwuelementowych itd.
Czyli łącznie wszystkich podzbiorów jest \(\displaystyle{ {n \choose 0}+{n \choose 1}+\ldots+{n\choose n}}\).
3. Można indukcyjnie, ale akurat co do indukcji, to nie wiem, czy jest teraz w programie (ja ją miałem w drugiej klasie liceum, ale nauczycielka nie trzymała się bardzo rygorystycznie podstawy programowej); w każdym razie w podręczniku do szkoły średniej to występowało - zakres rozszerzony oczywiście.
\(\displaystyle{ \sum_{k=0}^{n}{n \choose k}a^{n-k} b^{k}={n \choose 0}a^nb^0+{n \choose 1}a^{n-1}b^{1}+\ldots+{n \choose n}a^ 0 b^n=(a+b)^n}\)
dla \(\displaystyle{ a=b=1}\).
2. Przez interpretację kombinatoryczną: zliczasz podzbiory zbioru o \(\displaystyle{ n}\) elementach. Z jednej strony taki podzbiór możesz utworzyć na \(\displaystyle{ 2^n}\) sposobów, bo dla każdego elementu decydujesz, czy wejdzie on w skład podzbioru, czy nie (po dwie możliwości, a ogólnie masz \(\displaystyle{ n}\) elementów). Z drugiej strony wybierasz \(\displaystyle{ k}\) spośród \(\displaystyle{ n}\) elementów zbioru na \(\displaystyle{ {n \choose k}}\) sposobów. Masz więc: \(\displaystyle{ {n \choose 0}=1}\) zbiorów pustych, \(\displaystyle{ {n \choose 1}=n}\) zbiorów jednoelementowych, \(\displaystyle{ {n \choose 2}}\) zbiorów dwuelementowych itd.
Czyli łącznie wszystkich podzbiorów jest \(\displaystyle{ {n \choose 0}+{n \choose 1}+\ldots+{n\choose n}}\).
3. Można indukcyjnie, ale akurat co do indukcji, to nie wiem, czy jest teraz w programie (ja ją miałem w drugiej klasie liceum, ale nauczycielka nie trzymała się bardzo rygorystycznie podstawy programowej); w każdym razie w podręczniku do szkoły średniej to występowało - zakres rozszerzony oczywiście.
-
- Użytkownik
- Posty: 47
- Rejestracja: 20 lip 2010, o 16:32
- Płeć: Mężczyzna
- Lokalizacja: Imielin
- Pomógł: 7 razy
Problem z silnią
Właściwie to mam może sprytniejsze rozwiązanie.
Wystarczy zauważyć, że tak naprawdę na tyle samo sposobów można przegłosować ustawę jak i ją odrzucić, ponieważ z każdym możliwym głosowaniem możemy związać głosowanie, w którym wszyscy posłowie zagłosowali przeciwnie.
Wszystkich możliwości jest \(\displaystyle{ 2^{101}}\), a stąd wynik \(\displaystyle{ 2^{100}}\)
Wystarczy zauważyć, że tak naprawdę na tyle samo sposobów można przegłosować ustawę jak i ją odrzucić, ponieważ z każdym możliwym głosowaniem możemy związać głosowanie, w którym wszyscy posłowie zagłosowali przeciwnie.
Wszystkich możliwości jest \(\displaystyle{ 2^{101}}\), a stąd wynik \(\displaystyle{ 2^{100}}\)