Eccoci al piccioni milanesi 3..ancora telematica dell'unimi (quesito 5 stavolta).
Sono dati 2007 rettangoli con i lati di lunghezza intera e minore di 2007.
Dimostrare che esistono 3 rettangoli A,B,C congruenti a 3 dei dati tali che A sia contenuto (o uguale a) in B e B sia contenuto (o uguale a) in C.
Che l'invasione di pennuti abbia inizio..
-
enomis_costa88
- Messaggi: 537
- Iscritto il: 01 gen 1970, 01:00
- Località: Brescia
Che l'invasione di pennuti abbia inizio..
"Tu che lo vendi cosa ti compri di migliore?"
Membro dell' "Associazione non dimenticatevi dei nanetti! "
Membro dell'EATO.
Membro dell' "Associazione non dimenticatevi dei nanetti! "
Membro dell'EATO.
Che figata il titolo 
Vabeh, proviamoci.
Innanzitutto, giro tutti i rettangoli in modo che la base sia maggiore o uguale dell'altezza e in modo che abbiano il vertice in basso a sinistra in comune.
Poi li ordino per inclusione.
Abbiamo un insieme parzialmente ordinato di 2007 elementi, supponiamo che non contenga catene di lunghezza 3 (la nostra tesi è dimostrare che esistono).
Allora esiste un'anticatena di lunghezza almeno 1004. Per un lemma noto, che adesso non ho tempo (bella scusa... la realtà è che mi sto incasinando), l'insieme si partiziona in due anticatene.
Dei due rettangoli prendo quello con altezza massima. Se l'altro ha la stessa altezza, sono uno sottoinsieme dell'altro, assurdo.
Allora l'altro ha l'altezza minore. Se anche la base è minore o uguale, allora è sottoinsieme dell'altro. Altrimenti l'altezza è minore (almeno di 1) e la base è maggiore (almeno di 1)... ma attenzione, così facendo sta cercando di scappare dalla gabbia!
Vabeh, proviamoci.
Innanzitutto, giro tutti i rettangoli in modo che la base sia maggiore o uguale dell'altezza e in modo che abbiano il vertice in basso a sinistra in comune.
Poi li ordino per inclusione.
Abbiamo un insieme parzialmente ordinato di 2007 elementi, supponiamo che non contenga catene di lunghezza 3 (la nostra tesi è dimostrare che esistono).
Allora esiste un'anticatena di lunghezza almeno 1004. Per un lemma noto, che adesso non ho tempo (bella scusa... la realtà è che mi sto incasinando), l'insieme si partiziona in due anticatene.
Dei due rettangoli prendo quello con altezza massima. Se l'altro ha la stessa altezza, sono uno sottoinsieme dell'altro, assurdo.
Allora l'altro ha l'altezza minore. Se anche la base è minore o uguale, allora è sottoinsieme dell'altro. Altrimenti l'altezza è minore (almeno di 1) e la base è maggiore (almeno di 1)... ma attenzione, così facendo sta cercando di scappare dalla gabbia!
-
enomis_costa88
- Messaggi: 537
- Iscritto il: 01 gen 1970, 01:00
- Località: Brescia
se non ho capito male chiedi di trovare 3 rettangoli A,B,C dei 2007 dati tali che A sia contenuto in(o uguale a) Be stessa cosa per B con C...
se cosi provo a dare una soluzione:
li giro tutti in modo che abbiano la base maggiore o uguale rispetto all'altezza e il vertice in basso a sinistra coincidente (by edriv
)
poi con il pigeonhole trovo che almeno due rettangoli avranno la base uguale => uno dei due conterra l'altro (oppure saranno uguali).ne ho trovati due.
Per n misure possibili (di quelle delle basi) vuote avrò n+1 coppie di rettangoli, e l'altezza minima sarà n+1.
Ora per trovare il terzo devo trovare un rettangolo che abbia base minore dell'altezza minima di almeno una coppia.
Tra le prime n+1 misure (sempre delle basi) al massimo potrò avere n buchi e quindi almeno un rettangolo avrà base (e di conseguenza altezza) minore di quelli di una coppia=> avrò 3 rettangoli che soddisfano la proprietà.
forse è un incasinata...se non capite qualcosa provo a dirla meglio...
se cosi provo a dare una soluzione:
li giro tutti in modo che abbiano la base maggiore o uguale rispetto all'altezza e il vertice in basso a sinistra coincidente (by edriv
)poi con il pigeonhole trovo che almeno due rettangoli avranno la base uguale => uno dei due conterra l'altro (oppure saranno uguali).ne ho trovati due.
Per n misure possibili (di quelle delle basi) vuote avrò n+1 coppie di rettangoli, e l'altezza minima sarà n+1.
Ora per trovare il terzo devo trovare un rettangolo che abbia base minore dell'altezza minima di almeno una coppia.
Tra le prime n+1 misure (sempre delle basi) al massimo potrò avere n buchi e quindi almeno un rettangolo avrà base (e di conseguenza altezza) minore di quelli di una coppia=> avrò 3 rettangoli che soddisfano la proprietà.
forse è un incasinata...se non capite qualcosa provo a dirla meglio...