Che l'invasione di pennuti abbia inizio..

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Rispondi
Avatar utente
enomis_costa88
Messaggi: 537
Iscritto il: 01 gen 1970, 01:00
Località: Brescia

Che l'invasione di pennuti abbia inizio..

Messaggio da enomis_costa88 » 18 gen 2007, 14:56

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.
"Tu che lo vendi cosa ti compri di migliore?"

Membro dell' "Associazione non dimenticatevi dei nanetti! "
Membro dell'EATO.

Avatar utente
edriv
Messaggi: 1638
Iscritto il: 16 feb 2006, 19:47
Località: Gradisca d'Isonzo
Contatta:

Messaggio da edriv » 20 gen 2007, 15:31

Che figata il titolo :D

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! 8)

Avatar utente
enomis_costa88
Messaggi: 537
Iscritto il: 01 gen 1970, 01:00
Località: Brescia

Messaggio da enomis_costa88 » 20 gen 2007, 20:59

Edriv non ti pare d'avere cannoneggiato un po' troppo?

Si risolve bene anche senza usare Dilworth (il tuo lemma noto), e c'è una soluzione molto bella esteticamente..
"Tu che lo vendi cosa ti compri di migliore?"

Membro dell' "Associazione non dimenticatevi dei nanetti! "
Membro dell'EATO.

cromat
Messaggi: 70
Iscritto il: 24 feb 2007, 22:32
Località: roma

Messaggio da cromat » 28 feb 2007, 22:19

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

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à. :D

forse è un incasinata...se non capite qualcosa provo a dirla meglio...

Rispondi