Newsgroup: it.hobby.enigmi
Titolo: [MA] I figli dello sceicco

Per avere la concessione di alcuni pozzi di petrolio devo pagare una
tangente a un certo sceicco.
Questo è un uomo estremamente giusto, perciò pretende una somma che possa
essere suddivisa equamente tra i suoi figli. A ciascun figlio maschio deve
spettare la stessa cifra, e così per le figlie femmine (le cifre vanno
calcolate in Euri interi, senza frazionamenti).
Dalle informazioni che sono riuscito ad ottenere, risulta che:
_Lo sceicco è sicuramente sposato, ma non può avere più di quattro mogli;
_Ciascuna moglie gli ha dato almeno un figlio maschio ed una femmina;
_Nessuna moglie ha avuto più di sei figli complessivamente;
_Gli eventuali figli avuti dalle concubine non vanno considerati.
Chi mi aiuta ad avere la concessione con la minima spesa?
ciao
paolo

 Chi mi aiuta ad avere la concessione con la minima spesa?
E' probabile che a quest' ora non ci abbia capito un
sacrosanto tubo, pero'....
Spoiler
Spoiler
Spoiler
2 Euro e te la cavi, no?
ciao
fulvio

#include "Paolo Licheri.h"

Nonostante fulvio abbia gia' risposto, butto li' un'idea, dato che il
ragionamento e' assente e io non ci ho capito una cippa di sagola di come
sia arrivato all'irrisoria cifra di 2 Euro...
Dunque, come minimo ha 2 figli.
E con 2 Euro ce la si farebbe... ma come si puo' stabilire cosi' a priori,
ammettendo che fulvio abbia dato la risposta giusta, che lo sceicco ha due
figli?
Cioe', tendenzialmente si sa che ne ha un numero compreso fra 2 e 24, ma
come si puo' minimizzare la spesa?
L'unico modo che mi viene in mente e' di ridurre il problema a trovare il
piu' piccolo intero divisibile senza resto per tutte le cifre da 2 a 24...
Quindi...
24*23*22*...*4*3*2
Ma:
24 :(2^3 * 3)
23 e' primo
22 :(2,11)
21 :(7*3)
20 :(5 * 2^2)
19 e' primo
18 : 3^2*2
17 e' primo
16 :2^4
15 :5*3
14 :7*2
13 e' primo
12 2^2*3
11 e' primo
10 :5*2
9 :3^2
8:2^3
7 e' primo
6: 3*2
5 e' primo
4: 2^2
3,2: primi
2*3*5*7*11*13*17*19*23=223.092.870 euro.. .che pero' non e' sicuramenter
la spesa minima...
Come diavolo si arriva a 2 Euro?
---
Blackstorm
*Vicario d'Armi di IDF con gatto al seguito*                     .--.
                                                                |o_o |
Tittums e' il nostro gatto, ed ha le dimensioni                 |:_/ |
di un rotolo di soldini. Inarcava la schiena                   //   \ \
e bestemmiava come uno studente in medicina.                  (|     | )
(Jerome Klapka Jerome)   [UIN 116647346 (nick: blacks)]       /'_   _/`\
*************************************************************(___)=(___/

 la spesa minima...
