Gnomi

[axpgn]

Dopo i sofisti, gli gnomi

Ho tre quesiti basati su questi personaggi ...

Nel primo, gli gnomi (tanto per cambiare ) o mentono sempre o dicono sempre la verità e sappiamo anche che in questo gruppo ce ne sono di entrambe le tipologie.
Sono sedici in tutto e si dispongono su una scacchiera dalle dimensioni $4 xx 4$, uno per cella.
Ognuno di loro dice: "Tra i miei vicini, i bugiardi sono tanti quanto i sinceri".
Per vicini si intende quelli "ortogonalmente adiacenti" ovvero che hanno in comune un lato della cella.
Quanti bugiardi ci sono?

Nel secondo non sappiamo se gli gnomi siano bugiardi o sinceri ma di sicuro sono educati e gentili
Nove gnomi si posizionano su una scacchiera dalle dimensioni $3 xx 3$, uno per cella e poi salutano ogni loro vicino (ortogonalmente adiacente ).
Ripetono questa procedura per tre volte.
Provare che non tutte le coppie riescono a salutarsi.

Nell'ultimo abbiamo una scacchiera dalle dimensioni $7 xx 7$ su ogni cella della quale c'è uno gnomo.
Per ogni coppia di gnomi le cui celle condividono un lato (ortogonalmente adiacenti ), la lunghezza delle loro barbe differisce non più di un pollice.
Successivamente prendiamo gli gnomi e li facciamo sedere attorno ad un tavolo (rotondo).
Mostrare che è possibile farlo in modo tale che per ogni coppia che siede vicina, le loro barbe differiscono per non più di un pollice.


Cordialmente, Alex

[dan952]

Anche gli gnomi adesso

1)

|_|B|B|_|
|B|_|_|B|
|B|_|_|B|
|_|B|B|_|

Gli gnomi indicati con B sono bugiardi perché hanno 3 gnomi adiacenti e quindi non si possono avere tanti gnomi sinceri quanti bugiardi da cui segue che anche quelli negli angoli sono bugiardi perché hanno 2 gnomi bugiardi adiacenti

|B|B|B|B|
|B|_|_|B|
|B|_|_|B|
|B|B|B|B|

Quelli rimanenti sono sinceri.

[axpgn]

Buona la prima!


Cordialmente, Alex

[dan952]

Il 3) sì tratta di collegare le celle della scacchiera ritornando al punto iniziale senza mai passare due volte per una stessa casella e non muovendosi diagonalmente. Da ieri che provo ma niente...

[axpgn]

@dan95

Per il 3) non ho la soluzione ma l'autore dice che quanto stai facendo sarebbe una facile soluzione su una scacchiera $8 xx 8$ ma non su una $7 xx 7$, difatti un ciclo del genere in questo caso non esiste.
L'autore sostiene che occorre trovare un'altra strada.
Ipse dixit

Cordialmente, Alex

[dan952]

Posso tagliare la barba?

[dan952]

$ {: ( 0, 1 , 2 , 3 , 4 , 5 , 6 ),( 1 , 2 , 3 , 4 , 5 , 6 , 7 ),( 2 , 3 , 4 , 5 , 6 , 7 , 8 ),( 3 , 4 , 5 , 6 , 7 , 8 , 9 ),( 4 , 5 , 6 , 7 , 8 , 9 , 10 ),( 5 , 6 , 7 , 8 , 9 , 10 , 11 ),( 6 , 7 , 8 , 9 , 10 , 11 , 12 ) :} $

Ogni numero indica quanto "al più" è lunga in pollici la barba rispetto allo gnomo in alto a sinistra indicato con lo 0. Esiste un cammino dove ci si muove anche in diagonale l ho trovato ma non so disegnarlo qui...

[dan952]

[axpgn]

Ma chi ti garantisce che il tuo percorso valga per qualsiasi disposizione?
Per esempio, mi sono inventato questo schema per cui il tuo percorso non vale più quindi cosa fai?
Cerchi un percorso per ogni possibile schema?

Cordialmente, Alex

[dan952]

