Combinatoria
Dato un modo di numerare le caselle di una scacchiera n × n con i numeri
da 1 a $ n^2 $ , si consideri la massima differenza presente fra i numeri di due caselle “vicine”
(dove per vicine s’intende che hanno un lato o un vertice in comune).
Qual e il minimo di tale differenza al variare della numerazione fra le $ (n^2)! $ possibili?
da 1 a $ n^2 $ , si consideri la massima differenza presente fra i numeri di due caselle “vicine”
(dove per vicine s’intende che hanno un lato o un vertice in comune).
Qual e il minimo di tale differenza al variare della numerazione fra le $ (n^2)! $ possibili?
Risposte
non ho provato a risponderti prima perché se la numerazione è arbitraria la risposta è banale, altrimenti ... ?
se si riferisce alla somma di tutte le differenze... allora c'è da specificare!
se si riferisce alla somma di tutte le differenze... allora c'è da specificare!
Premesso che il crossposting è vietato, credo intenda dire che data una numerazione a caso, tra tutte le differenze fra le celle vicine ce n'è una massima. Ora se prendiamo tutte le numerazioni possibili e quindi tutte le differenze massime, qual è la minima tra queste? Io l'ho inteso così ...
sì, grazie axpgn, sono un tantino distratta!
Guarda che io stavo per rispondergli che era di una banalità pazzesca ma poi l'ho riletto ... 
[xdom="@melia"]Carissimo gl630 un piccolo contributo alla soluzione degli esercizi, magari semplicemente con delle considerazioni tue che possono essere giuste o sbagliate non importa, ma che, comunque, ci darebbero un'idea di chi sei e che cosa sei in grado di fare da solo e di conseguenze fino a che punto è possibile spingersi nell'astrazione di alcune soluzioni.
Due righe di presentazione sarebbero gradite.
Inoltre ti comunico che il crossposting è vietato.[/xdom]
Due righe di presentazione sarebbero gradite.
Inoltre ti comunico che il crossposting è vietato.[/xdom]
Io non credo ... non penso si possa andare molto oltre l'otto (sempre che già non sia il minimo o addirittura meno ...)
"axpgn":
Io non credo ... non penso si possa andare molto oltre l'otto (sempre che già non sia il minimo o addirittura meno ...)
Ti riferisci al mio messaggio?
Puoi dettagliare il concetto?
Controesempio
$((1,2,4,6,7),(3,9,10,12,14),(5,11,17,18,20),(8,13,19,22,23),(15,16,21,24,25))$
S.E.&O. ...
Cordialmente, Alex
$((1,2,4,6,7),(3,9,10,12,14),(5,11,17,18,20),(8,13,19,22,23),(15,16,21,24,25))$
S.E.&O. ...
Cordialmente, Alex
Ma la disposizione banale?
12345
678910
...
Per cui il min-max è n+1?
12345
678910
...
Per cui il min-max è n+1?
Allora, secondo me, il minimo non può dipendere da $n$ per un semplice fatto: per quanto $n$ diventi grande, le caselle "vicine" sono sempre otto (già da $n>=3$) quindi "trovato" uno schemino, sufficientemente grande che funzioni una volta, poi lo puoi ripetere quanto vuoi ...
IMHO
Cordialmente, Alex
IMHO
Cordialmente, Alex
Sono d'accordo con la considerazione di axpgn, ma andando avanti la differenza dovrebbe rimanere costante?
con n=3 l differenza massima mi sembra essere 4, con n=4, 5 quindi n+1, però questo va in conflitto con la mia affermazione di prima. Ho le idee confuse ahah
con n=3 l differenza massima mi sembra essere 4, con n=4, 5 quindi n+1, però questo va in conflitto con la mia affermazione di prima. Ho le idee confuse ahah
Sì, come detto, raggiunta una dimensione "sufficiente" la minima tra le differenze massime resterà costante.
Penso questo.
Penso questo.
Mi autosmentisco 
La "distanza" massima tra due caselle di una "scacchiera" $n xx n$ è $n-1$, la differenza massima tra i valori è $n^2-1$; perciò la minima tra le differenze massime non può essere minore di $(n^2-1)/(n-1)=n+1$.
It's ok?
Cordialmente, Alex
La "distanza" massima tra due caselle di una "scacchiera" $n xx n$ è $n-1$, la differenza massima tra i valori è $n^2-1$; perciò la minima tra le differenze massime non può essere minore di $(n^2-1)/(n-1)=n+1$.
It's ok?
Cordialmente, Alex
"axpgn":
Mi autosmentisco
La "distanza" massima tra due caselle di una "scacchiera" $n xx n$ è $n-1$, la differenza massima tra i valori è $n^2-1$; perciò la minima tra le differenze massime non può essere minore di $(n^2-1)/(n-1)=n+1$.
It's ok?
Mmh... Non mi sono chiari i passaggi logici...
@Cordialmente Alex: complimenti
wow! che spettacolare applicazione del principio dei cassetti: come prendere n^2-1 piccioni con n+1 fave.
@dr00ster
credo che la cosa funzioni così:
tratto il caso n=5, ma le considerazioni valgono in generale.
Gli estremi dell'insieme sono 1 e 25, che al "meglio" "distano" di 4 posizioni.
Al "meglio" si intende che per cercare di minimizzare la massima differenza devo tenere il più possibile distanti gli estremi 1 e 25, e questo nella scacchiera 5X5 significa che tra i dyue numeri, AL MASSIMO, ci sono 4 posizioni contigue (nel senso richiesto dal problema cioè con un lato o vertice in comune).
Quindi la differenza 25-1=24 la devo ripartire al meglio tra 4 posizioni. La differenza minima ottenibile la si ha quando sono tutte uguali, cio per 24/4=6.
Questo non prova che che n+1 sia un minimo ma solo che il minimo non può essere più piccolo di questo valore: cioè n+1 è un minorante dell'insieme delle minime differenze massime.
Per chiudere la prova basta trovare una disposizione che realizzi proprio questo valore.
wow! che spettacolare applicazione del principio dei cassetti: come prendere n^2-1 piccioni con n+1 fave.
@dr00ster
credo che la cosa funzioni così:
tratto il caso n=5, ma le considerazioni valgono in generale.
Gli estremi dell'insieme sono 1 e 25, che al "meglio" "distano" di 4 posizioni.
Al "meglio" si intende che per cercare di minimizzare la massima differenza devo tenere il più possibile distanti gli estremi 1 e 25, e questo nella scacchiera 5X5 significa che tra i dyue numeri, AL MASSIMO, ci sono 4 posizioni contigue (nel senso richiesto dal problema cioè con un lato o vertice in comune).
Quindi la differenza 25-1=24 la devo ripartire al meglio tra 4 posizioni. La differenza minima ottenibile la si ha quando sono tutte uguali, cio per 24/4=6.
Questo non prova che che n+1 sia un minimo ma solo che il minimo non può essere più piccolo di questo valore: cioè n+1 è un minorante dell'insieme delle minime differenze massime.
Per chiudere la prova basta trovare una disposizione che realizzi proprio questo valore.
"sprmnt21":
Per chiudere la prova basta trovare una disposizione che realizzi proprio questo valore.
Ma questa l'hai già trovata tu ... "la disposizione banale" ...
E la spiegazione è chiarissima ...
Cordialmente, Alex
Hai premuto il tasto "invia" qualche secondo prima di me
Stavo per scrivere la stessa identica cosa
Stavo per scrivere la stessa identica cosa
Correggo, 3 minuti 
Spiegazione chiarissima
Spiegazione chiarissima
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo