Griglie quadrate

info · Messaggio da **info** » 01 gen 1970, 01:33

Ecco quà 2 esercizi sulle famigerate griglie, che ogni tanto ritornano. Ve li propongo...
 
 1) Una compagnia vuole costruire il suo nuovo edificio: una griglia quadrata 2001X2001, con delle porte che connettono camere adiacenti, cosicchè ogni camera ha esattamente 2 porte. Provare che questo è impossibile...
 
 2) In ogni quadrato di una griglia nXn viene scritto un intero. Quadrati con un lato in comune contengono interi che differiscono al più di 1. Provare che esistono nella griglia n numeri uguali...

positrone · Messaggio da **positrone** » 01 gen 1970, 01:33

2)Per dimostrare la proprietà voluta ci basta provarla nel caso in cui vengano usati nella griglia il massimo numero di interi in funzione della limitazione data.
 Consideriamo dunque ogni singola riga(orizzontale)della griglia partendo dalla prima,si possono usare al piu\' n interi consecutivi,passando alla seconda riga e adottando lo stesso criterio si ha che ogni numero di ogni quadrato è il successivo rispetto al numero del quadrato corrispondente alla prima riga:quindi il numero k che occupa l\'ultimo quadrato nella prima riga, nella seconda occupa il penultimo.Procedendo di riga in riga abbiamo che k arretra ogni volta di un quadrato fino ad arrivare ad occupare il primo quadrato nell\'n-esima riga.Resta così provato che vengono usati nella griglia n numeri k.
 
 [ Questo Messaggio è stato Modificato da: positrone il 02-11-2004 17:07 ]
 
 [ Questo Messaggio è stato Modificato da: positrone il 02-11-2004 17:07 ] [ Questo Messaggio è stato Modificato da: positrone il 02-11-2004 17:08 ]

MindFlyer · Messaggio da **MindFlyer** » 01 gen 1970, 01:33

Per il punto 1), vedi il problema 2 di Cesenatico 2003.

MindFlyer · Messaggio da **MindFlyer** » 01 gen 1970, 01:33

<TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD>Quote:<HR></TD></TR><TR><TD><BLOCKQUOTE>
 On 2004-11-02 17:07, positrone wrote:
 2)Per dimostrare la proprietà voluta ci basta provarla nel caso in cui vengano usati nella griglia il massimo numero di interi in funzione della limitazione data.
 Consideriamo dunque ogni singola riga(orizzontale)della griglia partendo dalla prima,si possono usare al piu\' n interi consecutivi
 </BLOCKQUOTE></TD></TR><TR><TD><HR></TD></TR></TABLE>
 Hehe, troppo comodo.
 Prima di tutto non dimostri l\'asserzione iniziale che, per quanto intuitivamente vera, va giustificata.
 E poi, non puoi assolutamente supporre senza perdere in generalità che la prima riga contenga n numeri distinti. Infatti, riesci a massimizzare il numero di elementi distinti della griglia anche senza porti in questa situazione. Insomma, se non era ovvio che ti servisse massimizzare gli elementi distinti dell\'intera griglia, è ancor meno ovvio che ti serva massimizzare quelli di una sola riga!

info · Messaggio da **info** » 01 gen 1970, 01:33

Ma allora a Cesenatico riciclate i problemi ? <IMG SRC="images/forum/icons/icon_biggrin.gif">
 Scherzi a parte, mind la tua nn mi sembra una soluzione... che importanza può avere che sia stato dato in una gara o no? L\'importante è la soluzione e se vuoi puoi scrivere quella che avete dato a Cesenatico.....

MASSO · Messaggio da **MASSO** » 01 gen 1970, 01:33

1) coloriamo a scacchiera la griglia; siccome il numero totale di quadretti è dispari possiamo porre che i quadretti neri siano almeno uno in più rispetto ai bianchi; ora se per assurdo fosse possibile dare due e sole due porte a tutte le stanze, avremo che si può uscire dalla zona nera da 2n porte, ma si può entrare nella zona bianca solo da 2b porte con n>b per ipotesi; ciò è chiaramente assurdo; (è chiaro che se esco da una stanza nera mi ritrovo in una bianca per come le ho colorate)

