Problem z silnią

[Ania221]

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ć.

[Marian517]

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}}}\)

[Ania221]

No tak...a jak to zrobić na poziomie liceum? i raczej na podstawowym?

[Premislav]

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ę).

[Ania221]

OK...
A jak można udowodnić tę pierwszą tożsamość? Tez na poziomie liceum (niekoniecznie podstawowym )

[Premislav]

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.

[Marian517]

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}}\)

[Premislav]

Mam dość, nie mów mi nic, pozwól żyć, pozwól mi byyć.