Principe in castello a 7 piani

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Rispondi
MicheleMat
Messaggi: 10
Iscritto il: 26 apr 2014, 12:35

Principe in castello a 7 piani

Messaggio da MicheleMat » 26 apr 2014, 14:14

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.

Triarii
Messaggi: 464
Iscritto il: 18 nov 2010, 21:14

Re: Principe in castello a 7 piani

Messaggio da Triarii » 26 apr 2014, 18:33

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)
"We' Inge!"
LTE4LYF

MicheleMat
Messaggi: 10
Iscritto il: 26 apr 2014, 12:35

Re: Principe in castello a 7 piani

Messaggio da MicheleMat » 26 apr 2014, 19:46

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

Rispondi