positrone · Messaggio da **positrone** » 01 gen 1970, 01:33

Non ho capito la\" bocciatura\" di Mind,infatti provando nel caso che ho considerato-cioè quando data una griglia nXn ogni quadrato di una riga o di una colonna contiene un intero diverso e il primo quadrato di una data riga(o colonna)contiene il numero succesivo rispetto a quello contenuto nella riga(o colonna)precedente-si dimostra per ogni altro caso perchè ogni altra griglia di nXn che non abbia la configurazione di quella illustrata sopra avrà almeno due numeri uguali in una riga o in una colonna,cosi,a parità di interi disponibili per essere disposti in una data griglia si dovranno usare più interi uguali n volte o ripetere un intero n+x volte, mentre nel primo caso da me considerato si ripete un solo intero n volte.Sono naturalmante disponibile per ulteriori correzioni,e\'possibilissimo che stia dicendo una gran boiata.
 P.S.Chiedo scusa,ma ho dimenticato di dare una risposta ad hoc per la prima obiezione che mi ha mosso Mind:se quadrati con un lato in comune possono contenere interi che distino al più di 1 per ottenere in una riga solo interi diversi tra loro essi dovranno essere consecutivi.

MindFlyer · Messaggio da **MindFlyer** » 01 gen 1970, 01:33

<TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD>Quote:<HR></TD></TR><TR><TD><BLOCKQUOTE>
 On 2004-11-03 17:28, info wrote:
 Ma allora a Cesenatico riciclate i problemi ? <IMG SRC="images/forum/icons/icon_biggrin.gif">
 Scherzi a parte, mind la tua nn mi sembra una soluzione... che importanza può avere che sia stato dato in una gara o no? L\'importante è la soluzione e se vuoi puoi scrivere quella che avete dato a Cesenatico.....
 </BLOCKQUOTE></TD></TR><TR><TD><HR></TD></TR></TABLE>
 Boh, è un problema che viene in mente così facilmente che non mi stupirei se l\'originale risalisse a ben prima del 2001!
 
 Ad ogni modo, la mia non voleva essere una soluzione, ho solo indicato un problema correlato e più generale. E\' una cosa che si usa fare quando si riconosce un problema già visto, ma non vuol dire assolutamente nulla.

MindFlyer · Messaggio da **MindFlyer** » 01 gen 1970, 01:33

<TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD>Quote:<HR></TD></TR><TR><TD><BLOCKQUOTE>
 On 2004-11-03 21:12, positrone wrote:
 si dimostra per ogni altro caso perchè ogni altra griglia di nXn che non abbia la configurazione di quella illustrata sopra avrà almeno due numeri uguali in una riga o in una colonna,cosi,a parità di interi disponibili per essere disposti in una data griglia si dovranno usare più interi uguali n volte o ripetere un intero n+x volte
 </BLOCKQUOTE></TD></TR><TR><TD><HR></TD></TR></TABLE>
 Sì, ho capito quello che dici! E ho capito anche che intuitivamente è vero.
 Tante grazie, dici una cosa che è equivalente alla tesi... il problema sta appunto nel dimostrare quell\'affermazione, e ti assicuro che non è cosa che possa essere liquidata così facilmente!
 
 Nella fattispecie, il tuo claim è: se vi sono 2 numeri uguali nella stessa riga o colonna, la tesi segue banalmente. A me sembra però che la tesi segua banalmente solo nel caso opposto, a cui corrisponde una sola configurazione!

positrone · Messaggio da **positrone** » 01 gen 1970, 01:33

Non capisco affatto neanche la seconda obiezione di Mind:quello che dico non è affatto equivalente alla tesi.
 Inoltre io dico proprio il contrario di quello che dice Mind nella seconda parte del messaggio,infatti la mia configuazione \"base\" è:in ogni riga e in ogni colonna sono disposti n numeri consecutivi,il numero collocato in un qualsiasi quadrato di una data riga o colonna è il successivo del numero collocato in un qualsiasi della riga o colonna precedente,quindi la successione di numeri consecutivi collocati nella prima riga sarà uguale alla successione di quelli della prima colonna,la successione della seconda riga uguale a quella della seconda colonna, e cosi via. Quindi si osserva facilmente che questa configurazione ci permette di utilizzare più interi diversi rispetto a qualsiasi altra configurazione si usi:infatti è la configurazione in cui ogni quadrato che contiene un dato numero è adiacente a quadrati che contengono numeri diversi di 1 rispetto al numero contenuto nel quadrato,quindi è il caso limite tenendo conto della richiesta fatta nel testo:che dice che la differenza tra numeri contenuti in quadrati aventi un lato adiacente è al più 1.
 Questa configurazione è naturalmente equivalente a quella nella quale si \"rovesci\" la griglia considerando con un ragionamento analogo il numero contenuto in un quadrato di una data riga o vcolonna come il precedente di quello contenuto nella riga o colonna precedente.
 
 [ Questo Messaggio è stato Modificato da: positrone il 05-11-2004 17:21 ] [ Questo Messaggio è stato Modificato da: positrone il 05-11-2004 17:22 ]

MindFlyer · Messaggio da **MindFlyer** » 01 gen 1970, 01:33

<TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD>Quote:<HR></TD></TR><TR><TD><BLOCKQUOTE>
 On 2004-11-05 16:56, positrone wrote:
 Quindi si osserva facilmente che questa configurazione ci permette di utilizzare più interi diversi rispetto a qualsiasi altra configurazione si usi:infatti è la configurazione in cui ogni quadrato che contiene un dato numero è adiacente a quadrati che contengono numeri diversi di 1 rispetto al numero contenuto nel quadrato,quindi è il caso limite tenendo conto della richiesta fatta nel testo:che dice che la differenza tra numeri contenuti in quadrati aventi un lato adiacente è al più 1.
 </BLOCKQUOTE></TD></TR><TR><TD><HR></TD></TR></TABLE>
 E\' appunto questo il discorso che non regge!!
 - Se lo dimostri, hai risolto il problema.
 - Se cominci con un \"si osserva facilmente\", e ti ostini a fare vaghi discorsi di \"caso limite\", hai semplicemente ripetuto la tesi del problema, e questa non è una dimostrazione.

info · Messaggio da **info** » 01 gen 1970, 01:33

Ok..il primo esercizio era il più facile. Usando poi il trucco della colorazione di Masso, è diventato lampante. Io avevo utilizzato il fatto che se facciamo un percorso chiuso, dobbiamo sempre passare un numero pari di camere...
 Il secondo mi pare più complicato. Quando ci stavo provando pensavo di essere arrivato vicino alla soluzione, ma mi ero rotto le scatole. Il mio approccio era induttivo... se avete altre idee...

info · Messaggio da **info** » 01 gen 1970, 01:33

up...voglio vedere quanto mi ero avvicinato alla sol...

positrone · Messaggio da **positrone** » 01 gen 1970, 01:33

