Newsgroup: it.hobby.enigmi
Titolo: Pirati

Ciao a tutti 
Ben ritrovati ...
Vi propongo un quesito facile facile
se e' gia comparso, vi chiedo scusa in anticipo.
Vi e' una comunita' di pirati, a loro modo piuttosto democratici.
Alla fine di un saccheggio devono dividersi il bottino (costituito da
monete d'oro). I pirati sono organizzati gerarchicamente in base alla
forza individuale ed ogni pirata sa esattamente quale posizione occupa
nella scala gerarchica (assegniamo il numero piu' alto al pirata piu'
forte e cosi' su 10 pirati il piu' forte avra' il numero 10 e il piu'
debole il numero 1).
La divisione delle monete d'oro avviene nel modo seguente:
a) il pirata piu' forte decide quale deve essere la divisione, quindi
assegna ad ogni pirata la quantita' di monete d'oro che gli spetta
b) la proposta viene messa ai voti (vota anche il proponente)
c) Se la proposta raggiunge il 50% dei consensi la proposta viene
approvata e la divisione delle monete viene effettuata secondo quanto
stabilito.
d) Se la proposta non raggiunge il 50% dei consensi il pirata proponente
viene buttato a mare e si riparte dal punto a con un pirata in meno.
Ammettiamo che la nostra comunita' di pirati sia formata da 10 pirati e
devono dividersi un bottino di 20 monete d'oro, considerando che non
esistono pirati della stessa forza, che ogni pirata non si fida di
nessun altro (quindi non ci si puo' mettere d'accordo in alcun modo),
che una moneta e' indivisibile, e che ogni pirata mira ad ottenere il
massimo delle monete e che comunque gode a buttare il piu' forte a mare,
quale deve essere la proposta del pirata 10 (il piu' forte, il primo a
parlare) per non essere buttato a mare e per ottenere il massomo delle
monete ?
e se i pirati fossero 40 e le monete 20 ?
e se i pirati fossero 60 e le monete 20 ?
Ciao
Italo

 monete ?
(tentativo di) SPOILER
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
GRADO   MONETE
  10                6
    9                5
    8                4
    7                3
    6                2
altri: niente
--
Er Roscio.

 altri: niente
La tua soluzione evita al pirata 10 di 
finire a mare, ma il pirata 10 
potrebbe ottenere piu' monete con una diversa ripartizione
 
Italo

 e se i pirati fossero 60 e le monete 20 ?
Come sopra; i pirati 60->41 finiscono tutti in mare.
(si suppone che a parita' di monete ottenute ciascun pirata preferisca
la soluzione per cui finiscono in mare il maggior numero di pirati)
:-)
Ciao,
C.
--

Questo manca nelle FAQ!!
:-)

 wrote in message
393CF4D8...@libero.it...

Hai ragione. Non ho riflettuto che conviene premiare
gli ultimi come si fa nel Vangelo, ma anche in politica,
con motivazioni diverse !... :-)))))
Credo che basti una ripartizione del genere:
GRADO   MONETE
   10              10
     4                4
     3                3
     2                2
     1                1
--
Er Roscio.

 
Si puo' fare ancora meglio:
GRADO   MONETE
 10       16
 8        1
 6        1
 4        1
 2        1
e nulla a tutti gli altri
:-)
Ciao,
C.
--

 wrote in message 393E2704...@stetel.com...

Non capisco il perché dei numeri pari e come mai
l'ottavo debba accontentarsi di una moneta...
--
Er Roscio.

 l'ottavo debba accontentarsi di una moneta...
Per il semplice fatto che non puo' ottenere di piu'! :-)
La dimostrazione e' molto semplice, anche se complessa da spiegare;
provo ad illustrarla, sperando di riuscire ad essere chiaro. In
sostanza basta fare un ragionamento a ritroso.
Dunque, consideriamo il caso limite in cui tutti i pirati tranne
gli ultimi due finiscono in mare: il n. 2 puo' tenersi tranquillamente
tutte le monete in quanto, pure se il n. 1 non e' d'accordo, avrebbe il
50% dei consensi e non finirebbe in mare.
Se i pirati rimasti sono 3 che succede? Il n. 3 non puo' tenersi tutte
le monete, perche' verrebbe buttato a mare; se pero' ne tiene 19 e ne
lascia una al n. 1, il n. 1 voterebbe a favore - in quanto se votasse
contro torneremmo al caso precedente in cui il n. 1 non becca neanche
una moneta. Abbiamo quindi il seguente schema parziale delle monete
per ciascun pirata, a seconda del numero di pirati rimasti:
       pirata:    3     2     1      |  n. di pirati
    ---------------------------------+----------------   
                             20      |      1
                       20     0      |      2
                 19     0     1      |      3
                                     |
