Griglie quadrate

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

uppo questo msg...Io nn ho ancora voglia di riprovarci e nn so quando mi arriverà...e poi il secondo esercizio da me postato può essere un buon allenamento per tutti i fortunanti che parteciperanno a breve ai giochi di archimede. Quindi datevi da fare e postate (Mind, cmq nn è che ti sia vietato postare la sol)...

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-11 21:21, info wrote:
 il secondo esercizio da me postato può essere un buon allenamento per tutti i fortunanti che parteciperanno a breve ai giochi di archimede.
 </BLOCKQUOTE></TD></TR><TR><TD><HR></TD></TR></TABLE>
 Mah, più che altro sarebbe un buon allenamento per le IMO.
 
 <TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD>Quote:<HR></TD></TR><TR><TD><BLOCKQUOTE>
 (Mind, cmq nn è che ti sia vietato postare la sol)...
 </BLOCKQUOTE></TD></TR><TR><TD><HR></TD></TR></TABLE>
 Appena la trovo, la posto. Ok? <IMG SRC="images/forum/icons/icon_wink.gif">
 
 Nel frattempo, eccovi un problema simile ma più facile, che potrebbe fornire qualche buona idea per la soluzione:
 
 Stessa griglia nxn riempita di numeri interi. Ma questa volta i vincoli sono più forti: i quadrati con un lato o un vertice in comune contengono interi che differiscono al più di 1. Dimostrare che vi sono n interi uguali nella griglia.

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

