Significa che dovresti usare pigeonhole Secondo me per vedere la strada giusta conviene fare come faresti nella realtà, supponendo di voler prendere la più lunga sequenza idonea. Ovviamente non guarderesti tutti i piccioni insieme andando a tentativi, sarebbe troppo dispersivo... Magari cominci considerando solo quelli più a sinistra, ignorando tutti gli altri... e via via ne aggiungi uno nuovo vedendo cosa si modifica.RiccardoKelso ha scritto:Il titolo del post mi ha attratto in maniera irresistibile
Tanti piccioni
Re: Tanti piccioni
Re: Tanti piccioni
beh si...xXStephXx ha scritto:Significa che dovresti usare pigeonhole Secondo me per vedere la strada giusta conviene fare come faresti nella realtà, supponendo di voler prendere la più lunga sequenza idonea. Ovviamente non guarderesti tutti i piccioni insieme andando a tentativi, sarebbe troppo dispersivo... Magari cominci considerando solo quelli più a sinistra, ignorando tutti gli altri... e via via ne aggiungi uno nuovo vedendo cosa si modifica.RiccardoKelso ha scritto:Il titolo del post mi ha attratto in maniera irresistibile
ad essere sincero avevo fatto ragionamento leggermente diverso..inizio dai due più a sinistra..essi creano tre intervalli di altezze..allora devo sistemare n-2 elementi in tre fasce..ne esisterà una con almeno $ \lfloor {(n-2)/3}\rfloor+1 $ elementi....
Re: Tanti piccioni
Si tratta di una strada che avevo provato inizialmente che però non mi ha portato da nessuna parte. Sfortunatamente ancora adesso non riesco a concretizzare l'idea, chiedo quindi umilmente che qualcuno espliciti
Re: Tanti piccioni
Numeri i piccioni da $1$ a $n$ (da sinistra verso destra). All' $i-esimo$ piccione ci associ una coppia di naturali $(a_i, b_i)$ dove $a_i$ è la lunghezza della più lunga sequenza crescente che puoi formare prendendo l'$i-esimo$ piccione e guardando solo quelli alla sua sinistra, e analogamente $b_i$ è la lunghezza della più lunga decrescente. Ora facendo qualche considerazione sulle $(a_i,b_i)$ ottieni facilmente la tesi.
Re: Tanti piccioni
Beh, insomma, c'è anche da dire che una minima variante di questo problema appare ad ogni lezione di P medium (o quasi) e ad alcune lezioni di P basic negli ultimi 5 o 6 Senior...
Re: Tanti piccioni
Beh, l'onere di informarsi sta a voi, puelli carissimi.
Non è difficile notare il thread Senior 2015 con 41 pagine in Olimpiadi della Matematica...magari a quel punto uno si domanda cosa sia questo "senior" e usa un po' la funzione Cerca del forum.
Diciamo che il fatto che siano online le lezioni degli ultimi 9 anni (cioè file video e pdf per un totale di più di 800 ore di lezione su argomenti da base ad avanzati) dovrebbe essere una delle prime cose che sfrutta chi vuole ben prepararsi alle Olimpiadi.
BTW, in quello che ha scritto xXStephXx c'è un sacco di roba che va espansa... al lavoro, se non avevate mai visto questo genere di soluzione
Non è difficile notare il thread Senior 2015 con 41 pagine in Olimpiadi della Matematica...magari a quel punto uno si domanda cosa sia questo "senior" e usa un po' la funzione Cerca del forum.
Diciamo che il fatto che siano online le lezioni degli ultimi 9 anni (cioè file video e pdf per un totale di più di 800 ore di lezione su argomenti da base ad avanzati) dovrebbe essere una delle prime cose che sfrutta chi vuole ben prepararsi alle Olimpiadi.
BTW, in quello che ha scritto xXStephXx c'è un sacco di roba che va espansa... al lavoro, se non avevate mai visto questo genere di soluzione
-
- Messaggi: 169
- Iscritto il: 28 lug 2014, 10:01
- Località: Genova, Pisa
Re: Tanti piccioni
Propongo una formalizzazione del problema che dovrebbe (spero) andare bene per risolverlo
Ci basta immaginare l'insieme dei piccioni come un ordine parziale in cui, messi i piccioni in fila, esiste una relazione dal piccione A al piccione B se A viene prima di B in fila e A è più alto di B. In questo modo è facile vedere che una catena rappresenta una successione di piccioni crescente, mentre un'anticatena rappresenta una successione di piccioni decrescente. A questo punto per il Teorema di Dilworth posso dire che se esiste una partizione in $k$ anticatene al minimo allora esisterà una catena di almeno $k$ elementi. Vediamo allora che se $k \ge \sqrt{n}$ allora esiste sicuramente una catena di almeno $\sqrt{n}$ piccioni, mentre se $k < \sqrt{n}$ allora per pigeonhole almeno un'anticatena conterrà almeno $\sqrt{n}$ piccioni. E così si finisce, basta solo verificare che questo sia il minimo creando delle anticatene di cardinalità uguale fra loro nei casi in cui è possibile.
Ci basta immaginare l'insieme dei piccioni come un ordine parziale in cui, messi i piccioni in fila, esiste una relazione dal piccione A al piccione B se A viene prima di B in fila e A è più alto di B. In questo modo è facile vedere che una catena rappresenta una successione di piccioni crescente, mentre un'anticatena rappresenta una successione di piccioni decrescente. A questo punto per il Teorema di Dilworth posso dire che se esiste una partizione in $k$ anticatene al minimo allora esisterà una catena di almeno $k$ elementi. Vediamo allora che se $k \ge \sqrt{n}$ allora esiste sicuramente una catena di almeno $\sqrt{n}$ piccioni, mentre se $k < \sqrt{n}$ allora per pigeonhole almeno un'anticatena conterrà almeno $\sqrt{n}$ piccioni. E così si finisce, basta solo verificare che questo sia il minimo creando delle anticatene di cardinalità uguale fra loro nei casi in cui è possibile.
$ x^2 + (y - \sqrt {|x|} )^2 = 2 $
Re: Tanti piccioni
Diciamo che era pensato per non "conoscere" esplicitamente Dilworth