OliForum Matematico

Ecco un problema preso da una "dispensa di matematica olimpionica":
Un castello è composto da sette piani, ognuno con nove stanze disposte 3x3. Un principe
deve entrare da una delle quattro stanze ’centrali’ del piano terra e salvare la principessa
che si trova nella stanza corrispondente all’ingresso dell’eroe ma all’ultimo piano. Il
principe per salvare la principessa deve attraversare tutte le stanze e raccogliere in ognuna
una perla in esse contenute, senza passare due volte per la stessa camera. Sapendo
che da ogni stanza è possibile raggiungere quelle adiacenti, riuscirà il principe a salvare
la principessa?

Credo che sia risolvibile con le colorazioni, ho provato con la solita "a scacchiera" ma non sono giunto a nessuna conclusione.
Ho notato però che esiste un percorso che riempie 2 piani completi e che porta il principe ancora ad una stanza "centrale" (non d'angolo insomma) sul lato adiacente o sul lato opposto alla partenza (basta scegliere un percorso adeguato). Il problema è che il castello ha 7 piani, non 4 o 6.
Infine ho pensato anche a contare i movimenti in xyz, in altezza sarebbero 6+2h con h naturale, ma sul piano la questione si fa più complessa credo.

Dunque, considerando che tu con le colorazioni dici di non aver ottenuto nulla, la mia soluzione è probabilmente sbagliata.
Coloro le caselle centrali dei piani dispari di nero, e le altre di bianco. Nei piani pari faccio il contrario. Così facendo ho che caselle adiacenti hanno colori diversi.
Pertanto ad ogni passo cambia il colore della casella in cui si trova il principe. Facendo un rapido conto, nel palazzo ci sono 31 caselle nere, di cui 30 ancora da percorerre (visto che inizialmente il principe di trova su una casella nera) e 32 caselle bianche. Questo comporta la tesi: infatti se esistesse un percorso lecito devono esserci tante caselle bianche da percorrere quante caselle nere visto che ad ogni passo cambia colore (o al massimo una in meno se le caselle totali fossero state in numero pari)

Grazie! Io avevo colorato così ma poi avevo solo considerato la casella di partenza e arrivo, senza contare le caselle totali. Ho perso di vista una delle cose più semplici