Mi accorgo solo ora della tua risposta,Mind,e devo ammettere che hai proprio ragione...
 Provo quindi a dimostrare il punto \"incriminato\".
 Allora,provo che la configurazione che massimizzi gli elementi distinti è quella da me indicata nel caso in cui n=2:colloco un dato intero m nel primo quadrato della prima riga:se collocassi m stesso nel secondo quadrato,nel secondo quadrato della seconda riga dovrei collocare m , m+1 o m-1(se m>1)e nel primo quadrato della seconda riga dovrei necessariamente collocare m se ho collocato nel secondo quadrato m+1 o m-1,oppure m+1 o m-1 se nel secondo quadrato ho collocato m ,quindi con questa configurazione ho in ogni caso almeno tre m(e quindi almeno n+1 numeri uguali). Se invece-ritornando alla prima riga-colloco nel secondo quadrato m+1,posso collocare nel secono quadrato della seconda riga il successivo di m+1 e quindi m+2 e cosi posso collocare al primo quadrato della seconda riga m+1,questa configurazione mi permette di ottenere tre numeri diversi,ma al contempo ottengo che m+1 è ripetuto n volte. Essa è equivalente al caso in cui rivolti la griglia,cioè collochi i numeri che ho considerato nei secondi quadrati delle due righe(o colonne) nei primi e invece collochi quelli che ho considerato nei primi quadrati delle due righe(o colonne) nei secondi.
 Ora considero delle griglie di nXn pari,le posso considerare come degli \"agglomerati\" di griglie di 2X2,chiamo lati di \"confine\" i lati adiacenti tra quadrati che fanno parte di due delle griglie distinte di 2X2 che formano l\'agglomerato,allora,a partire dalla prima griglia applico la configurazione che ho dimostrato massimizzi gli elementi distinti nel caso n=2,estendo questa configurazione alle griglie di 2X2 formate da quadrati aventi lati di confine in comune,se cambio configurazione anche in una sola griglia di 2X2 avrò almeno in questa griglia una configurazione che non massimizza gli elementi distinti .Anche in questo caso posso rivoltare la griglia ottenendo una configurazione equivalente. Come già osservato nel caso della griglia 2X2,con questa configurazione viene ripetuto n volte solo il numero che occupa l\'ultimo quadrato all\' ultima riga,o se rivoltiamo la griglia-considerando quindi una progressione discendente di numeri nelle righe e nelle colonne-quello che occupa il primo quadrato alla prima riga.
 Ora estendo la configurazione anghe alle griglie di nXn dispari:considero sempre un agglomerato di griglie 2X2 e aggiungo una riga e una colonna:applico la configurazione \"massimizzante\" alle varie griglie 2X2(anche quelle formate da lati di confine)-e considero la riga e la colonna aggiunte come formanti ogni due loro quadrati una griglia di confine con la riga o colonna precedenti,ottenendo un caso analogo a quelli provati precedentemente.
 Spero che questa dimostrazione sia giusta ed esauriente.

MindFlyer · Messaggio da **MindFlyer** » 01 gen 1970, 01:33

<TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD>Quote:<HR></TD></TR><TR><TD><BLOCKQUOTE>
 On 2004-11-07 18:21, positrone wrote:
 Mi accorgo solo ora della tua risposta,Mind,e devo ammettere che hai proprio ragione...
 Provo quindi a dimostrare il punto \"incriminato\".
 [...]
 Spero che questa dimostrazione sia giusta ed esauriente.
 </BLOCKQUOTE></TD></TR><TR><TD><HR></TD></TR></TABLE>
 Perdonami positrone, ma temo che non ci siamo capiti minimamente.
 
 Partiamo dalla tua ultima dimostrazione, che dovrebbe far vedere che la configurazione da te descritta massimizza il numero di elementi distinti nella griglia.
 Premettiamo che dimostrarlo in modo giusto è facile, in quanto la \"distanza massima\" tra 2 caselle nella matrice è 2n-2, da cui il fatto che nella matrice vi possono essere al più 2n-1 numeri distinti, e la configurazione da te descritta ne contiene ovviamente 2n-1.
 Il guaio più immediato della tua dimostrazione è che provi la tesi per le griglie 2x2, ma l\'argomento secondo cui se massimizzi gli elementi distinti nelle sotto-griglie, allora hai massimizzato gli elementi distinti nella griglia, non regge per nulla. Ma nessun problema, perché come dicevo, dimostrarlo in modo giusto è facile.
 
 Al di là di queste sottigliezze, il grave guaio è che, come ti facevo notare fin dall\'inizio, tu hai dimostrato la tesi del problema solo per una configurazione!! Non hai detto ancora nulla su tutte le configurazioni in cui in una riga o in una colonna vi sono 2 numeri uguali. Nota ad esempio che molte di queste configurazioni massimizzano il numero di elementi distinti della griglia. Ed anche se non lo massimizzassero, ti servirebbe comunque un argomento valido per dire che verificano la tesi.
 
 Buon lavoro, quindi! [ Questo Messaggio è stato Modificato da: MindFlyer il 13-11-2004 00:21 ]