Combinatoria - preIMO 2017
Combinatoria - preIMO 2017
Anche qui, salve! La domanda che porrò qui si ricollega a una posta sul subforum di Algebra: nel quinto problema viene usata la disuguaglianza di Jensen per risolvere il problema, e viene dato per scontato che la funzione x(x-1)(x-2)(x-3)/24 sia convessa per x>3. Per dimostrare questa cosa, basta calcolare la derivata seconda e notare come sia sempre positiva per x>3; è lecito, però, far ricorso a nozioni di analisi? O esiste per caso una maniera differente attraverso cui giungere alla medesima conclusione? La domanda sorge, come anticipato, in quanto viene "rifiutata" la soluzione del settimo problema di algebra per mezzo degli integrali. Ancora: nella spiegazione si impone la funzione f(x)=0 per x≤3: ciò viene fatto per assicurare che la funzione risultante sia sempre convessa e in quanto lecito dal momento che i valori assunti da x sono sempre interi (ossia, non vi è alcuna differenza tra la funzione "vera" e questa scelta per x=0,1,2,3)? Non bastava dire che per x≤3 un coefficiente binomiale avente 4 sotto è sempre nullo, per cui bastava considerare la parte del dominio della funzione, in cui questa risulta incidentalmente sempre convessa, per la quale i valori assunti risultano diversi?
Re: Combinatoria - preIMO 2017
Non bastava. Cerca di capire da te perché in linea teorica non si può applicare Jensen su una funzione definita su quel dominio lì (hint: il problema è il dominio, non la funzione).
"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
"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
Re: Combinatoria - preIMO 2017
Beh, mi è chiaro perchè non sia convessa la funzione per x≤3; formulo nuovamente: è ammessa l'analisi dove utile per risolvere i problemi (soprattutto in questi casi dove non credo esista una via alternativa)?
Re: Combinatoria - preIMO 2017
È ammessa l'analisi (purché usata correttamente e con tutte le verifiche del caso; non basta dire "la derivata si annulla quindi è il minimo").
--federico
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]
Re: Combinatoria - preIMO 2017
Il punto è che se prendi una funzione definita solo sull'insieme $\{0\}\cup\{1\}\cup\{2\}\cup[3,+\infty)$ non puoi usare Jensen. Se l'insieme di definizione fosse $[0,+\infty)$ potresti. Allora come sistemi? Mettendo $0$ dappertutto per $x\le3$
![Wink ;)](./images/smilies/icon_wink.gif)
"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
"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
Re: Combinatoria - preIMO 2017
Ho studiato le soluzioni del settimo e dell'ottavo problema di combinatoria e ho compreso tutto abbastanza agevolmente; voglio solo sperare di essere io ad aver frainteso la traccia dei problemi. In particolare, nella risoluzione del C7, l'enumerazione delle città in ordine decrescente viene fatta ripercorrendo talvolta una stessa linea aerea nei due sensi (in caso contrario, anche nei grafi "esempio" proposti, si avrebbe un numero minore di enumerazioni possibili e molte terminerebbero in punti ciechi): la traccia, però, afferma testualmente "Per ciascuna città C, il sindaco di C conta i modi in cui può numerare le città (da 1 a n) in modo che, qualunque viaggio si faccia a partire da C senza utilizzare linee in entrambi i sensi, lungo il percorso le città sono numerate in ordine decrescente." Cosa non ho compreso di ciò?
Per il problema 8, invece, la questione è leggermente più subdola: innanzitutto, nella risoluzione viene discussa anche un'interessante variante che però non viene menzionata nella traccia, per cui presumo che non debba essere trascritta; nella soluzione del problema in sè, poi, ci si sofferma sulla possibilità di utilizzare il pumping lemma per togliere lettere (dimostrando che tutte le parole con anche meno di [math] lettere sono implementabili), ma non sulla loro aggiunta (per dimostrare invece che ogni parola anche più lunga di [math] può essere implementata). Vorrei dunque chiedere: quando nella traccia viene detto "Supponiamo che ogni parola di lunghezza esattamente [math] sia implementabile: dimostrare che ogni parola finita è implementabile" viene richiesta la dimostrazione delle parole con meno di [math] lettere o lettere con un numero di lettere [math] qualsiasi? In tal caso (che sarebbe quello a mio avviso più logico), può il pumping lemma da solo giustificare una tale affermazione?[math]
Ringrazio per la pazienza di chi vorrà rispondere anche a questi quesiti, dettati dalla volontà di non commettere errori banali.
EDIT: In ogni caso, ho dimostrato la possibilità di implementare qualsiasi parola di qualsiasi lunghezza finita nel caso dell'8; la traccia del 7 rispetto alla soluzione proposta, d'altro canto, continua a turbarmi...
Per il problema 8, invece, la questione è leggermente più subdola: innanzitutto, nella risoluzione viene discussa anche un'interessante variante che però non viene menzionata nella traccia, per cui presumo che non debba essere trascritta; nella soluzione del problema in sè, poi, ci si sofferma sulla possibilità di utilizzare il pumping lemma per togliere lettere (dimostrando che tutte le parole con anche meno di [math] lettere sono implementabili), ma non sulla loro aggiunta (per dimostrare invece che ogni parola anche più lunga di [math] può essere implementata). Vorrei dunque chiedere: quando nella traccia viene detto "Supponiamo che ogni parola di lunghezza esattamente [math] sia implementabile: dimostrare che ogni parola finita è implementabile" viene richiesta la dimostrazione delle parole con meno di [math] lettere o lettere con un numero di lettere [math] qualsiasi? In tal caso (che sarebbe quello a mio avviso più logico), può il pumping lemma da solo giustificare una tale affermazione?[math]
Ringrazio per la pazienza di chi vorrà rispondere anche a questi quesiti, dettati dalla volontà di non commettere errori banali.
EDIT: In ogni caso, ho dimostrato la possibilità di implementare qualsiasi parola di qualsiasi lunghezza finita nel caso dell'8; la traccia del 7 rispetto alla soluzione proposta, d'altro canto, continua a turbarmi...
Re: Combinatoria - preIMO 2017
Credo possa permettermi di uppare il dubbio sulla traccia del 7 dopo questo tot di giorni.
Re: Combinatoria - preIMO 2017
Allora, nel $7$ non c'è un problema di testo, ma un fraintendimento. Quando dice che ogni enumerazione è decrescente vuol dire che prendo una città e numero le città in modo che partendo dalla città di partenza e seguendo le linee fino a un punto cieco (e lì mi fermo) passo sempre da una città maggiore a una minore. Ci sono dunque dei percorsi indipendenti, cioè che si incontrano solo nella città d'origine e quindi non posso passare in alcun modo da uno all'altro.
Per quanto riguarda il tuo dubbio sull'$8$ devi dimostrare che quelle più corte sono implementabili (è una cosa molto facile e intuitiva) ma anche quelle di lunghezza finita grande a piacere. Il plumping lemma ti apre la strada, ma devi creargli attorno tutta una struttura (tipo induzione o dimostrazione per assurdo) per applicarlo bene a questo caso. Non ci metti molto, ma ti direi di fare attenzione a tutti i casi particolari, anche se forse sono troppo pignolo. In ogni caso sappi che la dimostrazione del video mi sembra che sia spiegata bene (la parte mancante è preparata bene ed è fattibile), ma se avessi altri dubbi non esitare a chiedere.
Per quanto riguarda il tuo dubbio sull'$8$ devi dimostrare che quelle più corte sono implementabili (è una cosa molto facile e intuitiva) ma anche quelle di lunghezza finita grande a piacere. Il plumping lemma ti apre la strada, ma devi creargli attorno tutta una struttura (tipo induzione o dimostrazione per assurdo) per applicarlo bene a questo caso. Non ci metti molto, ma ti direi di fare attenzione a tutti i casi particolari, anche se forse sono troppo pignolo. In ogni caso sappi che la dimostrazione del video mi sembra che sia spiegata bene (la parte mancante è preparata bene ed è fattibile), ma se avessi altri dubbi non esitare a chiedere.
Re: Combinatoria - preIMO 2017
Come già scritto nell'edit, per l'8 ho risolto abbastanza agevolmente; per il 7 faccio un esempio pratico preso direttamente dal video. Prendo n vertici, di cui uno collegato a tutti gli altri n-1 e con questi collegati solo a questo: i percorsi possibili sono evidentemente solo n-1 senza tornare indietro partendo dal centro (si va in un vertice qualsiasi e si resta bloccati), ma quelli invece possibili se si può tornare indietro sono alquanto evidentemente (n-1)!, esattamente il numero di percorsi per tal caso proposto nel video (diciamo che l'effetto di tale fraintendimento si riversa poi nel dimostrare la possibile bipartizione dei vertici del grafo, per effettuare la quale ho dato per lecito il ritornare sui propri passi...ed è quanto mi preoccupa in particolare).
Re: Combinatoria - preIMO 2017
Mh, credo di aver capito quale sia il fraintendimento. La mia idea sarebbe adesso di dimostrare che ogni ordinamento valido possa essere associato, più che a una varietà di percorsi chiusi, a un singolo percorso che possa tornare sui suoi passi basandomi sul fatto che il grafo sia per definizione un "albero" a più rami che non possono comunicare tra loro e, detto ciò, mantenere la dimostrazione della bipartizione delle città che sfrutta appunto tale tipo di percorso: ritieni che sia un'idea funzionante?