Alegeri libere în Demokratistan

Question

Demokratistan e un ținut imaginar unde au drept de vot 20 de milioane de oameni.

Președintele în funcție, susținut doar de un procent din cei 20 de milioane de votanți, vrea să fie reales în mod democratic. O democrație originală, unde sistemul electoral ar funcționa astfel:

Toți votanții sunt împărțiți în n₁ grupuri egale numeric. Fiecare dintre aceste grupuri pot fi apoi împărțite în n₂ subgrupuri mai mici și egale numeric (n₂ același pentru toate grupurile).

Fiecare subgrup poate fi apoi împărțit în n₃ sub-subgrupuri egale ș.a.m.d.

În cadrul fiecărui subgrup de nivel i este ales un reprezentant prin vot democratic, câștigat cu majoritate simplă (jumătate plus 1, iar în caz de egalitate câștigă coaliția care i se împotrivește președintelui în funcție). Acest reprezentant va merge mai departe în alegeri la nivelul i-1.
 

Poate actualul președinte șă își grupeze cumva suporterii cu drept de vot astfel încât să câștige alegerile?

Comments

E clar ca daca are destui suporteri poate castiga.

Banuiesc ca intrebarea ar fi daca poate castiga alegerile cu mai putin de 50% suporteri. Ori poate expresia "susținut doar de un procent" ar trebui luata ca numarul de suporteri este 1% din cei 20 milioane?

 

---

Un procent înseamnă 1%, în timp ce mărimile exprimate în procente se cheamă procentaje. Problema e că multă lume folosește prost cuvintele astea și astfel tind să devină ambigue.

---

Da. Asta e ideea. Dacă poate caștiga alegerile susținut de doar 200000 de votanți. 1% din 20 de milioane. Și, dacă da, cum anume, desigur...

---

Frumoasa problema ,evident ca acele Ni-uri sunt divizori si cred ca problema se poate generaliza.Insa nu m-am gandit serios la ea dar combina aritmetica si inegalitati.

---

Cînd eram prin liceu aveam o culegere de probleme de matematică date la olimpiadele sovietice, tradusă din rusă. Printre ele era și asta. Nu garantez că erau aceiași parametri, dar ideea era exact aceeași.

---

@zec: La ce vă referiți când vorbiți de generalizare? La înlocuirea numărului de alegători cu altă valoare?

---

Unul nu desecretizeaza arhivele KGB, altul este lenes. Amindoi au o solutie si nu au oferit-o. Pai de ce nu ?

---

am nevoie de o clarificare.Reprezentanti deja sunt in grupele anterioare, deci care e rolul reprezentantilor am nevoie de o explicati ma clara.

---

Nu prea vă înțeleg nelămurirea...

La cel mai de jos nivel, să îi spunem k, nu putem vorbi de reprezentanți. Toată populația votează. De la nivelul (k-1) în sus întrecerea electorală are loc între așa-numiții reprezentanți, cei victorioși la nivelul imediat inferior. Cei care sunt învingători la nivelul k rămân și electori la nivelul (k-1), desigur...

Answer 1

RESCRIEREA INTEGRALA A RASPUNSULUI MEU.

am avut intradevar o mica mare eroare dar ideea e cam aceeasi.

Daca impartim N in n1 grupuri fiecare a cate k1 membri  si fiecare grup se imparte la randul sau in ni grupuri cu cate ki membri ne dam seama ca

N se scrie ca produs N=n1*k1=n1*n2*k2=...=n1*n2*n3.....*ni*ki

 evident va fi ceva de genul acelui produs considerat doar ca greseala mea data trecuta a fost aceasta scriere.

Daca vrem sa castige trebuie ca jumatate plus 1 din cei ki membri sa aiba castig de cauza in jumatate plus 1 in grupele ni si asa mai departe.

Adica numarul lor trebuie sa fie cel putin acel produs si vrem sa fie de cel putin 1%.Cu cat factori sunt mai mici cu atat putem avea sansa sa gasim o eventuala solutie .

