Kombinatoryka Helena Paździoch owa: Uzasadnij że grupa 101 posłów w której żaden nie wstrzymuje się od głosu może przegłosować zwykła ustawę na 2¹⁰⁰ sposobów

xyz: Każdy poseł ma dwie możliwości: − być za − być przeciw zatem każda osoba ma dwie możliwości osób jest 101, zatem mamy 2 * 2 * 2 * ... * 2 <−− czyli 101 mnożeń dwójek, czyli 2¹⁰¹

Helena Paździoch owa: Ale to ma być 2¹⁰⁰ i trzeba zastosować wzór dwumianowy Newtona tylko nie wiem dlaczego właśnie ma być 2¹⁰⁰

PW: Wyjaśnij sobie, co to znaczy "przegłosować zwykłą ustawę".

Helena Paździoch owa: Mi się też na początku zdawalo że albo ''za" albo "przeciw" i powinno wyjść rzeczywiście 2¹⁰¹ ale moze autor miał na myśli tylko 1 opcie i trzeba więc otrzymany wynik podzielić na 2

PW: Ile głosów "za" potrzeba, żeby przegłosować zwykłą ustawę?

Helena Paździochowa:

	101 0
najwyraźniej tak chociaż nie wiem ale jest do tego zadania wskazówka że		+

	101 1		101 2		101 50		101 51		101 101
		+		+...+		+		+...+		i trzeba zastosować wzor

	n k		n n−k
dwumianowy Newtona i zauważyć że		=		i ja też uważam że powinno wyjść 2101

ale oni twierdzą że 2¹⁰⁰ czyli trzeba by było podzielić przez 2 tylko dlaczego?

Pytający:

	101 k		101 101−k
∑k=51101(		)=∑k=51101(		)=

	1		101 k		101 101−k
=		(∑k=51101(		)+∑k=51101(		))=
	2

	1		101 k		1
=		∑k=0101(		)=		*2101=2100
	2				2

Odpowiedz sobie na pytanie zadane przez PW, może coś zaświta Matematyczko.

PW: Składniki tej sumy o numerach 0, 1, 2, ..., 50 nie są nam potrzebne (to jest liczba wyników głosowań niekorzystnych ("za" głosował o0, 1, 2, 3,..., 50 posłów). Interesuje nas suma

	101 51		101 51		101 101
		+		+...+		,

czyli liczba głosowań, w których "za" było 51, 52, 53,..., 101 posłów. Słuszne spostrzeżenie, że składniki jednakowo odległe od początku i od końca są jednakowe (jest ich po 51) pozwala stwierdzić, że (*) (1+1)¹⁰¹=2S, gdzie S jest szukaną liczbą wyników głosowań przegłosowujących ustawę. Mamy więc 2¹⁰¹=2S,

	2101
S=		.
	2

Kluczowe dla rozwiązania jest spostrzeżenie (*).

PW: O, zanim udłubałem swoje rozwiazanie, to Pytający już rozwiązał. Musisz przyznać, Heleno, że rozwiązanie nie było tak oczywiste, jak się na początku wydawało.

polo: @PW Czy mógłby pan jakoś bardziej rozpisać skąd się bierze te (1+1)¹⁰¹=2S?

b.: W pierwszym rozwiązaniu została policzona liczba wszystkich możliwych głosowań, i z tej liczby połowa pozwala przegłosować ustawę, a połowa nie: ze względu na symetrię jednych i drugich sytuacji jest tyle samo. (Dokładniej, odwzorowanie które zamienia głosy na przeciwne jest bijekcją pomiędzy zbiorem wyników, w których ustawa przechodzi, a zbiorem wyników, w których ustawa przepada).

Mila: Np. dla n=5 mamy: Większość dla n≥3

	5 0		5 1		5 2		5 3		5 4		5 5
(1+1)5=		*1+		+		+		+		+		=

	5 5		5 4		5 3		5 3		5 4		5 5
=		+		+		+		+		+		=S+S=2S

32=2⁵ 2⁵=2*S S=2⁴

PW: W zadaniu mamy zsumować kolejne współczynniki Newtona, więc powinno pojawić się skojarzenie:

	101 0		101 1		101 2		101 50
(1+1)101=		+		+		+...+		+

	101 51		101 52		101 101
+		+		+...+

− to wzór na potęgę sumy (a+b)ⁿ, w którym a=b=1 i n=107, dający sumę wszystkich współczynników postaci

	101 k
		, k=0, 1,..., 101.

W pierwszym wierszu jest suma wszystkich możliwych głosowań "przeciw", w drugim − suma liczby wszystkich głosowań "za". Helena o 15:33 wskazała znaną zależność między współczynnikami, którą określiłem słownie: "składniki jednakowo odległe od początku i od końca są jednakowe", a więc sumy w pierwszym i drugim wierszu dają to samo, S+S=2S. Jeszcze raz: Interesująca nas suma S jest w drugim wierszu, ale suma w pierwszym wierszu jest taka sama, stąd (1+1)¹⁰¹=2S.

PW: Przepraszam, b i Mila, nie widziałem Waszych wskazówek, pisanie zajmuje mi dużo czasu

Mila: Pozdrawiam PW Ja z kolei myślałam, że już zniknąłeś z forum.

Eta:

F_P_W: Hej Eta!

PW:

F_P_W: