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

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

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

Messaggio da Talete » 24 dic 2016, 15:18

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

Gerald Lambeau
Messaggi: 290
Iscritto il: 17 mag 2015, 13:32

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

Messaggio da Gerald Lambeau » 27 dic 2016, 14:44

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 )
"Non ho rispetto per i miei superiori, figurati se ho rispetto per i miei pari: il rispetto di un uomo lo merita solo chi è a lui inferiore."
Cit. Marco (mio vero nome)

The Game.

Ci sono cose che non si possono confutare; per tutto il resto, c'è la fisica.

Rispondi

Chi c’è in linea

Visitano il forum: Nessuno e 2 ospiti