[Ammissione WC17] Combinatoria 3: Turisti, tornatevene a casa!

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

[Ammissione WC17] Combinatoria 3: Turisti, tornatevene a casa!

Messaggio da Talete »

In una nazione ci sono $2016$ città. Possiamo stilare $4$ graduatorie $A_1$, $A_2$, $A_3$, $A_4$, ciascuna delle quali ordina totalmente tutte le città di questa nazione. Ciascun turista che arriverà sceglierà una graduatoria $A_i$ e una città $c$ e visiterà tutte le città che, secondo $A_i$, sono migliori di $c$, decidendo eventualmente se andare anche in $c$. Alla fine desideremmo che, comunque vengano prese due città $c$ e $c′$, l’insieme dei turisti che avranno visitato $c$ sia diverso dall’insieme di quelli che avranno visitato $c′$. Qual è il minimo numero $k$ di turisti per cui esistono graduatorie e scelte dei turisti che realizzano tale situazione?
"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
Avatar utente
Gerald Lambeau
Messaggi: 335
Iscritto il: 17 mag 2015, 13:32
Località: provincia di Lucca

Re: [Ammissione WC17] Combinatoria 3: Turisti, tornatevene a casa!

Messaggio da Gerald Lambeau »

Testo nascosto:
Stime!
Testo nascosto:
Ma se una graduatoria la scelgono $n$ turisti, sarà che la possiamo dividere in $n+1$ parti?
Testo nascosto:
Quanto varrà, come minimo, la più grande di queste parti? Pigeonhole!
Testo nascosto:
Ma poi, la devi spezzettare usando la seconda graduatoria, poi la terza, poi...
Testo nascosto:
Una volta che spezzetti con la quarta graduatoria, non ci devono più essere gruppi di città indistinte! Quindi un certo valore sarà uguale a $1$
Testo nascosto:
Ma allora, AM-GM ci dà un bound per $k$! ("Che ha detto? Ma è matto? Ma da dove lo tira fuori il bound per $k$???")
Testo nascosto:
Non dimentichiamoci di un esempio funzionante! (io ho messo le targhe alle città per mostrare l'esempio :D )
"If only I could be so grossly incandescent!"
Rispondi