Questa mi sembra una versione semplificata del problema: il vincolo imposto nel
problema dice che la somma deve essere divisibile per tutte le combinazioni
figli maschi/figlie femmine. Per cui bisogna che, per ogni combinazione di figli
Maschi/Femmine valga la seguente proprieta`:
	per ogni M,F esistono DM,DF tali che Somma = F*DF + M*DM 
Con il tuo ragionamento, si arriva ad un risultato che mi pare valido, pero` non
dovresti fare il prodotto dei soli numeri primi da 2 a 24, bensi` il minimo
comune multiplo dei valori da 2 a 24, che e` piu` alto: 5.354.228.880.
Ad esempio, 223.092.870 non e` divisibile per 8.
Certamente esisteranno soluzioni migliori.
ciao ciao,
Marco
-- 
http://www.ing.unife.it/docenti/MarcoGavanelli

 Ad esempio, 223.092.870 non e` divisibile per 8.
C' e' stato almeno un errore nel calcolo del mcm: 8=2^3  e
non si puo' semplificarlo mettendo un solo 2 tra i fattori,
mi pare.
Per il resto non ho strumenti di forza bruta ne' il tempo di
risolverlo "a mano" comunque concordo sul fatto che il
minimo non provenga dal semplice calcolo del mcm, in quanto
ogni possibilita' di 1,2,3,4 mogli porta ad un minimo di
maschi e femmine diverso e dunque alcune combinazioni non
sono ammesse. Inoltre la distinzione tra maschi e femmine
genera una divisione del patrimonio che potrebbe
semplificare il tutto (se ho ben capito i termini del
problema, ossia tuti i maschi devono avere la stessa cifra
tra loro e tute le femmine pure, ma non necessariamente
uguale ai maschi).
A titolo di puro esempio, mettiamo il caso di avere
esattamente 4 femmine e da 4 a 6 maschi. Qui basta fare il
mcm di 4,5,6 (60) ed aggiungere 4 in modo da lasciare 1 euro
ciascuna alle donzelle (alla faccia della parita' ;-) ),
senza dover fare il mcm dei numeri da 8 a 10. Rendo l' idea?
ciao
fulvio
PS- Non ho tempo per sviluppare quell' idea della caccia al
tesoro di cui avevo parlato :-((((((((
       Comunque il progetto resta nel cassetto, prima o
poi....

 senza dover fare il mcm dei numeri da 8 a 10. Rendo l' idea?
E` esattamente l'idea che stavo studiando. Secondo i miei calcoli ci sono 62
possibili combinazioni maschi/femmine interessanti (ad esempio, se ho trovato la
soluzione per 4/4 ho anche la soluzione per 2/2, basta moltiplicare per un
fattore 2). Quindi, trovate tutte le possibili combinazioni, eliminando quelle
simmetriche (scambiare i maschietti con le femminucce) e tenere solo la piu`
grande fra le frazioni equivalenti, dovrebbero rimanere 62 possibilita`. A
questo punto si costruisce un sistema lineare che coinvolge le 62*2 variabili.
Il problema e` quindi un problema ILP (Integer Linear Programming).
Sconsiglio di provarci a forza bruta, io sto usando EPLEX ed ancora non sono
arrivato ad una soluzione ...


 Il problema e` quindi un problema ILP (Integer Linear Programming).
Devo aver fatto qualche errore nel programma, non avevo tenuto conto del massimo
valore rappresentabile (e, chissa` perche', non mi da` overflow...)
Ho trovato un valore un po' piu` basso, a mano:
N = 2*2*2*2*3*3*5*7*11*13*17*19
insomma, non metto nel mcm il fattore 23, in quanto il valore N si riesce ad
ottenere come A*B+C*D con valori interi qualsiasi siano i valori possibili A e C
che forniscono somma 23, cioe` (19,4), (18,5), ..., (12,11).
Credo che il meccanismo si possa iterare; ora non ho tempo ne' di correggere il
programma ne' di iterare :-(


 arrivato ad una soluzione ...
Io ho solo una soluzione parziale. Considero che il sesso più rappresentato
non può essere superiore a 20 (
p.es
. 4 mogli con 5 figli maschi ciascuna) e
l'altro sesso può al max, arrivare a 12 (24 figli, 12 m e 12 f).
Allora calcolo il MCM dei numeri da 2 a 20 (232792560 Euri), e separatamente
il MCM dei numeri da 2 a 12 (27720 Euri), ed ho le somme separate
ripartibili rispettivamente tra i maschi e le femmine (o viceversa).
La somma delle due, 232820280 Euri (poco più di 450 miliardi di lire)
dovrebbe andar bene per ogni caso.
Comunque sono curioso di vedere se il tuo metodo mi consente di risparmiare.
:-)
ciao
paolo

 Chi mi aiuta ad avere la concessione con la minima spesa?
La somma delle mogli e' compresa tra 1 e 4.
Per ogni moglie il numero di figli e' compreso tra 2(M+F) e 6.
I soldi spesi sono dati dalla somma dei soldi per i maschi e
dei soldi per le femmine S=Sm+Sf, tale per cui le due cifre
siano divisibili senza resto rispettivamente per la sommatoria 
di tutti i maschi e per quella di tutte le femmine. Un euro a
testa e' il minimo.
La soluzione minima e' 1 moglie, da cui 2 figli, 1 maschio e
una femmina: 2 euro. 
Del tutto avulsa dalla realta'. Manchera' qualcosa?
P.S.: eur_o_, non eur_i_.
P.P.S.: faccio fuori tutti i figli dello sceicco, a parte quelli delle
concubine, cosi' la soluzione minima diventa 0 (zero) €uro. ;)
Mh. Tra viaggio e spese varie, mi sa che no. ^_^;;
-- 
ciriciao from kirone
togliere il punto tra "lib" ed "ero", che ci sta per antispam
gia' che ci siete, togliete pure l'.invalid

 Comunque sono curioso di vedere se il tuo metodo mi consente di risparmiare.
Per ora ho trovato un 12.279.960 euro; ti ho gia` fatto risparmiare 220.540.320
euro! Mi dai una percentuale? ;-)


 Comunque sono curioso di vedere se il tuo metodo mi consente di risparmiare.