20000000=2x10^7=2^8x5^7 Sa luam efectiv grupurile n pe descompunerea in factori primi si chiar in aceasta ordine .

Adica n1=n2=..=n7=2  n8=n9=...=n14=5 si k14=5.

Evident distribuim convenabil.

adica in grupele de 5 ne trebuie 3 si in cele de 2 ambi.

Astfel numarul minim necesar ar fi 3^7x2^8=559872 >200000. si nu iese.

Cum variaza acest numar? de exemplu grupele de 2 in numar de 8 daca le fac de 4 voi avea 4^4 ceea ce implica 3^4 fata de 2^8 numar necesar de votanti.Deci o reducere si in total as avea 3^11=177147<200000 .Bingo.Deci se poate.

Comments

Scuze pentru întârzierea răspunsului. Nu sunt convins că am înțeles ideea dvs., dar ce observ e că produsul celor 7 factori, k1, k2,..., k7 este 2 milioane, nu 20 de milioane...

Later edit:
Ideea cu produsul jumatatilor plus unu din fiecare factor e ok, doar ca nu orice configuratie de 7 factori duce la un produs al jumatatilor plus 1 din acesti factori mai mic sau egal cu 1% din total. Si asta tocmai ptr. ca produsul jumatatilor plus unu din fiecare factor poate depasi cu mult produsul jumatatilor fiecarui factor. De fapt habar nu am daca exista vreo configuratie valida de 7 factori.... Aici trebuie umblat la solutie... si gata, ca deja am zis prea mult :-)

---

mi am dat seama de ieri  de greseala .Mersi:)

o sa reeditez aproape tot.

---

ok scuze de intarziere datorata lipsei de chef in special pe editarea acestui gen de problema.Am sters total raspunsul anterior si am adus altul.

---

Înțeleg lipsa de chef, dar cred că ar merita efortul unei demonstrații riguroase editată cum trebuie până la capăt :)

Adică tratat cazul 1 și trecerea de la nivelul k la nivelul k+1.

Mai am o sugestie, pentru viitor. Cred că ar fi bine ca atunci când veniți cu o soluție nouă să scrieți un alt răspuns și nu să îl editați pe cel anterior, pentru că se pierde sensul dialogurilor anterioare, cum e cazul si acum, iar aceste discuții pot fi utile celor care citesc pe aici...

Answer 2

Păi cred că ar trebui să împărțim cei 20.000.000 de alegători în trei grupuri, astfel încât vom avea 20.000.000/3=6.666.666 de alegători într-un grup (doi alegători nu s-au prezentat la vot si nu fac parte din niciun grup, nu pățesc nimic, fiindcă este un sistem democratic). Pentru ca rezultatul final sa îi fie favorabil peședintelui ce ține atât de mult la democerație, are nevoie să fie susținut de două dintre cele tri grupuri. Așadar în grupul opozant putem pune 6.666.666 de opozanți (evident). Acum luăm unul dintre celelalte grupuri (raționamentul este același pentru amândouă) și îl împărțim din nou la 3: 6.666.666/3=2.222.222. Pentru a câștiga în cadrul unui astfel de grup format din 6.666.666 este nevoie de asemenea să fie susținut de către două dintre cele două grupuri de 2.222.222, așadar grupul opozant poate fi constituit 100% din opozanți. Până la acest nivel avem 6.666.666+2.222.222+2.222.222=11.111.110 opozanți din 20.000.000 adică mai mult de 50%+1 din populația cu drept de vot și în ciuda acestui fapt, respectând repartiția alegătorilor de mai sus, președintele în funcție ar câștiga.

Impărțind din nou grupurile la 3, am ajunge la concluzia că putem grupa favorabil 11.111.110+740740+740740=12592590 opozanți și președintele tot ar câștiga. Putem face acest lucru până ajungem la grupuri formate din 3 membri.

Pentru a afla dacă este suficient un procent de susținători pentru a câștiga alegerile, voi încerca să găsesc forma matematică a soluției de mai sus (sper să confirme soluția).

