Tanti piccioni

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
xXStephXx
Messaggi: 471
Iscritto il: 22 giu 2011, 21:51

Re: Tanti piccioni

Messaggio da xXStephXx » 06 ott 2015, 20:51

RiccardoKelso ha scritto:Il titolo del post mi ha attratto in maniera irresistibile
Significa che dovresti usare pigeonhole :D 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.

Avatar utente
gpzes
Messaggi: 173
Iscritto il: 01 gen 1970, 01:00
Contatta:

Re: Tanti piccioni

Messaggio da gpzes » 07 ott 2015, 00:05

xXStephXx ha scritto:
RiccardoKelso ha scritto:Il titolo del post mi ha attratto in maniera irresistibile
Significa che dovresti usare pigeonhole :D 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.
:wink: :wink: beh si...
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....

RiccardoKelso

Re: Tanti piccioni

Messaggio da RiccardoKelso » 15 ott 2015, 09:12

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 :oops:

xXStephXx
Messaggi: 471
Iscritto il: 22 giu 2011, 21:51

Re: Tanti piccioni

Messaggio da xXStephXx » 22 ott 2015, 16:55

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.

EvaristeG
Site Admin
Messaggi: 4759
Iscritto il: 01 gen 1970, 01:00
Località: Roma
Contatta:

Re: Tanti piccioni

Messaggio da EvaristeG » 23 ott 2015, 14:47

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

RiccardoKelso

Re: Tanti piccioni

Messaggio da RiccardoKelso » 23 ott 2015, 15:59

Tutte cose a me note.

EvaristeG
Site Admin
Messaggi: 4759
Iscritto il: 01 gen 1970, 01:00
Località: Roma
Contatta:

Re: Tanti piccioni

Messaggio da EvaristeG » 23 ott 2015, 16:52

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

erFuricksen
Messaggi: 165
Iscritto il: 28 lug 2014, 10:01
Località: Genova, Pisa

Re: Tanti piccioni

Messaggio da erFuricksen » 21 nov 2015, 10:49

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.
$ x^2 + (y - \sqrt {|x|} )^2 = 2 $

xXStephXx
Messaggi: 471
Iscritto il: 22 giu 2011, 21:51

Re: Tanti piccioni

Messaggio da xXStephXx » 23 nov 2015, 17:33

Diciamo che era pensato per non "conoscere" esplicitamente Dilworth :D

Rispondi