Altroche',
la soluzione ottima ti fa spendere "solo" 27.720 euro!


 P.S.: eur_o_, non eur_i_.
La questione è controversa. Se ne è discusso recentemente in
it.cultura.linguistica.italiano, e sembra che si dovrà adattare a quello che
sarà l'uso predominante.
Per quanto mi riguarda, vanno bene sia gli Euri che gli Euro, ... purché
siano molti.
:-)
ciao
paolo

 la soluzione ottima ti fa spendere "solo" 27.720 euro!
Ottimo!
Non so come tu ci sia arrivato; solo ora che ho visto il risultato e fatto
qualche verifica, mi sono accorto che ci si poteva arrivare direttamente
senza troppi calcoli.
Infatti la somma S=27.720 è esattamente il MCM degli interi tra 1 e 12.
Qualunque sia la ripartizione dei figli, sarà comunque del tipo A+B, e posto
A<=B deve essere A<=12.
Allora S risulta comunque divisibile per A. Basta ripartire la somma in due
parti
S-(A*B) che è ancora divisibile per A
(A*B) che è comunque divisibile per B
e il gioco è fatto.
Ti sono debitore della percentuale
:-)
ciao
paolo

> la soluzione ottima ti fa spendere "solo" 27.720 euro!
Prima di andare sallo sceicco, ti arriva una soffiata:
_I figli maschi sono piů delle femmine.
Puoi risparmiare qualcosa?
Silv:o)

 Puoi risparmiare qualcosa?
Certo! Quanto ti devo per la soffiata?
spoiler
.
.
.
.
.
.
.
.
In questo caso me la cavo con 2520 Euri (MCM dei primi 10 numeri naturali)
Infatti le femmine non possono essere più di 11.
allora:
Se F<11 procedo come nel caso precedente
2520-(M*F) è divisibile per F
(M*F) è divisibile per M
Se F=11, M può essere 12 o 13
2520=1584+936
1584 divisibile per 11
936 divisibile per 12 e per 13
ciao
paolo

 In questo caso me la cavo con 2520 Euri (MCM dei primi 10 numeri naturali)