Încep cu o reprezentare grafică, cu următoarea convenție: + reprezintă vot favorabil al unui individ (pe ultimul rând) sau reprezentant al grupului, respectiv - este vot negativ. În paranteză am scris raportul dintre voturile pozitive și numărul total de voturi De asemenea fiecare rând a fost rescris pe rândul următor detaliindu-se modul în care s-a facut împărțirea, până la nivel de individ.

 + (înseamnă câștigător)

++- (2/1)

++-/++-/--- (4/9)

++-/++-/---//++-/++-/---//---/---/--- (8/27)

++-/++-/---//++-/++-/---//---/---/---///++-/++-/---//++-/++-/---//---/---/---///---/---/---//---/---/---//---/---/--- (16/81)

......

++-/++-/---//++-/++-/---//---/---/---/// ..... //---/---/--- (2^n/3^n)

Se observă că rezolvând inecuația (2/3)^n<=1/100 aș putea găsi numărul minim de alegători care grupați convenabil, ar face ca rezultatul votului să fie cel așteptat. Cu ajutorul Google constat că pentru n>11,35775 inecuația este adevărată. Acum caut o putere  a lui 3 pentru a mă apropia de 20.000.000 și constat că 3^15=14.348.907 din care 2^15=32768 sunt opozanti (mult sub 1%). Pentru restul de alegători (5.651.093) voi avea la 3^14=4782969 alegători cu 16384 opozanti. Din nou rămân "pe afară" 868124, pentru care pot relua raționamentul rezultând înca 4096 opozanti pentru 531441, si tot așa.

În acest moment mă gândesc că din cei 20.000.000 se pot forma initial 6.666.666 grupuri de catre 3 persoane, cu sustinatorii distribuiti favorabil, conform modelului de mai sus, apoi din trei grupuri se poate forma un grup mai mare, și tot așa.

Însă în toate raționamentele de mai sus nu am respectat riguros condițiile problemei, de fiecare dată rămânând un rest pe care l-am ignorat (presupunând că este neglijabil), mai mult, nu am respectat condiția împărțirii în grupuri numeric egale.

Să vedem dacă este posibil acest lucru:

20.000.000=5 grupuri a câte 4.000.000 alegători. În două dintre ele punem doar opozanți, așadar voi avea 8.000.000. Restul de 12.000.000 (dar și pe cei 8.000.000) îi imparțim din nou, în grupuri formate din 4.000.000 de membri. Din nou într-unul dintre cele 3 grupuri de 4.000.000 putem așeza doar opozanți, pe care îi adăugăm celor 8.000.000, rezultând un total de 12.000.000. Apoi se pot forma grupuri de câte 800.000, și mai adăugam 3.200.000 opozanților (cate 2 grupuri de 800.000 dintr-un total de cinci, format dintr-un grup de 4.000.000), având un total de 15.200.000 de opozanți, și 4.800.000 în 6 grupuri a câte 800.000 favorabile presedintelui. Formăm din nou pe următorul nivel 6x5 grupuri a 160.000, rezultând un total de 17.760.000 opozanti la care presedintele poate câștiga și 15 grupuri a câte 160.000 favorabile actualului președinte.

"Ochiometric" constat că viteza de creștere a numărului de opozanți odată cu impărțirea în mai multe grupuri la care președintele încă mai poate câștiga nu este suficient de mare, motiv pentru care mă vo opri aici propunându-mi să revin în cazul în care voi putea găsi o soluție.

Comments

Nu am ”procesat” în detaliu întregul dvs. raționament, dar ce mi-a sărit în ochi e faptul că abordați problema top-down. În scenariul meu e nevoie de o abordare bottom-up, în sensul că alegerile încep de la grupurile cele mai mici dpdv numeric și evoluează de acolo...

De pildă, niciodată nu se va ajunge la 3 grupuri de câte 6.666.666 de alegători în abordarea bottom-up, pentru că nu vor mai fi atâția când alegerile vor ajunge la acel nivel, cel mai de sus...

Later edit:

