Caramelle e cioccolatini

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
leoll2
Messaggi: 1
Iscritto il: 11 mag 2014, 19:16

Caramelle e cioccolatini

Messaggio da leoll2 » 23 mag 2015, 21:32

Hai 99 contenitori, ognuno contenente un numero arbitrario di caramelle e cioccolatini. Dimostra che puoi scegliere 50 contenitori in modo da avere complessivamente almeno la metà delle caramelle e almeno la metà dei cioccolatini.

Nota: I numeri di cioccolatini e caramelle possono essere uguali tra loro, differenti o uguali a 0, mai negativi.

Giovanni_98
Messaggi: 69
Iscritto il: 10 apr 2015, 18:19

Re: Caramelle e cioccolatini

Messaggio da Giovanni_98 » 18 ott 2015, 19:05

Per complessivamente intendi il numero di caramelle più il numero di cioccolatini presenti nei 50 contenitori scelti?

Enigmatico
Messaggi: 79
Iscritto il: 03 dic 2014, 23:23

Re: Caramelle e cioccolatini

Messaggio da Enigmatico » 19 ott 2015, 18:38

Suppongo che "complessivamente" significhi che la somma di tutte le caramelle dei 50 contenitori deve essere almeno la metà del totale delle caramelle nei 99 contenitori e lo stesso deve valere per i cioccolatini (così è più difficile, :( ).

remat7
Messaggi: 21
Iscritto il: 21 feb 2014, 11:18

Re: Caramelle e cioccolatini

Messaggio da remat7 » 20 ott 2015, 11:01

Sia $ A $ il numero totale di cioccolatini e $ B $ quello delle caramelle.
Possiamo scrivere $ A= a_1 + a_2 + ... + a_{99} $ e $ B= b_1 + b_2 +...+ b_{99} $ dove $ a_i , b_i \geq 0 $ sono il numero di cioccolatini e caramelle contenute nell' i-esimo contenitore.
Chiamiamo $ S_i = a_i + b_i $. Ora riordino i contenitori con $ S_i $ crescente. Prendo i 50 contenitori con $ S_i $ più grande, essi contengono necessariamente almeno più della metà dei cioccolatini o delle caramelle.

Per motivi di tempo non posso formalizzare la conclusione, che consiste nel far vedere delle stupidaggini nei rimanenti 49 contenitori e nel dimostrare quindi che esiste sempre uno "scambio" che mi permetta di confermare la richiesta. Se qualcuno ha voglia di scrivere al posto mio gli sarei grato, altrimenti stasera o domani sera formalizzerò il tutto.

Giovanni_98
Messaggi: 69
Iscritto il: 10 apr 2015, 18:19

Re: Caramelle e cioccolatini

Messaggio da Giovanni_98 » 20 ott 2015, 13:28

Remat7 , se pongo $a_1=0$ e $a_2 = a_3 = \cdots = a_{99}=100$ e $b_1 = 90$ e $b_2=b_3=\cdots=b_{99}=0$ il tuo ragionamento non fila poichè gli $S_i$ più grandi sono quelli che hanno $100$ cioccolatini e $0$ caramelle , ma ovviamente $0 < \frac{99}{2}$.

RiccardoKelso

Re: Caramelle e cioccolatini

Messaggio da RiccardoKelso » 20 ott 2015, 17:05

Buttiamola lì, questo problema mi aveva sempre attirato.
Negare la tesi significa sostenere che per ognuna delle $\binom {99}{50}$ combinazioni possibili si abbia più della metà di un ingrediente e meno della metà dell'altro. Diciamo allora $N$ il numero di combinazioni tali per cui si ha più della metà dei cioccolatini e meno della metà delle caramelle. Se ne avranno di conseguenza $\binom {99}{50}-N$ tali per cui si ha meno della metà dei cioccolatini e più della metà delle caramelle. Ma notiamo che per ogni combinazione di un tipo ne deve esistere una dell'altro, di conseguenza $N=\frac{\binom {99}{50}}{2}$, il che per fortuna non dovrebbe essere intero, giungiamo quindi a una contraddizione.

EDIT: Se non vi convince la necessarietà (non penso che questa parola esista ma mi piace) di una corrispondenza biunivoca tra le combinazioni di un tipo e quelle dell'altro: per ogni comb. del primo tipo avremmo le combinazioni formate dai 49 elementi non scelti all'inizio e uno dei 50 invece scelti, ma così facendo contiamo 50 volte le combinazioni del secondo tipo. Quindi, ovviamente, $\frac{50x}{50}=x$.

remat7
Messaggi: 21
Iscritto il: 21 feb 2014, 11:18

Re: Caramelle e cioccolatini

Messaggio da remat7 » 20 ott 2015, 19:02

Giovanni_98 ha scritto:Remat7 , se pongo $a_1=0$ e $a_2 = a_3 = \cdots = a_{99}=100$ e $b_1 = 90$ e $b_2=b_3=\cdots=b_{99}=0$ il tuo ragionamento non fila poichè gli $S_i$ più grandi sono quelli che hanno $100$ cioccolatini e $0$ caramelle , ma ovviamente $0 < \frac{99}{2}$.
Giovanni, io ho infatti detto almeno metà delle caramelle o dei cioccolatini, non "e". :)

Giovanni_98
Messaggi: 69
Iscritto il: 10 apr 2015, 18:19

Re: Caramelle e cioccolatini

Messaggio da Giovanni_98 » 20 ott 2015, 20:55

Uh vero, chiedo scusa :roll:

AlexThirty
Messaggi: 217
Iscritto il: 20 giu 2015, 20:58

Re: Caramelle e cioccolatini

Messaggio da AlexThirty » 20 ott 2015, 22:54

RiccardoKelso ha scritto: EDIT: Se non vi convince la necessarietà (non penso che questa parola esista ma mi piace) di una corrispondenza biunivoca tra le combinazioni di un tipo e quelle dell'altro: per ogni comb. del primo tipo avremmo le combinazioni formate dai 49 elementi non scelti all'inizio e uno dei 50 invece scelti, ma così facendo contiamo 50 volte le combinazioni del secondo tipo. Quindi, ovviamente, $\frac{50x}{50}=x$.
Scusa potresti spiegare meglio questo che non mi è chiaro?
Grazie :)
Un bresciano esportato nel cremonese

-"Dal palazzo di giustizia di Catania o esci con più soldi di prima, o non esci proprio"
-"Baroni uscirebbe con un Win - Win".
Tutti si mettono a ridere, e allora intuisco che non aveva detto "Weed - Win" come avevo capito.

RiccardoKelso

Re: Caramelle e cioccolatini

Messaggio da RiccardoKelso » 21 ott 2015, 17:05

Vedila così
Definiamo combinazioni di tipo $A$ tutte quelle che comprendono più di metà dei cioccolatini e meno di metà delle caramelle. Analogamente, saranno di tipo $B$ tutte quelle comprendenti meno di metà dei cioccolatini e più di metà delle caramelle. Quando hai una combinazione di un tipo, sei sempre sicuro di trovarne una dell'altro con le 49 scatole non comprese all'inizio e una qualsiasi delle 50 comprese. Questo significa che per ogni combinazione $A$ ce ne è almeno una $B$, e viceversa.

AlexThirty
Messaggi: 217
Iscritto il: 20 giu 2015, 20:58

Re: Caramelle e cioccolatini

Messaggio da AlexThirty » 21 ott 2015, 17:40

Si ma alcune le conti più volte, non mi è quindi bene chiaro come puoi dire di ottenere una cosa biunivoca. Perché per ogni combinazione ne hai 50 dell'altra e non sai se effettivamente ne basteranno per tutti
Un bresciano esportato nel cremonese

