[Ammissione WC16] Combinatoria 1: Tanti cioccolatini!

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Rispondi
Talete
Messaggi: 744
Iscritto il: 05 giu 2014, 13:47
Località: Riva del Garda

[Ammissione WC16] Combinatoria 1: Tanti cioccolatini!

Messaggio da Talete » 30 dic 2015, 22:47

NON pubblicate la soluzione prima delle 23:59 di oggi!

Ci sono $n$ bambini di età diverse che devono spartirsi $2n$ cioccolatini. Fanno così: il più grande propone una divisione, su cui si vota; se almeno il $50\%$ (incluso il proponente) è favorevole, la divisione viene attuata; altrimenti, lui viene escluso (con $0$ cioccolatini) e il successivo in ordine di età ripete la procedura con i bambini restanti. Se tutti vogliono più cioccolatini possibile e, se si trovano a dover scegliere tra due possibilità che gli porterebbero lo stesso numero di cioccolatini, votano in modo da eliminare più bambini possibile, come avverrà la divisione?
"Sei il Ballini della situazione" -- Nikkio
"Meriti la menzione di sdegno" -- troppa gente
"Sei arrivato 69esimo? Ottima posizione!" -- Andrea M. (che non è Andrea Monti, come certa gente pensa)
"Se ti interessa stanno inventando le baricentriche elettroniche, che dovrebbero aiutare a smettere..." -- Bernardo

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

Re: [Ammissione WC16] Combinatoria 1: Tanti cioccolatini!

Messaggio da AlexThirty » 31 dic 2015, 14:57

Sempre in ordine di hintosità
Testo nascosto:
Supponiamo rimangano in $ 2 $ a dividersi i cioccolatini, cosa succede?
Testo nascosto:
E se rimangono in $ 3 $, ora che sappiamo cosa succede se rimangono in $ 2 $, come se li dividono?
Testo nascosto:
Beh ora si capisce che tornando indietro, quello più grande ha sempre la situazione in mano
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.

Rho33
Messaggi: 89
Iscritto il: 16 set 2014, 13:15

Re: [Ammissione WC16] Combinatoria 1: Tanti cioccolatini!

Messaggio da Rho33 » 05 gen 2016, 13:24

La divisione potrebbe essere:
Testo nascosto:
WLOG $ n=2k $. Numero i bambini da $ 1 $ a $ n $ in ordine decrescente di età. Il bambino più grande dà un solo cioccolatino ai bambini numeri dispari( che sono quelli con la maggiore probabilità di essere esclusi), in tutto darà quindi $ k-1 $ cioccolatini. I restanti $ 3k+1 $ se li prende tutti lui( per farsi venire il mal di denti)
?

Nadal21
Messaggi: 164
Iscritto il: 12 mar 2015, 15:30

Re: [Ammissione WC16] Combinatoria 1: Tanti cioccolatini!

Messaggio da Nadal21 » 05 gen 2016, 18:27

Rho33 ha scritto:La divisione potrebbe essere:
Testo nascosto:
WLOG $ n=2k $. Numero i bambini da $ 1 $ a $ n $ in ordine decrescente di età. Il bambino più grande dà un solo cioccolatino ai bambini numeri dispari( che sono quelli con la maggiore probabilità di essere esclusi), in tutto darà quindi $ k-1 $ cioccolatini. I restanti $ 3k+1 $ se li prende tutti lui( per farsi venire il mal di denti)
?
:?: ma se $n$ è dispari? Ponendo $n=2k$ perdi di generalità.

Rho33
Messaggi: 89
Iscritto il: 16 set 2014, 13:15

Re: [Ammissione WC16] Combinatoria 1: Tanti cioccolatini!

Messaggio da Rho33 » 05 gen 2016, 21:45

Non credo, perchè la cosa è analoga nel caso dispari:
Testo nascosto:
$ n=2k-1 $. Allora, analogamente, il bambino più grande distribuisce un cioccolatino ai bambini dispari, ovvero in tutto $ k-1 $, ed i restanti $ 4k-2-(k-1)=3k-1 $ se li prende lui. Cosa ha di diverso?

Ora, a patto che questa divisione funzioni, nella soluzione di un problema del genere, va dato un metodo di divisione dimostrando che è la divisione ottimale, oppure è necessaria qualche altra cosa in più?

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

Re: [Ammissione WC16] Combinatoria 1: Tanti cioccolatini!

Messaggio da AlexThirty » 05 gen 2016, 22:13

