Disfida Matematica 2007

Soluzione del problema 21

24.
La ronda.    Supponiamo di avere una griglia $ a\times b$ . Intanto la lunghezza complessiva delle strade è

$\displaystyle a(b+1)+(a+1)b=2ab+a+b\,.
$

Supponiamo poi, come nel caso particolare dell'esercizio, che $ a$ sia dispari e $ b$ pari. Il problema del percorso minimo riguarda in particolare i nodi della griglia in cui confluiscono un numero dispari di strade (in questo caso tutti gli incroci sul perimetro tranne i quattro vertici, in cui confluiscono tre strade). Almeno una strada di questi nodi deve essere infatti percorsa più di una volta. Conviene quindi unire tra loro a coppie tali nodi con un percorso minimo. Un possibile modo di unirli è mostrato nella prima figura; da qui si evince che un tratto di strada pari ad almeno $ a+b$ deve essere percorso due volte. La lunghezza totale del percorso del Primo Ministro deve essere pari ad almeno

$\displaystyle 2ab+a+b+a+b= 2(ab+a+b)\,.
$

Resta solo da dimostrare che questa stima è ottimale, ovvero che esiste almeno un percorso lungo $ 2(ab+a+b)$ . Tale percorso, nel caso $ a=7$ e $ b=4$ ma facilmente generalizzabile, è mostrato nella seconda figura. Risulta quindi che la risposta è $ 2(64\cdot 37+64+37)$ , ovvero \fbox{4938} . Nota: tale soluzione vale anche nel caso $ a,b$ entrambi pari, mentre nel caso $ a,b$ entrambi dispari si può trovare un percorso lungo $ 2(ab+a+b-1)$ .
\includegraphics[height=10cm]{griglia}




DMF Web 2007-03-29