Soluzione all'enigma 63, proposto da Luca B. il 6 febbraio 2006

La stella di Napoleone (enigma063.pdf)

Ecco la soluzione proposta da Stefano.
Intanto direi che è' possibilissimo disporre 9 pedine su altrettanti punti lasciandone uno solo scoperto. Per vederlo io ho fatto così.
Beh, ovviamente, 9 punti è il massimo in cui posso sperare: per come è concepito il gioco posso occupare un punto solo partendo da un punto libero, pertanto alla fine un punto deve necessariamente restare scoperto.
Intanto ho trasformato la stella in un altro grafo in questo modo: come vertici utlizzo gli stessi punti, ma congiungo tra di loro due punti se e soltanto se è possibile, partendo da uno dei due punti deporre una pedina sull'altro. Quello che ottengo è il seguente grafo (un po' di "ASCII-art"):
a ----- g ----- d ----- l ----- b
| |
| |
i ----- c ----- f ----- e ----- h
Evidentemente il grafico è assolutamente "simmetrico" (se fossi un ASCIIartista un po' più bravo avrei disposto i punti su una circonferenza... ;-)), nel senso che la situazione non cambia partendo da uno qualsiasi dei vertici, quindi tanto vale partire dal vertice "a" e andare a occupare, diciamo, il vertice "g", ottenendo:
a (g) d ----- l ----- b
| |
| |
i ----- c ----- f ----- e ----- h
dove ho rimosso i due lati uscenti da "g" e ho messo "g" stesso tra parentesi perché ormai "g" è occupato dalla pedina e pertanto da lui non si può più partire per occupare altri punti.
L'osservazione è che il grafo qui sopra è connesso, ovvero a partire da un qualsiasi punto posso raggiungerne un qualsiasi altro, e questo è quello che garantisce che, almeno teoricamente, posso rimanere con un solo punto. Se infatti il grafo non fosse connesso e fosse formato da due parti "staccate", visto che i punti da una parte non possono "dialogare" con i punti dall'altra, alla fine nella migliore delle ipotesi dovrei avere *due* punti scoperti, uno in ciascuno dei due pezzi di grafo (e analogamente se i pezzi fossero più di due). Questo suggeriesce anche la strategia da adottare: cercare di fare in modo di non "sconnettere" il grafo, ovvero di lasciarlo sempre di un unico pezzo. Per fare questo ad ogni passo ho solo due mosse possibili, per esempio nel caso in esame devo o occupare "d" (partendo da "l") o occupare "a" (partendo da "i"): ogni altra mossa mi spezza il grafo in piu' pezzi. La strategia vincente dunque è (per esempio):
a --> g
l --> d
b --> l
h --> b
e --> h
f --> e
c --> f
i --> c
a --> i
E questo è quanto!
Ma si può anche ricavare qual è la *peggior* strategia possibile, ovvero quella che mi lascia con più punti scoperti, ovvero quella che sconnette maggiormente il grafo... direi che è questa:
a --> g
d --> l
b --> h
e --> f
c --> i
e ora non posso più muovere... quindi almeno 5 pedine riesco sempre a posizionarle e queste 5 sono necessariamente le 5 centrali, altrimenti ho sempre almeno ancora una mossa da fare e posso aggiungerne un'altra.