Scrivere solo la divisione così è campato per aria. Chi mi dice che gli altri accettino anche se gli offre un solo cioccolatino? (il risultato mi esce molto simile mi sembra ma io ce lho scritto in funzione di n quindi penso sia giusto, ma va dimostrato perché effettivamente funziona questa divisione)
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.

Delfad0r
Messaggi: 42
Iscritto il: 28 ago 2014, 19:59

Re: [Ammissione WC16] Combinatoria 1: Tanti cioccolatini!

Messaggio da Delfad0r » 06 gen 2016, 11:43

Questo problema è più insidioso di quanto possa sembrare, cosa di cui molti aspiranti partecipanti si renderanno presto conto.
Testo nascosto:
Una soluzione completa prevede infatti che si dimostri:
  • che la distribuzione proposta viene accettata (cioè che il bambino più grande ottiene almeno il 50% dei voti se la propone), che è vero perchè tutti i bambini cui viene proposto un cioccolatino votano a favore perchè...
  • che la distribuzione proposta è ottimale (cioè che il bambino più grande non può sperare di ottenere più cioccolatini di quelli che ottiene così), che è vero perchè, affinchè un bambino voti a favore, è necessario che riceva almeno un cioccolatino perchè...
  • che la distribuzione proposta è l'unica ottimale, che è vero perchè, se una proposta contiene il medesimo numero di cioccolatini allora deve darne necessariamente uno a testa ai bambini che votano a favore, ma alcuni bambini ne vogliono almeno 2, quindi...
Alternativamente, al posto degli ultimi due punti di può dire che, fra i bambini diversi dal più grande, circa la metà (in particolare, il numero minimo necessario da convincere) esigono almeno un cioccolatino per essere convinti (perchè ...), mentre tutti gli altri ne esigono almeno 2 (perchè...), quindi al bambino più grande conviene (perchè...) convincere tutti e soli quelli che esigono un cioccolatino (che è circa la stessa cosa dei punti sopra riformulata).

Nadal21
Messaggi: 164
Iscritto il: 12 mar 2015, 15:30

Re: [Ammissione WC16] Combinatoria 1: Tanti cioccolatini!

Messaggio da Nadal21 » 06 gen 2016, 12:13

Rho33 ha scritto:Non credo, perchè la cosa è analoga nel caso dispari:
Testo nascosto:
$ n=2k-1 $. Allora, analogamente, il bambino più grande distribuisce un cioccolatino ai bambini dispari, ovvero in tutto $ k-1 $, ed i restanti $ 4k-2-(k-1)=3k-1 $ se li prende lui. Cosa ha di diverso?
Ora, a patto che questa divisione funzioni, nella soluzione di un problema del genere, va dato un metodo di divisione dimostrando che è la divisione ottimale, oppure è necessaria qualche altra cosa in più?
Mi pare, ma forse sbaglio, che quello che hai scritto nell'hint dimostri che, pur essendo giusto il ragionamento, non è corretto scrivere $ WLOG \quad n=2k \quad $ altrimenti nei due casi (pari o dispari) il risultato dovrebbe essere uguale. :)
Delfad0r ha scritto:Questo problema è più insidioso di quanto possa sembrare, cosa di cui molti aspiranti partecipanti si renderanno presto conto.
Si potrebbe dimostrare che quella divisione funziona per $ n $ piccoli e poi per induzione dimostrare che funziona per tutti gli $ n $? :roll:

MATHia
Messaggi: 90
Iscritto il: 11 apr 2014, 01:08

Re: [Ammissione WC16] Combinatoria 1: Tanti cioccolatini!

Messaggio da MATHia » 06 gen 2016, 12:38

Delfad0r ha scritto:Questo problema è più insidioso di quanto possa sembrare, cosa di cui molti aspiranti partecipanti si renderanno presto conto.
Mi piace pensare che quel "presto" implichi che in settimana finirete le correzioni, ma probabilmente mi sto illudendo :D
Nadal21 ha scritto:Si potrebbe dimostrare che quella divisione funziona per $n$ piccoli e poi per induzione dimostrare che funziona per tutti gli $n$? :roll:
Penso di sì, però mancherebbe comunque da dimostrare il terzo punto della lista di Delfad0r.

Avatar utente
Federico II
Messaggi: 230
Iscritto il: 14 mag 2014, 14:56
Località: Roma

Re: [Ammissione WC16] Combinatoria 1: Tanti cioccolatini!

Messaggio da Federico II » 06 gen 2016, 12:49