Am citit acum atent și am văzut că abordarea top-down a fost doar un instrument de care v-ați folosit, revenind apoi la cea de jos în sus. Deci cred că ați judecat corect, doar că ar fi bine să încercați să formalizați cumva matematic ideile, pentru a putea trece, să zicem, de la nivelul 1 al demonstrației la nivelul 2 sau, mai general, de la nivelul k al demonstrației la nivelul următor, k+1...

---

ai abordat gresit ,din cauza ta am rescris raspunsul asa ca bravo pentru efort  e chiar foarte mult si sa sti ca uneori produce si efecte pozitive chiar daca ai complicat rau ideea problemei.

Answer 3

O soluție similară cu a lui zec am găsit și eu.

Împărțim n, numărul total de votanți, în n₁ grupuri de câte k₁ votanți, fiecare grup de k₁ votanți în n₂ sub-grupuri de câte k₂ votanți etc.

Ca să fim siguri că președintele câștigă, dacă în fiecare sub-grup n_i  sunt k_i votanți,   în cel puțin    dintre acele sub-grupuri vor trebui să fie distribuiți cel puțin     susținători.

Ca să fie posibil aceasta, factorizarea lui n trebuie să conțină numai numere impare, însă 20.000.000 este 2⁸ ·​5⁷ .

Putem scrie factorizarea lui n sub forma 

20.000.000=2² ·2² ·2² ·2² ·5·5·5·5·5·5·5

iar fiecare factor în parte reprezintă de fapt numărul de grupuri/sub-grupuri/votanți.

Nu este importantă ordinea în care distribuim factorii, ci doar faptul că sunt 11 factori, ce semnifică faptul că vor fi 11 grupuri/sub-grupuri/votanți.

În cele de 4, 3 vor susține președintele, iar în cele de 5, 3 vor susține președintele, astfel încât numărul lor să fie mai mare de jumătate plus 1 în grupa/sub-grupa respectivă, dar numărul total nu trebuie să depășească acel procent și într-adevăr, 3¹¹ < 2⁶ ·​5⁵ .

Cu alte cuvinte, în ultimele sub-grupuri în fiecare dintre ele sunt un anumit număr de votanți, iar jumătate plus 1 dintre ei trebuie să fie susținători.

Dar asta nu trebuie să existe în toate acele ultime sub-grupuri, ci doar în jumătate plus 1 dintre ele și tot așa.

Comments

Da. Este ok. Cu mențiunea că puteți apela la valoarea

 

pentru a nu mai face discuția par-impar.

Ce mi s-ar mai părea mie necesar, pentru a genera o soluție riguroasă dpdv matematic, ar fi să formalizăm răspunsul cumva. Iar ideea care mi se pare cel mai la îndemână e cea de inducție matematică de la un nivel cu un anumit număr de grupuri la nivelul imediat superior, cu mai puține grupuri și mai puțini votanți.

Încercați?

---

Tu vrei să arăți riguros dpdv matematic cum se generează o soluție sau toate soluțiile ?

Ca și răspuns la întrebarea ta Încercați? am prezentat mai jos ceva, încercând să arât câte soluții pot fi, dar a doua parte conține ceva greșit și va trebui să corectez.

Și am încercat să detaliez acolo ce-am făcut și ce-am gândit, dar nu puteam scrie mai mult de 8000 caractere și am scris mult mai sumar.

---

Nu. Ma refeream la a demonstra ca daca n = n₁*n₂*n₃*...*n_p atunci e suficient un numar de k₁*k₂*k₃*...*k_p = ([n₁/2]+1)*([n₂/2]+1)*([n₃/2]+1)*...*([n_p/2]+1) sustinatori (distribuiti corespunzator) pentru ca presedintele sa castige alegerile. Dupa atatea discutii si rationamente pare o chestiune de la sine inteleasa, dar ideea asta suporta totusi o demonstratie ...

Gasirea descompunerii potrivite in factori e pasul urmator, si nu cred, de fapt nu stiu daca e posibil sa fie stabilita riguros, prin calcul matematic. E mai mult o chestiune de trial and error din cate am putut sa-mi dau seama...

