Pagina:Matematica in relax.pdf/146

146 Maurizio Codogno

sempre. Le lepri più lontane sono invece su una casella del colore opposto, e quindi i cacciatori possono riuscire a intrappolarle in un angolo.

Post Scriptum

Ecco un altro problema dove la parità è la chiave per la soluzione; in questo caso l’unica vera difficoltà è accorgersi che quella che sembra la strategia più facile (gli inglesi la chiamano greedy, ingorda) non può essere vincente.

•• ••• ••••• ••••••• ••••• ••• ••

53. Il giro dell’isola

Considerate tutte le triplette (incrocio, strada di arrivo, ultima direzione presa). Il loro numero è finito, quindi prima o poi Loris deve per forza ripeterne una. Ma visto che da ogni tripletta si può raggiungere solo una specifica altra tripletta, la prima che capiterà di nuovo sarà quella iniziale.

Post Scriptum

Anche in questo caso abbiamo una soluzione combinatoria non costruttiva. Un matematico direbbe che ha definito uno spazio degli stati tale per cui c’è una funzione univoca e invertibile tra uno stato e l’altro; a questo punto la soluzione segue subito. Il vero problema è trovare il giusto spazio degli stati! Non basta per esempio dire “consideriamo tutti gli incroci, e come ci siamo arrivati”, perché in tal caso non sapremmo se dobbiamo girare a sinistra o a destra una volta arrivati all’incrocio; né tanto meno è sufficiente considerare i soli incroci. Lo spazio degli stati è in genere enorme, e con moltissime dimensioni; ma questo non è un problema per un matematico, perché gli strumenti teorici non si curano della dimensione del problema, almeno fino a che essa è un numero finito.

•• ••• ••••• ••••••• ••••• ••• ••