Disfida Matematica 2007

Soluzione del problema 21

24.

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

$$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

$$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 . 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)$ .