Data una scacchiera $n\times n$ pongo sulle caselle tutti i numeri da $1$ a $n^2$.
Determinare il maggiore $ d\in\mathbb{N} $ tale che comunque metto i numeri ce ne saranno 2 in caselle adiacenti (con un lato in comune) con differenza maggiore o uguale a $d$.
p.s. dato che è famoso forse è già passato dal forum
Re: Minima differenza su una scacchiera
Inviato: 06 mar 2011, 13:10
da staffo
Io ho ragionato così: prendo una casella in un angolo, poi scrivo le due adiacenti con differenza minore possibile (1,2) poi prendo le tre adiacenti a quest'ultime due, che avranno diferenza con quella adiacenti di (2,3), vado avanti così facendo diagonale per diangonale, fino ad ottenere la differenza massima per la diagnale n-esima, in cui appunto le differenze sono (n-1,n),e quindi la differenza minima per qualsiasi configurazione è d=n.
EDIT: questa è la configurazione miglore possibile per minimizzare le differenza proprio perchè associa alle caselle adiacenti quelle con il numero più vicino possibile (che con altre configurazioni non sarebbe possibile)
Re: Minima differenza su una scacchiera
Inviato: 06 mar 2011, 13:58
da dario2994
staffo ha scritto: questa è la configurazione miglore possibile per minimizzare le differenza proprio perchè associa alle caselle adiacenti quelle con il numero più vicino possibile (che con altre configurazioni non sarebbe possibile)
Tu hai mostrato solo che $d\le n$ perchè quanto ho citato è un poco troppo vago
Re: Minima differenza su una scacchiera
Inviato: 07 mar 2011, 18:27
da Anér
dario2994 ha scritto:p.s. dato che è famoso forse è già passato dal forum
È davvero famoso? Perché assomiglia molto al Romanian 6 di quest'anno, è forse una tua variante di quel problema?
Re: Minima differenza su una scacchiera
Inviato: 07 mar 2011, 21:06
da dario2994
Anér ha scritto:
dario2994 ha scritto:p.s. dato che è famoso forse è già passato dal forum
È davvero famoso? Perché assomiglia molto al Romanian 6 di quest'anno, è forse una tua variante di quel problema?
È il romanian 6 che è una variante di questo
Re: Minima differenza su una scacchiera
Inviato: 08 mar 2011, 11:46
da Anér
Ed effettivamente questo si faceva più o meno come il Romanian 6 (anche se il Romanian 6 era più difficile soprattutto per l'esempio). Metto la soluzione a un problema vagamente più generale, e cioè anziché una scacchiera nxn ne considero una axb, con a maggiore o uguale a b e b>1. Questa scacchiera contiene i numeri da 1 ad ab. Bisogna sempre trovare il massimo d tale che ci siano sempre due caselle adiacenti con differenza maggiore o uguale a d. Metto la soluzione nascosta così se qualcuno vuole provare da solo può farlo.
Testo nascosto:
La risposta è b, ossia esistono sempre due caselle adiacenti contenenti numeri che differiscono almeno di b, ma non sempre ci sono due caselle adiacenti con numeri che differiscono per almeno b+1.
Se sulla prima riga scrivo in ordine i numeri da 1 a b, sulla seconda quelli da b+1 a 2b, e così via, fino a scrivere sull'ultima i numeri da ab-b+1 ad ab, ho che la differenza tra due caselle adiacenti in orizzontale è sempre 1, mentre quella tra due caselle adiacenti in verticale è sempre b. Dunque esiste un caso senza differenze maggiori di b.
Se prendo invece una configurazione qualsiasi e mi armo di un bel pennarello rosso, posso colorare nell'ordine i numeri 1, 2, 3, andando avanti fino a quando non mi accorgo che su tutte le righe o su tutte le colonne c'è almeno un numero rosso. Appena succede questo mi fermo e chiamo h l'ultimo numero colorato di rosso, con $ b\leq h<ab $. Diciamo che una "fila" è una riga se alla fine della colorazione abbiamo una casella rossa su ogni riga, ed è una colonna altrimenti; ovvero alla fine della colorazione abbiamo almeno una casella rossa su ogni fila. Tuttavia non possiamo avere una fila tutta rossa, altrimenti se h sta su quella fila allora non era necessario colorarlo, e se h non sta su quella fila dovevo fermarmi prima perché avevo già una casella rossa su tutte le "non file". Avendo almeno una casella bianca su ogni fila ho almeno un'adiacenza tra una rossa e una bianca per ogni fila, dunque almeno b adiacenze. Allora tra queste adiacenze ce n'è una che usa una casella rossa con un numero minore o uguale a h-b+1; la casella bianca invece ha senz'altro un numero maggiore o uguale a h+1, per cui c'è una differenza di almeno b.
Re: Minima differenza su una scacchiera
Inviato: 08 mar 2011, 17:16
da dario2994
Anér ha scritto:Ed effettivamente questo si faceva più o meno come il Romanian 6 (anche se il Romanian 6 era più difficile soprattutto per l'esempio). Metto la soluzione a un problema vagamente più generale, e cioè anziché una scacchiera nxn ne considero una axb, con a maggiore o uguale a b e b>1. Questa scacchiera contiene i numeri da 1 ad ab. Bisogna sempre trovare il massimo d tale che ci siano sempre due caselle adiacenti con differenza maggiore o uguale a d. Metto la soluzione nascosta così se qualcuno vuole provare da solo può farlo.
Testo nascosto:
La risposta è b, ossia esistono sempre due caselle adiacenti contenenti numeri che differiscono almeno di b, ma non sempre ci sono due caselle adiacenti con numeri che differiscono per almeno b+1.
Se sulla prima riga scrivo in ordine i numeri da 1 a b, sulla seconda quelli da b+1 a 2b, e così via, fino a scrivere sull'ultima i numeri da ab-b+1 ad ab, ho che la differenza tra due caselle adiacenti in orizzontale è sempre 1, mentre quella tra due caselle adiacenti in verticale è sempre b. Dunque esiste un caso senza differenze maggiori di b.
Se prendo invece una configurazione qualsiasi e mi armo di un bel pennarello rosso, posso colorare nell'ordine i numeri 1, 2, 3, andando avanti fino a quando non mi accorgo che su tutte le righe o su tutte le colonne c'è almeno un numero rosso. Appena succede questo mi fermo e chiamo h l'ultimo numero colorato di rosso, con $ b\leq h<ab $. Diciamo che una "fila" è una riga se alla fine della colorazione abbiamo una casella rossa su ogni riga, ed è una colonna altrimenti; ovvero alla fine della colorazione abbiamo almeno una casella rossa su ogni fila. Tuttavia non possiamo avere una fila tutta rossa, altrimenti se h sta su quella fila allora non era necessario colorarlo, e se h non sta su quella fila dovevo fermarmi prima perché avevo già una casella rossa su tutte le "non file". Avendo almeno una casella bianca su ogni fila ho almeno un'adiacenza tra una rossa e una bianca per ogni fila, dunque almeno b adiacenze. Allora tra queste adiacenze ce n'è una che usa una casella rossa con un numero minore o uguale a h-b+1; la casella bianca invece ha senz'altro un numero maggiore o uguale a h+1, per cui c'è una differenza di almeno b.
Praticamente uguale alla mia... io mi fermavo quando avevo una fila colorata tranne che per una casella...