Delfad0r ha scritto:Questo problema è più insidioso di quanto possa sembrare, cosa di cui molti aspiranti partecipanti si renderanno presto conto.
Testo nascosto:
Una soluzione completa prevede infatti che si dimostri:
  • che la distribuzione proposta viene accettata (cioè che il bambino più grande ottiene almeno il 50% dei voti se la propone), che è vero perchè tutti i bambini cui viene proposto un cioccolatino votano a favore perchè...
  • che la distribuzione proposta è ottimale (cioè che il bambino più grande non può sperare di ottenere più cioccolatini di quelli che ottiene così), che è vero perchè, affinchè un bambino voti a favore, è necessario che riceva almeno un cioccolatino perchè...
  • che la distribuzione proposta è l'unica ottimale, che è vero perchè, se una proposta contiene il medesimo numero di cioccolatini allora deve darne necessariamente uno a testa ai bambini che votano a favore, ma alcuni bambini ne vogliono almeno 2, quindi...
Alternativamente, al posto degli ultimi due punti di può dire che, fra i bambini diversi dal più grande, circa la metà (in particolare, il numero minimo necessario da convincere) esigono almeno un cioccolatino per essere convinti (perchè ...), mentre tutti gli altri ne esigono almeno 2 (perchè...), quindi al bambino più grande conviene (perchè...) convincere tutti e soli quelli che esigono un cioccolatino (che è circa la stessa cosa dei punti sopra riformulata).
A risposta di suggerimenti per un altro problema, qualcuno ha scritto:Quel momento figo in cui sei un correttore e puoi spacciare per tue le soluzioni più belle tra quelle trovate :lol:
O in questo caso sostituirei "più belle" con "più complete" :P
Il responsabile della sala seminari

LucaMac
Messaggi: 178
Iscritto il: 14 set 2014, 19:59
Località: Napoli

Re: [Ammissione WC16] Combinatoria 1: Tanti cioccolatini!

Messaggio da LucaMac » 06 gen 2016, 13:12

MATHia ha scritto:
Delfad0r ha scritto:Questo problema è più insidioso di quanto possa sembrare, cosa di cui molti aspiranti partecipanti si renderanno presto conto.
Mi piace pensare che quel "presto" implichi che in settimana finirete le correzioni, ma probabilmente mi sto illudendo :D
Illuso! In settimana? Credi che noi correttori siamo così *aggettivo a tua scelta, ma io suggerirei "lenti" , ma se preferisci "veloci" fa pure*?
"And if we want to buy something to drink?"
"Just go to 7-11"
-----------------------------------
"Why an inequality?"
"Inequality happens"

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

Re: [Ammissione WC16] Combinatoria 1: Tanti cioccolatini!

Messaggio da AlexThirty » 06 gen 2016, 16:38

LucaMac ha scritto:
MATHia ha scritto:
Delfad0r ha scritto:Questo problema è più insidioso di quanto possa sembrare, cosa di cui molti aspiranti partecipanti si renderanno presto conto.
Mi piace pensare che quel "presto" implichi che in settimana finirete le correzioni, ma probabilmente mi sto illudendo :D
Illuso! In settimana? Credi che noi correttori siamo così *aggettivo a tua scelta, ma io suggerirei "lenti" , ma se preferisci "veloci" fa pure*?
Il bello di questa tua affermazione è che non ha rivelato niente...
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.

Rho33
Messaggi: 89
Iscritto il: 16 set 2014, 13:15

Re: [Ammissione WC16] Combinatoria 1: Tanti cioccolatini!

Messaggio da Rho33 » 06 gen 2016, 18:27

@Delfador: grazie per i chiarimenti!(anche se non ho tentato l'ammissione)
@Nadal21: Ah, ho capito che intendevi, avevo un concetto del WLOG diverso evidentemente( nel senso che i procedimenti nei due casi sono identici, cambia il numero di caramelle che si prende il più grande)

LucaMac
Messaggi: 178
Iscritto il: 14 set 2014, 19:59
Località: Napoli

Re: [Ammissione WC16] Combinatoria 1: Tanti cioccolatini!

Messaggio da LucaMac » 06 gen 2016, 19:10

AlexThirty ha scritto:
LucaMac ha scritto:
MATHia ha scritto: Mi piace pensare che quel "presto" implichi che in settimana finirete le correzioni, ma probabilmente mi sto illudendo :D
Illuso! In settimana? Credi che noi correttori siamo così *aggettivo a tua scelta, ma io suggerirei "lenti" , ma se preferisci "veloci" fa pure*?
Il bello di questa tua affermazione è che non ha rivelato niente...
Era voluto!
"And if we want to buy something to drink?"
"Just go to 7-11"
-----------------------------------
"Why an inequality?"
"Inequality happens"

Rispondi