kombinatoryka, głosowanie

[prawyakapit]

10. W wyborach startuje 4 kandydatów, a wyborców jest 100. Każdy wyborca oddaje głos na
jednego kandydata. Zakładamy, że głosowanie jest jawne, to znaczy ważne jest dla nas, kto
na kogo głosuje. Niech N oznacza liczb¦ takich wyników głosowania, w których na przynaj-
mniej jednego kandydata nikt nie głosował. Czy poniższy sposób wyznaczenia wartości N jest
poprawny?
Rozwiązanie: Przez dopełnienie. Od wszystkich możliwych wyników \(\displaystyle{ (4^{100}}\)) odejmujemy te,
w których każdy kandydat dostał jakiś głos. Wybieramy 4 wyborców (\(\displaystyle{ {100\choose 4}}\)
sposobów), ich głosy przydzielamy dowolnie czterem kandydatom (4! możliwości), a pozostałych 96 wyborców głosuje dowolnie (496 sposobów). Zatem

\(\displaystyle{ 4^{100} -{100\choose 4} \cdot 4! \cdot 4^{96}}\)


moje przemyślenia:
Według mnie to rozwiązanie nie jest poprawne ja bym to zrobiła w następujący sposób:
najpierw 4 przypadki gdy zagłosowano tylko na jednego kandydata potem 6 przypadków gdy zagłosowano tylko na 2 kandydatów potem 4 przypadki gdy zaglosowano tylko na 3 kandydatów
więc:
\(\displaystyle{ 4+ 6(2^{100}-1) + 4(3^{100}-3)}\)


czy to jest dobrze ?

[mat_61]

Pierwszy sposób faktycznie jest zły. Po prostu takie same głosowanie liczone są jako różne.

Oznaczmy kandydatów przez A, B, C i D. Wybieramy 4 wyborców np. 1, 3, 7, 12 i przydzielamy ich do kandydatów:

A-1, B-3, C-7, D-12

Następnie na kandydata A głosuje jeszcze wyborca 37.

Możemy jednak wybrać czterech wyborców tak: 37, 3, 7, 12 i przydzielić ich do kandydatów:

A-37, B-3, C-7, D-12

Następnie na kandydata A głosuje jeszcze wyborca 1 a pozostali tak jak wcześniej. Widać, że wynik głosowania jest identyczny choć liczony jest jako różny.

W Twoim sposobie pomysł jest dobry ale masz błąd w obliczeniach, np.:

6 przypadków gdy zagłosowano tylko na 2 kandydatów

Faktycznie mamy 6 możliwości wybrania dwóch kandydatów z czterech. Wszystkich możliwych przyporządkowań dla tych dwóch kandydatów mamy \(\displaystyle{ 2^{100}}\) ale musimy oczywiście odjąć przypadki gdy głosy zostały oddane tylko na jednego z dwóch wybranych kandydatów a takie przypadki są dwa a nie jeden (jeżeli np. wybraliśmy kandydatów B i D, to odejmujemy te głosowania gdy wszystkie głosy otrzymał B lub wszystkie głosy otrzymał D)

Analogicznie należy poprawić przypadki dla trzech wybranych kandydatów (należy odjąć te przypadki gdy głosy otrzymał tylko jeden kandydat lub tylko dwóch kandydatów, a takich przypadków jest dużo więcej niż trzy)

[prawyakapit]

czyli dla 3 kandydatów takich przypadków trzeba odjąć 6 przypadków ?

[mat_61]

Nie 6 ale duuuużo więcej.

Zauważ, że po wybraniu 3 kandydatów, np. A, B i D musimy odjąć te przypadki gdy wszystkie głosy oddane są na jednego z nich (czyli oczywiście trzy) i te przypadki gdy wszystkie głosy są oddane na dwóch z nich. Tych dwóch kandydatów (z trzech) możemy wybrać na trzy sposoby. Powiedzmy, że będą to kandydaci A i D.

Teraz odejmujemy wszystkie warianty głosów oddanych na tych dwóch kandydatów. Ile jest takich wariantów? Policzyłaś to już wcześniej i jest ich:

\(\displaystyle{ 2^{100}-2}\)

Rozumiesz dlaczego?

[prawyakapit]

no właśnie chyba nie rozumiem bo:
np. mamy trójkę A , B, D(głosy oddano na kandydata A , b i D)
muszę od tego odjąc trzy możliwości gdy głosy oddano tylko na A , tylko na b i tylko na C
potem musze odjąć możliwości gdy oddano tylko na A i B, tylko na A i c i tylko na B i C
nie wiem jakie możliwości sa jeszcze.

[mat_61]

No właśnie.

Napisałaś tak: potem musze odjąć możliwości gdy oddano głosy tylko na A i B

Ile może być takich głosowań, że stu wyborców odda głosy tylko na kandydatów A i B ?

Z pewnością nie są to tylko dwa warianty. Jak mogą np. wyglądać takie głosowania (liczby oznaczają kolejnych wyborców):

1-A 2-A 3-B 4-A 5-B 6-B 7-B 8-A .... 99-A 100-B

1-A 2-A 3-B 4-B 5-B 6-B 7-B 8-A .... 99-A 100-B

1-A 2-B 3-B 4-A 5-B 6-B 7-B 8-A .... 99-A 100-B

1-B 2-A 3-B 4-A 5-B 6-B 7-B 8-A .... 99-A 100-A

itd. itd.

Widzisz chyba, że takich wariantów głosowań w których będą głosy tylko na A i B mogę wypisać \(\displaystyle{ 2^{100}}\) ponieważ masz sto kolejnych pozycji (stu wyborców) i na każdej z nich masz do wyboru 2 możliwości głosowania (A lub B).

Oczywiście wśród nich będzie jeden wariant gdy będą same głosy A i jeden wariant gdy będą same głosy B. Z tego wynika, że takich wariantów głosowań w których zostaną oddane głosy na A i B (czyli musi być co najmniej jeden głos na każdego z kandydatów) mamy:

\(\displaystyle{ 2^{100}-2}\)

Czy teraz jest to jasne?

[prawyakapit]

ok już rozumiem, czyli przy wariancie 3 kadydatów od \(\displaystyle{ 3^{100}}\) musze odjąć \(\displaystyle{ 2^{100}+2}\) ?

[mat_61]

Może to użyty przez Ciebie skrót myślowy, ale dla 3 wybranych kandydatów od wszystkich możliwości (liczonych jako wariacje z powtórzeniami), czyli \(\displaystyle{ 3^{100}}\) musisz odjąć te warianty gdzie głosy będą na jednego kandydata, czyli \(\displaystyle{ 3}\) oraz te warianty gdzie głosy będą oddane na dwóch (z tych trzech kandydatów), czyli \(\displaystyle{ 3\left( 2^{100}-2\right)}\). Wszystkich wariantów będzie więc:

\(\displaystyle{ 3^{100}-3-3\left( 2^{100}-2\right)=3^{100}-3 \cdot 2^{100}+3}\)

[prawyakapit]

ok dzięki ; )