[Ammissione WC16] Combinatoria 1: Tanti cioccolatini!

[Talete]

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?

[AlexThirty]

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

[Rho33]

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]

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]

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]

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)

[Delfad0r]

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]

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.

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 $?

[MATHia]

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

Si potrebbe dimostrare che quella divisione funziona per $n$ piccoli e poi per induzione dimostrare che funziona per tutti gli $n$?

Penso di sì, però mancherebbe comunque da dimostrare il terzo punto della lista di Delfad0r.

[Federico II]

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).

Quel momento figo in cui sei un correttore e puoi spacciare per tue le soluzioni più belle tra quelle trovate

O in questo caso sostituirei "più belle" con "più complete"

[LucaMac]

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

Illuso! In settimana? Credi che noi correttori siamo così *aggettivo a tua scelta, ma io suggerirei "lenti" , ma se preferisci "veloci" fa pure*?

[AlexThirty]

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

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...

[Rho33]

@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]

Mi piace pensare che quel "presto" implichi che in settimana finirete le correzioni, ma probabilmente mi sto illudendo

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!