---

Înclin din ce în ce mai mult să fiu de acord cu tine.
Soluția este o problemă de trial and error, cum spui tu.
Am analizat-o destul de mult, dar n-am reușit să găsesc un raționament matematic care să implice direct soluția.
Pentru că descompunerea în factori primi rezultă în urma unui calcul propriu-zis și nu a unui raționament matematic propriu-zis.
Ori asta implică o chestie de trial and error. Descompui în factori și vezi care variantă se potrivește cerințelor problemei.

Oricum, problema mi-a furat ceva timp. Felicitări !

---

Da. E o problemă frumoasă. Frumusețea vine din faptul că, deși ”vânăm” situațiile cele mai speciale cu putință, totuși există scenarii cu iz democratic în care doar un procent din populație poate decide învingătorul....

Există și în realitate situații în care președinții sunt aleși, perfect legal și democratic, cu mai puține voturi, în absolut, decât cei care pierd, sistemul american cu electori fiind un exemplu... bineînțeles că diferențele de voturi sunt mici...

Answer 4

Exprimăm numărul total n de votanți sub forma 

n = n₁•k₁ = n₁•n₂•k₂ = n₁•n₂•n₃•k₃ = ...= n₁•n₂•n₃•...•n_i•k_i  .

Matematic, trebuie să găsim valorile pe care le pot avea n₁ , n₂ , n₃ ,..., n_i , k_i ,  astfel încât

unde 2⁶•5⁵ este un procent din n.

Factorizarea lui n=20.000.000 este 2⁸•5⁷ , iar valorile pe care le pot avea n₁ , n₂ , n₃ ,..., n_i , k_i  trebuie să fie multiplu de 2 sau/și de 5.

Exprimând factorizarea lui n sub forma 

n = 4•4•4•4•5•5•5•5•5•5•5 ,

 valorile pe care le pot avea n₁ , n₂ , n₃ ,..., n_i , k_i  pot fi oricare din factorii lui n de mai sus, iar înlocuind aceste valori în inegalitatea de mai sus obținem

 3•3•3•3•3•3•3•3•3•3•3 = 3¹¹ < 2⁶•5^{5 .}

Această metodă de distribuire a numărului total de votanți în i=11 grupuri și sub-grupuri îi asigură președintelui alegerile.

Dacă ei ar putea fi distribuți într-o manieră în care valoarea lui i este mai mică decât 11, pentru i=10, factorizarea lui n va fi

 fie n = 4²•4•4•5•5•5•5•5•5•5, fie n = 4•4•4•4•5•5•5•5•5•5² .

În primul caz, înlocuind în inegalitatea de mai sus se obține

5•3¹⁰ > 2⁶•5⁵ ,iar în al doilea caz, 13•3¹⁰  > 2⁶•5⁵ .

În ambele situații, dacă votanții sunt distribuiți 10 grupuri și sub-grupuri, președintele nu poate câștiga alegerile.

Situația este identică dacă reducem din nou numărul de grupuri și sub-grupuri, ceea ce înseamnă că 11 este numărul minim de grupuri și sub-grupuri în care pot fi distribuiți votanții astfel încât președintele să câștige în mod sigur alegerile.

Dacă încercăm să mărim acest număr de 11 grupuri/sub-grupuri, atunci factorizarea lui n va conține de cel puțin două ori factorul 2,  situație în care va reieși, înlocuind în inegalitatea de mai sus, că numărul de susținători trebuie să fie cel puțin 4•3¹⁰ > 2⁶•5⁵ 

Aceasta înseamnă că, pentru a fi sigur că va câștiga alegerile, numărul total de votanți trebuie să fie împărțit în exact 11 grupuri și sub-grupuri.

Comments

E greșit ceva mai sus, trebuie corectat.

Și mai există încă o factorizare a lui n care dă același rezultat dar pentru i=10 :

n = 16•4•4•5•5•5•5•5•5•5