SNS Esercizio 1 2021

[Gandalf73]

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

[Quinzio]

Questo esercizio era gia' comparso su questo forum tempo fa, ma vado a memoria.
Forse cercando con delle parole chiave si riesce a ri-trovarlo.

[hydro]

Testo nascosto, fai click qui per vederlo

Quando si è sopra la retta \(r:b=a-1/2\), le mosse verso sinistra e verso il basso hanno costo negativo. Notiamo che da qualsiasi punto di ordinata positiva che sta sopra $r$ si può raggiungere $(0,0)$ solo con mosse verso sinistra e verso il basso. Siccome $(0,0)$ sta sopra la retta $r$, ad un certo punto dovrò superarla. Sia $P=(x_P,y_P)$ il primo punto che visito sopra la retta $r$. Per arrivare a $P$ devo fare almeno $|5-x_P|$ mosse verso sinistra. Ma le mosse verso sinistra che costano meno sono, a parità di ascissa, quelle con ordinata più alta. Di conseguenza nessuna strategia con $y_P<1$ può essere ottimale, perchè la strategia di fare $4$ passi verso sinistra subito, da $(5,1)$, costa sicuramente meno.

Ne consegue che il modo più economico per arrivare in $(0,0)$ è il modo più economico per arrivare sopra ad $r$ ad un punto di ordinata positiva. Ora, muoversi verso destra non ha mai senso perchè poi per arrivare sopra ad $r$ dovrei pagare almeno tanto quanto avrei pagato senza muovermi. Similmente muoversi verso il basso non ha mai senso, perchè poi le mosse verso sinistra costano di più, quindi per arrivare sopra ad $r$ dovrei pagare almeno tanto quanto avrei pagato senza muovermi. Quindi devo valutare solo mosse verso l'alto e verso sinistra. In meno di $4$ mosse non posso arrivare sopra ad $r$. D'altro canto a parità di ascissa muoversi verso l'alto costa meno che muoversi verso sinistra; possiamo concludere allora che la strategia ottimale è fare $4$ passi verso l'alto da subito, poi $5$ verso sinistra e $5$ verso il basso, pagando se non ho sbagliato i conti $16$ euro.

[Gandalf73]

Ciao a tutti e grazie per la risposta.
@Quinzio: ho cercato in lungo ed in largo ma niente non sono riuscito a scovarlo.
@hydro: si corretto. Un'altra soluzione propostami (che poi risulta praticamente sovrapponibile) è quella di chiamare $ P=a-b $ e notare che il costo $ C = 2P+-1 $. Da lì poi tutti i ragionamenti sono similari.
Assumo come scontato il considerarsi vantaggiosa quella mossa che permette "l'accredito" anzichè "l'addebito" della funzione $ C $, corretto?Quello che mi manda in confusione è la funzione Costo "positiva" e "negativa".
Io non debbo preparare l'esame ma..da vecchio Ing. Ele. che ha ripreso i libri per fare un salto verso Fisica..cerco di tenermi allenato con questi esercizi che sembrano "fattibili" ma che non lo sono affatto per uno come me, che necessita di togliere della "polvere" per riprendere un "corretto" approccio alla materia .
Un saluto ed ancora grazie.
ps tutto il ragionamento è relativo al caso a) ossia al costo minimo per arrivare in $ (0,0) $ vero?

[Gandalf73]

Mi scuso per lo scivolone di cui mi sono accorto.
Nel testo del quesito ho riportato il costo della prima e della quarta mossa in modo invertito rispetto all'originale.
Quest'ultimo è quindi:
costo della prima mossa $ 2b-2a-1 $,
costo della quarta mossa $ 2b-2a+1 $. Le altre sono corrette.
Ovviamente la soluzione proposta risulta cambiata in alcuni punti.
Un saluto e perdonatemi ancora lo svarione.
A.