szukanie zaawansowane
 [ Posty: 8 ] 
Autor Wiadomość
Kobieta Offline
PostNapisane: 7 gru 2017, o 13:46 
Użytkownik

Posty: 1959
Lokalizacja: Warszawa
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 2^{100} sposobów

Zaczęłam tak
\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ć.
Góra
Mężczyzna Offline
PostNapisane: 7 gru 2017, o 14:22 
Użytkownik

Posty: 47
Lokalizacja: Imielin
Może większość zwykła to nie jest tylko stosunek głosów 51:50.
Wypadałoby pewnie przeliczyć sumę wszystkich innych możliwości tj.
{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:
\sum_{k=0}^{n}  {n \choose k} = 2^{n}
oraz
{n \choose k} =  {n \choose {n-k}}
Góra
Kobieta Offline
PostNapisane: 7 gru 2017, o 15:12 
Użytkownik

Posty: 1959
Lokalizacja: Warszawa
No tak...a jak to zrobić na poziomie liceum? i raczej na podstawowym?
Góra
Mężczyzna Offline
PostNapisane: 7 gru 2017, o 15:25 
Użytkownik

Posty: 12616
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ę).
Góra
Kobieta Offline
PostNapisane: 7 gru 2017, o 15:28 
Użytkownik

Posty: 1959
Lokalizacja: Warszawa
OK...
A jak można udowodnić tę pierwszą tożsamość? Tez na poziomie liceum (niekoniecznie podstawowym :) )
Góra
Mężczyzna Offline
PostNapisane: 7 gru 2017, o 17:07 
Użytkownik

Posty: 12616
1. Właśnie ze wzoru dwumianowego Newtona:
\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 a=b=1.

2. Przez interpretację kombinatoryczną: zliczasz podzbiory zbioru o n elementach. Z jednej strony taki podzbiór możesz utworzyć na 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 n elementów). Z drugiej strony wybierasz k spośród n elementów zbioru na {n \choose k} sposobów. Masz więc: {n \choose 0}=1 zbiorów pustych, {n \choose 1}=n zbiorów jednoelementowych, {n \choose 2} zbiorów dwuelementowych itd.
Czyli łącznie wszystkich podzbiorów jest {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.
Góra
Mężczyzna Offline
PostNapisane: 8 gru 2017, o 01:22 
Użytkownik

Posty: 47
Lokalizacja: Imielin
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 2^{101}, a stąd wynik 2^{100}
Góra
Mężczyzna Offline
PostNapisane: 8 gru 2017, o 03:20 
Użytkownik

Posty: 12616
Mam dość, nie mów mi nic, pozwól żyć, pozwól mi byyć.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 8 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 problem z silnią  je?op  2
 Problem z silnią - zadanie 4  Merol93  3
 Problem z silnią - zadanie 5  Thuddy  7
 problem z silnia - zadanie 3  17inferno  2
 Problem z silnią - zadanie 2  trzebiec  4
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl