Salve a tutti, dilettandomi con un po di matematica mi sono imbattuto in un esercizio di ammissione alla Scuola Normale nel 2021 su cui non riesco a metter mano. A seguire il testo.
Una pedina si può muovere su di una scacchiera di dimensioni infinite le cui caselle sono mappate dalla coppia di indici $ (a,b) $.
Ad ogni turno la mossa possibile può essere in orizzontale o verticale e dalla generica casella $ (a,b) $ si può balzare in $ (a+1,b);(a-1,b);(a,b+1);(a,b-1) $.
Le singole mosse hanno rispettivamente un costo C di:
$ 2a-2b-1;2a-2b+1;2a-2b-1;2a-2b+1 $.
Se $ C>=0 $ occorre sborsare $ C $ Euro per effettuare la mossa,mentre se $ C<0 $ muovendo la pedina si ricevono $|C|$ Euro. Sono vietate tutte le mosse il cui costo è strettamente maggiore di ciò che si ha a disposizione ad inizio turno. Il numero di Euro non può mai diventare negativo. Si inizia con la pedina nella casella $ (5,1) $ ed $ N $ Euro a disposizione.
Determinare:
1) il valore minimo di $ N $ che permette di arrivare in $ (0,0) $
2) il valore minimo di $ N $ che permette di arrivare in $ (1,5) $
Un saluto ed un GRAZIE a quanti volessero cimentarsi nella risoluzione.
A.
Ps: ho trovato da qualche parte un algoritmo che ha a che fare con la programmazione dinamica e sembra essere adatto a problemi di tal tipo....