In realtà posso ancora ridurre
ri spoiler
.
.
.
.
.
.
.
.
.
e arrivo a S=840 Euri, un terzo del valore precedente.
Considerato che le femmine sono al max 11, S risulta divisibile per F,
eccetto i casi F=9 ed F=11.
Per F=9, M può valere 10, 11, 12, 13, 14, 15
per F= 11 M può valere 12 o 13
Considerato che S è divisibile anche per 10, 12, 14, 15, esistono solo tre
casi in cui S non è divisibile per M né per F.
In questi tre casi posso  ripartire 840 in due tranches, come segue:
F   M  SommaF SommaM
9  11    774    86
9  13    801    36
11 13    671   169
In tutti gli altri casi S è divisibile almeno per uno dei due numeri M;F,
quindi le due tranches possono essere:
S-(M*F) ancora divisibile per M o per F, ed (M*F) divisibile per l'altro.
___
Posso anche dimostrare che, con le informazioni di cui dispongo, 840 è il
minimo indispensabile.
Infatti 840=3*5*7*8; e la somma in questione deve essere divisibile per
tutti quei fattori, per coprire per esempio le combinazioni 3+6; 5+10; 7+14;
8+16.
________
Però temo che lo sceicco, che sperava di farsi molti miliardi, vedendo che
dovrà accontentarsi di meno di due milioni si
inc#### un bel po'.
E, come in tutti i problemi del genere, mi farà tagliare la testa, o peggio,
mi costringerà a sposare tutte le sue figlie.
Se non mi sentirete per un po' di tempo, sapete il perché. :-(
ciao
paolo

 Euro, ... purché siano molti.
Fermo restando che sia meglio avercene tanti piuttosto che pochi ;-)) , mi
sembra di ricordare che sulle banconote ci sia scritto 5, 10, etc. EURO e
non EURI.
Un saluto.
Gianni
PS: Aderite compatti al Luigino Fans Club (n° 62 soci, finora)
--
Socio fondatore del Luigino Fans Club. Tessera n° 0001
Speroni propone di chiudere le frontiere agli islamici. Come faranno a
distinguerli? Con la prova del salame e del vino? Chi non mangia e non beve
non entra?


Uhm, ho scazzato il calcolo, cmq l'idea era quella di trovare il mcm...


 mi costringerà a sposare tutte le sue figlie.
Beh, avere da 2 a 11 mogli ma solo 1 suocero e non piu` di 4 suocere non mi
sembra cosi` male ;-)
In bocca al lupo!
Marco
-- 
http://www.ing.unife.it/docenti/MarcoGavanelli


Ora pero' me la spieghi... :)


 Ora pero' me la spieghi... :)
Beh, una spiegazione l'ha gia` data Paolo. Ti posso spiegare come ci sono
arrivato io.
Il nostro problema e` che per ogni possibile coppia di valori Maschi/Femmine
dobbiamo trovare due coefficienti, chiamiamoli Cm e Cf tali che:
	Maschi * Cm + Femmine * Cf = Somma.
Vogliamo trovare la Somma minima. Allora prendiamo tutte le possibili
combinazioni Maschio/Femmina interessanti (che come ho scritto in un post
precedente, sono 78) e scriviamo un sistema di 78 equazioni lineari in 78*2+1
incognite:
	7 * Cm1 + 6 * Cf1 = Somma
	7 * Cm2 + 7 * Cf2 = Somma
	8 * Cm3 + 5 * Cf3 = Somma
	...
	20* Cm78+ 4 * Cf78= Somma
con funzione obiettivo minimizzare la Somma.
Questo sistema si potrebbe risolvere, ad esempio, con l'algoritmo del Simplesso,
che e` bravissimo a trovare il valore minimo di una funzione obiettivo lineare
in un insieme definito da vincoli lineari (uguaglianze e disuguaglianze). Il
problema e` che ci vengono fuori delle soluzioni frazionarie, mentre noi
vogliamo che tutti i coefficienti (ed anche la Somma) siano interi.
Dobbiamo quindi utilizzare qualche algoritmo adatto a risolvere sistemi lineari
con vincoli di integrita`; per questo si affianca in genere il Simplesso con il
metodo del Branch & Bound, oppure con altri metodi. Sono algoritmi un po'
complicati; se la cosa ti interessa puoi guardare qualche tutorial:
http://mat.gsia.cmu.edu/orclass/integer/integer.html
oppure leggere qualcosa di Ricerca Operativa (in particolare, l'algoritmo del
Simplesso).
Ciao ciao,
Marco
-- 
http://www.ing.unife.it/docenti/MarcoGavanelli


Sarei interessato se non lo avessi come esame... :(((