Archimede chiama, io rispondo sperando di non ripetere performance da 0-... <IMG SRC="images/forum/icons/icon_smile.gif">
 
 Stessa griglia nxn riempita di numeri interi. Ma questa volta i vincoli sono più forti: i quadrati con un lato o un vertice in comune contengono interi che differiscono al più di 1. Dimostrare che vi sono n interi uguali nella griglia.
 
 partiamo dai casi semplici per vedere come funziona:
 - griglia 1x1, ts...
 - griglia 2x2, le terne di valori possibili sono:k, k+1, k-1; per il principio del pigeonhole ci sono almeno due numeri uguali.
 - griglia 3x3, i valori possibili sono sempre al massimo tre, sempre per il pigeonhole ci sono almeno tre numeri uguali.
 - griglia 4x4, le cose si complicano, i valori possibili sono al massimo quattro (ma va un po\' dimostrato forse?!? <IMG SRC="images/forum/icons/icon_wink.gif"> ), ci sono almeno 4 numeri uguali
 - griglia nxn, i valori possibili sono al massimo n (da dimostrarare...), ci sono almeno n numeri uguali.
 Qualche idea per al massimo n interi diversi?
 
 \"La numero 3!\" - Lord Farquaad

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

Melkon, mi sa che puoi considerarti sulla buona strada.
 Non ti resta che farti venire l\'idea giusta per dimostrare che vi sono al più n interi distinti nella matrice.
 
 EDIT:
 Ehm, se leggi bene, l\'ho dimostrato io 2 messaggi fa... [ Questo Messaggio è stato Modificato da: MindFlyer il 13-11-2004 00:19 ]

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

mi è venuta una idea che prescinde da discorsi di quadrati 2x2 che boh non ho capito del tutto 2n-2 & co. ...
 L\'idea è: dato che il legame è più forte e anche negli angoli i due numeri possono differire di al più una cifra, oltre che lungo le righe e le colonne, anche lungo la diagonale al più la variazione è di n numeri. Premettendo che, dato un numero k in alto a sinistra nella griglia, il valore più lontano numericamente è quello più lontano anche geometricamente (e questo posso considerarlo ovvio nella massimizzazione, perchè se ci fosse un valore massimo più vicino (w) potrei chiudere li la griglia n-wxn-w e quindi ci sarebbero meno numeri diversi, il che non è affatto una massimizzazione, no?) allora possiamo dire che dato che la differenza massima tra due caselle contigue è 1
 [porca miseria mio fratello ha appena sboccato... scusate l\'OT...]
 dicevo, allora possiamo dire la differenza tra il primo numero e l\'ultimo è (k+n) - k, e cioè evidentemente n, che è la tesi.
 
 \"Ehi amico tu e il mulo su pulitevi il... viso
 Duloc è, Duloc è, Duloc è il paradiso!\" - Shrek

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

Ehm, Melkon, non ho capito del tutto quello che dici.
 Diciamo che ho capito solo che tuo fratello ha sboccato e che sei un fan di Shrek. Potresti ripetere il resto della trattazione?
 Grazie, ciau!

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

Ok rileggendo tutto con calma ho visto di avere scritto parecchie bestialità tutte insieme... quindi riparto dall\'inizio, e speriamo dopodomani che mi vada meglio...
 
 Allora
 nella massimizzazione, il valore assoluto della differenza fra due numeri più alto è quello di due numeri uno in un angolo e l\'altro nell\'n-1 esima riga o colonna opposta. Questo è lampante, perché se ci fosse un valore per il quale ciò è verificato più vicino, allora non sarebbe una massimizzazione, perchè potrei \"chiudere lì\" la griglia. Però questo valore assoluto vale al massimo n-1, appunto perchè la differenza massima tra due caselle adiacenti è 1, e quindi possiamo finalmente dire che ci sono al più n cifre diverse, da cui consegue necessariamente la tesi.
 
 Mi sono spiegato meglio? ma soprattutto, va bene?
 
 Mi è appena venuta un\'idea per l\'originale, problema n2
 invece di dire \"il valore assoluto della differenza fra due numeri più alto\" posso dire \"la differenza con il valore medio (quello che viene in effetti ripetuto n volte, almeno nella massimizzazione)\". Mi sono spiegato?
 
 Buona notte

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

No Melkon, mi sa che non è chiaro neanche un po\'. <IMG SRC="images/forum/icons/icon_frown.gif">
 
 <TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD>Quote:<HR></TD></TR><TR><TD><BLOCKQUOTE>
 nella massimizzazione, il valore assoluto della differenza fra due numeri più alto è quello di due numeri uno in un angolo e l\'altro nell\'n-1 esima riga o colonna opposta.
 </BLOCKQUOTE></TD></TR><TR><TD><HR></TD></TR></TABLE>
 Prima di tutto, nella massimizzazione di cosa? E poi, stai dicendo che in ogni matrice la differenza più alta è data da 2 numeri di cui uno in un angolo ed uno in una riga o colonna opposta? Questo è evidentemente falso: prendi una matrice con tutti 0 sul bordo, e tutti 1 nel centro...
 
 <TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD>Quote:<HR></TD></TR><TR><TD><BLOCKQUOTE>
 Questo è lampante
 </BLOCKQUOTE></TD></TR><TR><TD><HR></TD></TR></TABLE>
 No, è falso.
 
 <TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD>Quote:<HR></TD></TR><TR><TD><BLOCKQUOTE>
 se ci fosse un valore per il quale ciò è verificato più vicino, allora non sarebbe una massimizzazione, perchè potrei \"chiudere lì\" la griglia. Però questo valore assoluto vale al massimo n-1, appunto perchè la differenza massima tra due caselle adiacenti è 1, e quindi possiamo finalmente dire che ci sono al più n cifre diverse, da cui consegue necessariamente la tesi.
 </BLOCKQUOTE></TD></TR><TR><TD><HR></TD></TR></TABLE>
 Buio assoluto, non sono riuscito a capire nulla. Ancora, una massimizzazione di cosa? Perdonami, ma dovresti fare lo sforzo di spiegarti meglio.
 
 <TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD>Quote:<HR></TD></TR><TR><TD><BLOCKQUOTE>
 Mi è appena venuta un\'idea per l\'originale, problema n2
 invece di dire \"il valore assoluto della differenza fra due numeri più alto\" posso dire \"la differenza con il valore medio (quello che viene in effetti ripetuto n volte, almeno nella massimizzazione)\". Mi sono spiegato?
 </BLOCKQUOTE></TD></TR><TR><TD><HR></TD></TR></TABLE>
 Per niente. Cos\'è una \"differenza con il valore medio\"? Anche qui, la massimizzazione di cosa?
 
 <TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD>Quote:<HR></TD></TR><TR><TD><BLOCKQUOTE>
 Buona notte
 </BLOCKQUOTE></TD></TR><TR><TD><HR></TD></TR></TABLE>
 Giustappunto.

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

con massimizzazione intendo dire: la configurazione nella quale appaiono il numero più alto di numeri
 
 Quote:
 --------------------------------------------------------------------------------
 
 Questo è evidentemente falso: prendi una matrice con tutti 0 sul bordo, e tutti 1 nel centro...
 
 --------------------------------------------------------------------------------
 
 In questo caso, ci sono meno numeri del massimo consentito (cioè, non è quello che intendo per massimizzazione, forse con il termine sbagliato)
 
 Ora dovrebbe essere tutto più chiaro, no? Comunque scusa Mind, credevo (male) che il termine non facesse problema <IMG SRC="images/forum/icons/icon_confused.gif">

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

<TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD>Quote:<HR></TD></TR><TR><TD><BLOCKQUOTE>
 On 2004-11-13 20:54, Melkon wrote:
 L\'idea è: dato che il legame è più forte e anche negli angoli i due numeri possono differire di al più una cifra, oltre che lungo le righe e le colonne, anche lungo la diagonale al più la variazione è di n numeri. Premettendo che, dato un numero k in alto a sinistra nella griglia, il valore più lontano numericamente è quello più lontano anche geometricamente (e questo posso considerarlo ovvio nella massimizzazione, perchè se ci fosse un valore massimo più vicino (w) potrei chiudere li la griglia bla... bla... bla...
 </BLOCKQUOTE></TD></TR><TR><TD><HR></TD></TR></TABLE>
 
 Oh, e l\'italiano?? Scusate, ma non ce la faccio a starne fuori: provo a ridirlo io in modo comprensibile.
 
 Intervengo sul problema 2 \'facile\' (con i vicini a passo di Re che differiscono di uno).
 
 [@Melkon: guarda che se nelle gare ti esprimi cosi\', Archimede ancora ancora, ma a Cesenatico ti tirano dietro tanti di quegli accidenti da far la siepe a Po... Come consiglio, cerca di sforzarti a enunciare e dimostrare bene... /@Melkon]
 
 Melkon ha bisogno di provare che ci sono al più n valori distinti. Suppongo che tutti sappiamo come si muove un Re degli scacchi...
 
 Dato che, per ipotesi, celle che stanno a passo di Re, differiscono al più di uno, le case di partenza e di arrivo di un Re che si muova di t passi differiscono al più di t. La distanza-Re massima su una scacchiera n x n è chiaramente <=n-1 [ossia, che un Re, partendo da una casa qualunque, può raggiungere qualunque altra casa con non più di n-1 passi; per i pignoli più del sottoscritto: ve lo dimostrate per induzione su n]. Ne segue che la casa massima e la minima della scacchiera differiscono al massimo per n-1 e quindi i valori distinti sono al più n. Principio dei Cassetti e fine. []
 
 Era così improbo da spiegare??
 
 Ciao.
 
 M.[addsig]

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

Ciao, giovani.
 
 Boh, voi dite che il pb. 2 è da IMO? Sarà anche, ma la soluzione sta in otto righe...
 
 Non ve la posto subito, ma ci metto su il carico da undici, chiedendovi di dimostrare il seguente problema, con una tesi ancora più forte:
 
 <TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD>Quote:<HR></TD></TR><TR><TD><BLOCKQUOTE>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 esiste un intero che compare in tutte le traverse o in tutte le colonne.</BLOCKQUOTE></TD></TR><TR><TD><HR></TD></TR></TABLE>
 Alla prox.
 
 M.
 
 
 
 \"My soul is painted like the wings of butterflies
 
 Fairy tales of yesterday will grow but never die\" [ Questo Messaggio è stato Modificato da: marco il 16-11-2004 08:55 ]

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-16 08:55, marco wrote:
 Boh, voi dite che il pb. 2 è da IMO? Sarà anche, ma la soluzione sta in otto righe...
 </BLOCKQUOTE></TD></TR><TR><TD><HR></TD></TR></TABLE>
 Io ho detto che il problema era da allenamento per le IMO (e non un problema da IMO), semplicemente perché qualcuno lo proponeva come allenamento per Archimede... In realtà non ho pensato seriamente a come risolverlo, e so solo che non è da Archimede e non è da Provinciali, forse è un Cesenatico difficile.
 Ti faccio notare però che esistono problemi IMO, anche abbastanza recenti, con soluzioni in molto meno di 8 righe. <IMG SRC="images/forum/icons/icon_smile.gif">

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

Ok, Fly.
 
 Immaginavo un\'obiezione del genere. E\' sempre il solito, annoso problema di valutare quanto è difficile un quesito. Sicuramente la lunghezza della soluzione non è un criterio del tutto affidabile, ma se ESISTE una soluzione breve, allora è quanto meno più, ahem...., probabile che l\'esercizio possa essere facile.
 
 Secondo me gli unici criteri veri (ma, ahime, conoscibili solo a posteriori) sono: la percentuale di soluzioni (su un campione sensato di solutori, evidentemente tarato sul tipo di gara) e il tempo medio di soluzione.
 
 Gli altri criteri sono, alla meglio, un\'approssimazione indicativa del grado di difficoltà.
 
 Per quanto riguarda il presente esercizio, trovo i seguenti indizi di facilità:
 
 - Ho trovato la soluzione senza scrivere, mentre guidavo verso casa (se qualche volta mi incidento per colpa del Forum...). Non è del tutto oggettivo, d\'accordo, ma io son sempre io e sono comunque un campione omogeneo di solutori (statisticamente molto poco significativo) per confrontare esercizi e soluzioni
 - Esiste una soluzione breve
 - Il problema \"si vede\" (cioè non richiede eccessiva intuizione per capire di cosa si sta parlando e il numero di soluzioni \"con le mani\" viste qui lo testimonia)
 - Non si usa niente di truccoso o di avanzato
 - Verosimilmente ci sono ennemila modi di arrivare alla tesi (tra cui, almeno uno elegante e conciso)
 - L\'esercizio originario non è sharp (tanto è vero che ne ho proposto uno più potente) e questo dà più \'margine di manovra\'
 
 La difficoltà, forse, vedendo la serie di posts precedenti, può stare nel fatto che la soluzione \"si vede troppo\" e quindi si può cadere nelle trappole che tu stesso hai segnalato. (\"si vede che è meglio se una riga contiene numeri distinti...\" ma perché mai? \"La configurazione migliore è quella con meno numeri distinti...\" e chi l\'ha detto? \"se ribalto le griglie 2x2...\" e sarebbe...?)
 
 Ma secondo me il problema resta suppergiù nella fascia \"Cesenatico\" (e su questo, siamo concordi).
 
 E poi, scusa, ma se dico che i problemi difficili sono cavolate, il rispetto quadratico medio verso il sottoscritto dovrebbe aumentare, non credi?
 <IMG SRC="images/forum/icons/icon_wink.gif">
 
 Ciao. M.
 
 P.S.: dopo tutto questo sproloquio sulla difficoltà o meno del problema, qualche idea per risolverlo?[addsig]

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

Lol.
 Una volta, in un attimo di delirio, ho pensato che i concorrenti dei paesi IMO-forti esaminassero tutti i possibili insiemi di frasi di senso compiuto, in ordine di lunghezza. Se un insieme di frasi corrispondeva ad un problema+soluzione, se lo studiavano. In questo modo conoscevano già tutti i possibili problemi con soluzione abbastanza corta... Se ci pensi bene, le combinazioni non sono così tante. Io sono quasi convinto che con le disuguaglianze si possa fare una cosa del genere. Scrivi un programma che ti crei tutte le disuguaglianze dimostrabili con al più 37 passaggi \"standard\", tipo AM-GM, coscì-sciuarz, etc, e falle risolvere tutte agli IMO-boys. Alla fine, questi si sogneranno le disuguaglianze di notte, e quando ne vedranno una, reciteranno la soluzione a memoria. Per me lo fanno davvero...
 Ok. Fine delirio. Risolviamo il problema. <IMG SRC="images/forum/icons/icon_smile.gif">

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