Sapevo che non ti avrebbe convinto... perché non convinceva neanche me...

Però hai notato che ci sono gnomi "diagonalmente" vicini, ovvero gnomi disposti diagonalmente l'uno all'altro con non più di un pollice di differenza.

Questo in teoria andrebbe dimostrato che esiste almeno una coppia diagonalmente vicina e questo permetterebbe la costruzione del cammino anche in una scacchiera 7×7

[dan952]

Consideriamo un quadrato 3x3 contenuto all'interno del quadrato 7x7 come nell'immagine




e sia $l$ la lunghezza della barba dello gnomo al centro.

Possono presentarsi queste tre tipi di configurazioni all'interno di questo quadrato:


$ {: ( \ast , l \pm 1 , \ast ),( l\pm 1 , l , l \pm 1 ),( \ast , l \pm 1 , \ast ) :} $




$ {: ( \ast , l \pm 1 , l ),( l\pm 1 , l , l \-/+ 1 ),( l , l -/+ 1 , \ast ) :} $



$ {: ( l , l -/+ 1 , l ),( l \pm 1 , l , l \pm 1 ),( l , l -/+ 1 , l ) :} $

In questa ultima configurazione nella cella vicina a quella in alto a destra deve esserci $l \pm 1$.

$ {: ( l , l -/+ 1 , l, l\pm 1 ),( l \pm 1 , l , l \pm 1,l \or l\pm 2),( l , l -/+ 1 , l, \ast) :} $


In tutte e tre le configurazioni è possibile costruire un cammino nella scacchiera 7×7 passante anche solo una volta per due gnomi diagonalmente vicini.








[nota]Il simbolo $-/+$ indica - o +.[/nota]

[axpgn]

Premesso che non mi è chiarissimo ...

(le situazioni sono un po' più di tre ma soprattutto come fai a far discendere, in modo certo, dal fatto che si possa fare una mossa in diagonale la conclusione che esista effettivamente un percorso?
Voglio dire, sappiamo fin dall'inizio che esiste sempre una soluzione ma andrebbe esplicitata quale è )

... rimane ancora aperto il secondo punto ...


Cordialmente, Alex

[axpgn]

Per il secondo punto ...

Affinché ogni gnomo saluti tutti gli altri compagni, ognuno deve salutare $8$ gnomi.
In una griglia $3 xx 3$, gli gnomi negli angoli salutano solo altri due gnomi, quelli intermedi sul lato ne salutano $3$ e quello in centro ne saluta $4$.

Ora, dopo la prima disposizione avremo quattro gnomi che ne hanno salutato altri due, quattro gnomi che ne hanno salutati tre e uno solo che ne ha salutati quattro.
Nella seconda disposizione possiamo mettere quest'ultimo in un angolo (come pure nella terza disposizione ed è a posto avendone salutati $8$) mentre possiamo disporre gli gnomi d'angolo uno al centro e tre sugli intermedi e i quattro intermedi negli angoli.
A questo punto ci sono sei gnomi che hanno salutato cinque altri vicini e per giungere all'obiettivo dovremmo posizionarli tutti e sei fuori dagli angoli ma purtroppo ci sono solo cinque posti disponibili ...

Cordialmente, Alex

[dan952]

@Alex ci penso domani...

[axpgn]

A cosa?

[dan952]

Al terzo punto... Perché tu dici che le configurazioni sono di più ma mi sfugge adesso quali siano le altre.

[axpgn]

Intendevo dire che a mio parere hai ipersemplificato la situazione (sia per le caselle adiacenti ortogonalmente sia per quelle diagonalmente ma anche per la posizione dei blocchi, non sono tutte equivalenti) ma il dubbio (mio) principale riguarda il perché da una possibile mossa in diagonale discenda sicuramente l'esistenza di un percorso compatibile con le richieste.
Io penso che andrebbe esplicitato o comunque esplicitata la sua costruzione.

[dan952]

Cammino configurazione 1




Cammino configurazione 2






Cammino configurazione 3

[axpgn]

Tutta notte?

[dan952]

Diciamo che ho fatto numerosi tentativi