Caramelle e cioccolatini

[leoll2]

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]

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

[Enigmatico]

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]

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]

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]

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]

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]

Uh vero, chiedo scusa

[AlexThirty]

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

[RiccardoKelso]

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]

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

[Luca Nalon]

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]

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.

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

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]

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]k-esima scatola in questo ordinamento il numero [math]k.
Adesso ordiniamo le scatole in ordine crescente in base al numero di caramelle contenute, quindi assegniamo alla [math]k-esima scatola in questo ordinamento il numero [math]k.
[math]\hspace 0.3cmNB è vero, potrebbero esserci due scatole con lo stesso numero di caramelle o cioccolatini, ma disponiamole in un'ordine a piacere negli
[math]\hspace 0.3cmordinamenti, tanto nei passaggi della dimostrazione che seguono non è influente questo fatto.

Così abbiamo che ogni scatola è definita da una coppia di numeri [math](x,y).
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]\hspace 0.2cm x,y\in N\hspace 0.8cm 1\leq x,y\leq 99
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]50 scatole scelte sia maggiore o uguale della metà dei cioccolatini totali è che tra i punti che hanno l'ascissa nell'intervallo [math][j,99]\hspace 0.4cm \forall 99\geq j\geq 1 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]50 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]99, e poi a seguire scegliamo altri 24 punti con ascissa nell'intervallo [math][51,98] in modo che il punto con ascissa [math]2x appartenga all'insieme dei punti scelti se e solo se il punto con ascissa [math]2x-1 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]j\geq 50. Se poi imponiamo anche che il punto con ascissa [math]2x sia scelto se e solo se la sua ordinata è maggiore dell'ordinata del punto con ascissa [math]2x-1 otteniamo che il numero di punti non scelti con ordinata inferiore a [math]50 è 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]j<50.
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][2k+1,98] con [math]2k+1 più grande possibile, ma di certo [math]\leq 51. In ogni caso stavolta si ottiene che la condizione sufficiente relativa alle ordinate è rispettata per tutti i [math]j\geq 50 mentre la condizione sufficiente relativa alle ascisse è rispettata per tutti i [math]j<50.
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]\forall j\in[1,99]\hspace 0.3cm 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]

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.