O Problema de Matamatica Instructiva

În țara Bashtania cu capitala la Khalab-al-Amouk din centrul Africii, condusă

de președintele All-Mirra-Floress, s-a apropiat timpul noilor alegeri prezidențiale. În țară sunt 20 milioane de alegători dintre care numai un procent (armata regulată a Bashtaniei) îl susține pe All-Miraa-Floress. All-Mirra-Floress , natural, dorește să fie ales, dar pe de altă parte el dorește ca alegerile sa pară democratice. Iată ce numește All-Mirra-Floress “votare democratica”: toți alegătorii sunt împărțiți în grupe egale, apoi fiecare dintre aceste grupe se împarte intr-un număr oarecare de grupe egale ,apoi acestea se impart din nou în grupe egale ș.a.m.d.; în cele mai mici grupe se alege reprezentantul grupei – electorul – apoi electorii aleg reprezentanții lor pentru votare în grupele mai mari ș.a.m.d ; în sfărșit reprezentanții celor mai mari grupe aleg președintele . All-Guvidess a împărțit alegătorii așa cum a vrut el și și-a instruit partizanii cum să voteze.

Poate el organiza “ alegerile democratice “ astfel încăt sa fie ales președinte?

( la egalitate de voturi căștigă opoziția).

Răspuns: DA. POATE.

Înainte de toate să vedem cum se poate ca în alegerile acestea “ cu mai multe trepte” să căștige candidatul pentru care votează minoritatea. În multe țări capitaliste se votează după acest sistem. Cel mai simplu exemplu care ilustrează astfel de situație este reprezentat în

figura 1: aici sunt 9 alegători – 4 din grupa A ( în desen cerculeț negru) și cinci din grupa B (trifoi) – care sunt împărțiți în 3 grupe de căte 3 alegători , astfel încăt în două grupe căștigă cei din A și deci ca rezultat al acestor alegeri “în două trepte” va fi ales candidatul susținut de cei din A , deși numărul susținătorilor săi este numai 4/9 din numărul total al alegătorilor.

Figura 1: Ọ

Ọ Ọ ♣

Ọ ♣ Ọ ♣ ♣ ♣

Ọ Ọ ♣

– 2 –

Nu e greu să se stabilească faptul că, la alegerile în două trepte cu un număr mai mare de alegători, procentul voturilor necesare pentru alegere poate fi chiar și mai mic, dar să fie mai mare de 25%.

Este clar că la o alegere în trei trepte acest procent poate fi făcut și mai mic. De exemplu, dacă înlocuim în figura 1. pe fiecare alegător printr-o grupă de 100 de cetățeni , astfel încăt în grupa de tip B toți sunt din B iar intr-una de tip A , 51 sunt din A și 49 din B, obținem un exemplu de situație în care cei din A reprezintă

4 51 17

numai –- x –- = –– din numărul total de alegători și totuși ei înving.

9 100 75

Rezolvarea problemei.

Împărțim toți alegătorii în 5 grupe de căte 4 milioane, astfel încăt două dintre grupe să fie formate în întregime din adversari ai lui All-Mirra-Floress ( vom numi aceste grupe de tip B , iar celelalte trei de tip A). Fiecare dintre aceste grupe de “rangul întăi) le împărțim din nou în cinci grupe care formează o grupă de tip A de rangul întăi trei să fie din A ș.a.m.d. așa cum se vede în tablou.

Este clar că, în această împărțire , pentru victoria lui All-Mirra-Floress e suficient ca pentru el să

3 11 177 147 1

voteze ––– = –––––- ≤ –– din totalul alegătorilor. Cum armata reprezintă

28 x 57 20 000 000 100

1% din totalul alegătorilor și ea îl susține pe All-Mirra-Floress , el poate învinge.

Se poate încerca să se rezolve următoarea problemă mai generală:

Care este numărul minim de partizani ai lui All-Mirra-Floress , astfel ca acesta să căștige „alegerile democratice” ,dacă numărul total de alegători este N?

Desigur că răspunsul nu depinde numai de mărimea numărului N ci și de modul în care se descompune în factori. Dacă N este prim, atunci alegătorii nu pot fi împărțiți în grupe egale ( inafară de cazul banal : N grupe de căte un singur om) și pentru victorie este necesară majoritatea simplă . Să încercăm să răspundem la această problemă pentru un N oarecare.

Să considerăm o astfel de descompunere a lui N în grupe ( de rangul întăi, al doilea ș.a.m.d.)

– 3 –

astfel încăt să căștige All-Mirra-Floress și numărul partizanilor săi să fie cel mai mic posibil. Evident că se poate considera că în grupele care votează contra lui nu este nici-un partizan de-al său și că toate grupele de tip A de același rang sunt împărțite la fel.

Notăm: ⌠…..⌡ ─ „partea întreagă „( ⌠x⌡este cel mai mare întreg care nu-l depășește pe x).

Evident că dacă o anumită grupă de tip A este formată din k grupe de rangul următor, atunci printre acestea trebuie să fie cel puțin ⌠k/2⌡+1 de tip A. Să presupunem că fiecare grupă de rang r ( r = 1,2,…,m-1) se descompune în kr grupe de rangul următor ,iar grupele de ultimul rang , al m-lea, sunt formate dintr-un singur om. Atunci pentru victoria grupei A , este necesar să fie cel puțin: ( ⌠k1/2⌡+1) (⌠k2/2⌡+1) … (⌠km/2⌡+1) voturi pentru A.

Problema noastră s-a redus la următoarea: să se descompună numărul dat N într-un produs de factori k1,k2 , … km, astfel încăt produsul R să fie minim. Fie: N = 2ª p1 ….pm unde m ≥0, a≥0 sunt numere naturale , p1 … pm sunt numere prime impare. Notăm prin P produsul :

(p1+1)/2 ….(pm +1)/2. Atunci numărul minim de partizani a lui All-Mirra-Floress , sufficient pentru victorie este :

R = 2P, dacă a = 1 ( adică dacă N = 2p1 … pm )

R = 5ⁿP , dacă a = 3n ( N = 8ⁿ p1 … pm )

R = 3∙ 5ⁿ P, dacă a = 3n + 2 ( N = 4∙ 8ⁿ p1 … pm )

R = 9 ∙5ⁿ P, dacă a = 3n + 4 ( N = 4² 8ⁿ p1 … pm ) , n număr natural.

În particular pentru N = 20 000 000 = 28 · 57 = 4· 82·57 , obținem : R = 34 · 52 · 112 = 164 025.

Acesta este numărul minim de partizani ai lui All-Guvidess astfel ca el să căștige alegerile democratice.

Sursa de informative:

Bibliografie: Revista popular stiințfiică de fizică și matematică Kvant ( Cuanta ).

Problema a fost dată la a XXXII – a olimpiadă din Moscova