-"Dal palazzo di giustizia di Catania o esci con più soldi di prima, o non esci proprio"
-"Baroni uscirebbe con un Win - Win".
Tutti si mettono a ridere, e allora intuisco che non aveva detto "Weed - Win" come avevo capito.

Luca Nalon
Messaggi: 20
Iscritto il: 03 lug 2015, 16:15

Re: Caramelle e cioccolatini

Messaggio da Luca Nalon » 21 ott 2015, 17:51

Inoltre aggiungendo una scatola alle 49 potrei aggiungere caramelle e/o cioccolatini e comprenderne magari più della metà di ognuno, quindi non sono nemmeno sicuro che tutte le 50 vadano bene. E poi... $ \binom{99}{50} $ è pari

RiccardoKelso

Re: Caramelle e cioccolatini

Messaggio da RiccardoKelso » 21 ott 2015, 18:05

AlexThirty ha scritto:Si ma alcune le conti più volte, non mi è quindi bene chiaro come puoi dire di ottenere una cosa biunivoca. Perché per ogni combinazione ne hai 50 dell'altra e non sai se effettivamente ne basteranno per tutti
Le prime combinazioni sono distinte per definizione, se vuoi non chiamiamola corrispondenza biunivoca dato che non preciso come associarle ma il numero delle prime deve essere uguale a quello delle altre.
Luca Nalon ha scritto:Inoltre aggiungendo una scatola alle 49 potrei aggiungere caramelle e/o cioccolatini e comprenderne magari più della metà di ognuno, quindi non sono nemmeno sicuro che tutte le 50 vadano bene. E poi... $ \binom{99}{50} $ è pari
Ti consiglio di rivedere la prima affermazione, non costituisce un attacco alla dimostrazione. Riguardo alla seconda... essendo il calcolo dei fattori 2 una questione piuttosto elementare, o continuo a sbagliare grossolanamente oppure...


EDIT: Meno male che hai controllato, così salta tutto :cry:

EDIT2: Però forse mi è venuta un'altra idea: considero la combinazione tale per cui si comprendono più di metà dei cioccolatini ($X$) e meno di metà delle caramelle ($Y$) e inoltre tale per cui non esistano altre combinazioni dello stesso tipo con un numero minore di $X$. A questo punto: se prendendo i 49 restati e uno dei 50 iniziali non è mai possibile soddisfare la richiesta, significa che sarebbe possibile abbassare ulteriormente $X$ pur rimanendo sopra la metà, il che va a contraddire l'ipotesi. :? :?:

bern-1-16-4-13
Messaggi: 72
Iscritto il: 23 mag 2015, 18:27

Re: Caramelle e cioccolatini

Messaggio da bern-1-16-4-13 » 23 ott 2015, 23:11

Riccardo, credo che non sia del tutto completa quella dimostrazione, perché in teoria scegliendo le altre 49 scatole più una qualsiasi delle altre 50 può anche darsi che non riesca mai a raggiungere la metà di cioccolatini...

vediamo se riesco a scrivere una soluzione decente...
Allora, ordiniamo le scatole in ordine crescente in base al numero di cioccolatini contenuti, quindi assegniamo alla [math]-esima scatola in questo ordinamento il numero [math].
Adesso ordiniamo le scatole in ordine crescente in base al numero di caramelle contenute, quindi assegniamo alla [math]-esima scatola in questo ordinamento il numero [math].
[math]NB è vero, potrebbero esserci due scatole con lo stesso numero di caramelle o cioccolatini, ma disponiamole in un'ordine a piacere negli
[math]ordinamenti, tanto nei passaggi della dimostrazione che seguono non è influente questo fatto.