Proviamo adesso a completare la tabella: che succede quando i pirati
sono 4? Nel caso rimangano in 3, il n. 2 non becca nulla; percio' a
lui conviene votare a favore se il n. 4 gli assegna almeno una
moneta... E poiche' col voto a favore del n. 2 il 4 raggiunge il 50%
dei consensi, chiaramente distribuira' le monete in questo modo: 19
a se stesso, una al n. 2 e nessuna al 3 e all'1.
Iterando il ragionamento, nel caso di cinque pirati il 5 per non
finire in mare deve assicurarsi l'appoggio di 2 pirati, per cui gli
basta dare una moneta ciascuno al n. 3 e al n. 1 e tenersi le 18
monete rimanenti: infatti se il 3 o l'1 votassero contro, ricadrebbero
nel caso sfavorevole in cui restano 4 pirati, per cui non beccherebbero
nulla. Ragionando sempre allo stesso modo, possiamo facilmente
completare la tabellina nel modo seguente (notare la regolarita' della
tabella):
pirata      10  9  8  7  6  5  4  3  2  1  |  n. di pirati
-------------------------------------------+----------------   
                                       20  |      1
                                    20  0  |      2
                                 19  0  1  |      3
                              19  0  1  0  |      4
                           18  0  1  0  1  |      5
                        18  0  1  0  1  0  |      6 
                     17  0  1  0  1  0  1  |      7
                  17  0  1  0  1  0  1  0  |      8 
               16  0  1  0  1  0  1  0  1  |      9
            16  0  1  0  1  0  1  0  1  0  |     10
                                           |
Per cui il n. 10 puo' tenersi le 16 monete dandone una ciascuno
ai pirati n. 8, 6, 4 e 2, come volevasi dimostrare.
Spero di essere stato sufficientemente chiaro; se hai dei dubbi
comunque chiedi pure! :-)
Ciao,
C.
--

 C.
Perfetto per i primi due casi 
per il terzo non e' cosi' semplice...
a parita' di monete un pirata cerca di non essere buttato a mare.
Mi spiego meglio, nel caso di 41 pirati, il 41 per salvarsi deve
ottenere 21 voti favorevoli (20 + il suo)., deve quindi "comprare" il
consenso di 20 colleghi pirati. Visto che ha esattamente 20 monete,
distribuendole a tutti i pirati dispari riesce a salvarsi pur non avendo
tenuto per lui alcuna moneta.
Il pirata 41 si salva avendo 0 monete.
Il pirata 42 si salva allo stesso modo.
Il pirata 43 deve comprare 21 consensi per poter sopravvivere, non
avendo sufficienti monete qualunque proposta fa viene buttato a mare
Il pirata 44 riceve comunque il voto favorevole del 43. Il 43 sa infatti
che se muore il 44 morira' anche lui. Il 44 riesce quindi a salvarsi in
quanto ha 20 voti comprati con le monete, il voto del 43 + il suo voto,
totale 22 voti e riesce a salvarsi...
e per gli altri ... ?
Ciao
Italo

 e per gli altri ... ?
Il 45 no, perche' avrebbe 21 consensi
Il 46 no, perche' avrebbe 22 consensi (20+il suo+quello del 45)
Il 47 no, perche' avrebbe 23 consensi (20+il suo+quello di 45 e 46)
Il 48 si, perche' avrebbe 24 consensi (20+il suo+quello di 45 e 46 e 47)
49, 50, 51, 52, 53, 54, 55 no
il 56 si: 20 + il consenso proprio e di 55,54,53,52,51,50,49 = 28
Finiscono in mare il 60, 59, 58, 57
Ma come deve distribuire le monete il 56? Torniamo indietro.
Il 42 si salva distribuendo le monete a tutti i pirati pari, tranne
che a se stesso. Il 44 le distribuisce a 20 pirati dispari tranne il
43, ma puo' gia' scegliere: le monete sono 20, i dispari tranne il 43
sono 21... se si arriva al 44, nessun pirata e' piu' certo di avere
almeno una moneta. Il 48 percio' non e' vincolato a doverle distribuire
a pirati pari, in quanto se anche le distribuisce ai dispari quelli
voterebbero a favore, perche' in caso contrario ciascuno rischierebbe
di essere proprio lui l'escluso dalla successiva distribuzione del
44... Lo stesso quindi si puo' dire per il 56, che puo' distribuire le
monete a 20 pirati a caso, scelti fra i primi 48.
Ciao,
C.
--
---------------------------------------------------------------------
http://www.egroups.com/group/g_6
  - Gruppo Scacchi E Informatica
Per tutti i programmatori italiani appassionati di scacchi, un punto
di incontro fondamentale: informazioni, consigli, materiale e quant'
altro sulla programmazione di software scacchistico.
---------------------------------------------------------------------