Così abbiamo che ogni scatola è definita da una coppia di numeri [math].
Quindi da ora in poi identificheremo ogni scatola con la sua coppia di numeri, perciò non parleremo più di scatole ma di punti nel piano.
Per la precisione bisogna specificare che questi punti hanno coordinate [math]
e che a due a due non hanno ascissa o ordinata in comune.
é facilmente dimostrabile che una condizione sufficiente affinché il numero totale di cioccolatini delle [math] scatole scelte sia maggiore o uguale della metà dei cioccolatini totali è che tra i punti che hanno l'ascissa nell'intervallo [math] almeno la metà è stata scelta. In pratica tutto ciò è equivalente a dire che posso raggruppare i punti a due a due in modo che all'interno di ognuno di questi sottoinsiemi ci sia un punto scelto e uno non scelto, e che il primo abbia ascissa maggiore del secondo (il punto che avanza è ovviamente scelto).
Analoghi ragionamenti valgono anche per le caramelle, quindi per le ordinate.
Quello che segue adesso è un algoritmo (che dovrebbe essere generalizzabile a un qualsiasi numero dispari di punti) che a prescindere dalla configurazione di punti che abbiamo ci permette di sceglierne [math] in modo da rispettare la condizione sufficiente sopra descritta.
Da notare che è una tesi più potente di quella del problema.
Prendiamo il punto con ascissa [math], e poi a seguire scegliamo altri 24 punti con ascissa nell'intervallo [math] in modo che il punto con ascissa [math] appartenga all'insieme dei punti scelti se e solo se il punto con ascissa [math] non appartiene.
Con questo criterio a prescindere da come verranno scelti gli altri 25 punti la condizione sufficiente relativa alle ascisse viene rispettata per tutti i [math]. Se poi imponiamo anche che il punto con ascissa [math] sia scelto se e solo se la sua ordinata è maggiore dell'ordinata del punto con ascissa [math] otteniamo che il numero di punti non scelti con ordinata inferiore a [math] è maggiore o uguale di 24 quindi sempre a prescindere dalla scelta degli altri 25 punti la condizione sufficiente relativa alle ordinate viene rispettata per tutti i [math].
Ora dovrei riscrivere queste ultime sei righe invertendo i termini "ascissa" con i termini "ordinata", ma evito...
L'unica cosa da precisare in quest'altro passaggio è che essendo alcuni punti già stati scelti da prima, per rispettare i vincoli di scelta sopradescritti dei 25 punti ancora da scegliere, le ordinate di questi ultimi staranno nell'intervallo [math] con [math] più grande possibile, ma di certo [math]. In ogni caso stavolta si ottiene che la condizione sufficiente relativa alle ordinate è rispettata per tutti i [math] mentre la condizione sufficiente relativa alle ascisse è rispettata per tutti i [math].
Unendo i risultati di questi due passaggi abbiamo finalmente ottenuto che seguendo quei passaggi sia la condizione sufficiente per le ascisse che quella per le ordinate sono rispettate [math] e da qui deriva la tesi, e forse qualcosa di più: conoscendo soltanto gli ordinamenti delle scatole in base al numero di cioccolatini e di caramelle in esse contenuti, posso sceglierne 50 in modo da essere sicuro che il numero di cioccolatini di queste 50 scatole sia almeno la metà dei cioccolatini, e lo stesso valga per le caramelle.

Mi rendo conto che come dimostrazione è veramente pesante sia da leggere che da scrivere, ma penso che le idee di per sé siano abbastanza intuitive...

RiccardoKelso

Re: Caramelle e cioccolatini

Messaggio da RiccardoKelso » 25 ott 2015, 20:57

bern-1-16-4-13 ha scritto:Riccardo, credo che non sia del tutto completa quella dimostrazione, perché in teoria scegliendo le altre 49 scatole più una qualsiasi delle altre 50 può anche darsi che non riesca mai a raggiungere la metà di cioccolatini...
Ciò però implica che il numero dei cioccolatini contenuti nelle 50 può essere abbassato pur rimanendo sopra la metà, ma io ho preso la combinazione di 50 scatole tale per cui ciò non può avvenire.

Rispondi