SNS Esercizio 1 2021

[Gandalf73]

Salve a tutti ,
sto svolgendo alcuni esercizi degli anni passati dei tests della scuola normale .
Di quello che vi posto non ho trovato nel web alcuna soluzione se non qualche indicazione che arriva (per problemi analoghi) dalla "programmazione dinamica".
A seguire il testo (scusandomi in anticipo se avessi sbagliato sezione).
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 $ € per effettuare la mossa,mentre se $ C<0 $ muovendo la pedina si ricevono $ |C| $ € . Sono vietate tutte le mosse il cui costo è strettamente maggiore di ciò che si ha a disposizione ad inizio turno. Ad ogni turno il numero di € non può mai diventare negativo. Si inizia con la pedina nella casella $ (5,1) $ ed $ N $ € 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

[Stef2008]

Ecco la mia soluzione (sperando che sia corretta)

Testo nascosto:

Definaimo la quantità $P_{(a,b)}=a-b$. Notiamo che ogni mossa su una coppa $(a,b)$ ha un costo di $2P_{(a,b)}±1$. Notiamo che ogno mossa fa cambiare il peso di esattamente 1 (può però sia aumentare che diminuire di 1). La posizione finale ha Peso zero (in quanto i due valori sono entrambi 0). Per continuità discreta, essendo partiti con $P_{(5,1)}=4$, avrò avuto almeno una posizione di Peso 4, di Peso 3, Peso 2, Peso 1 (perchè la variazione è 1, quindi avrò tutti i valori "in mezzo"). Il costo è minimo se ho fatto solo questo tipo di mosse prima di arrivare a Peso 0 (quindi facendo solo mosse che diminuiscono il peso). La mossa meno costosa che fa diminuire il peso è quella da $(a,b) $ a $(a, b+1)$. Usiamola fino ad avere peso 0.
La somma dei costi è $2×4-1+2×3-1+2×2-1+2-1= 16 $. Osserviamo che abbiamo scelto la mossa di sopra invece della mossa $(a-1,b)$ perchè è più economica quella usata sopra perchè l'addendo 1 è negativo. Ora siamo in una posizione con peso 0, in partcolare in $(5,5)$. Ora abbiamo capito che abbiamo bisogno di almeno 16 euro. Dimostriamo che sono sufficienti. Facciamo un altra mossa del tipo $(a,b+1)$ e arriviamo allo posizione $(5,6)$ guadagnando un euro. Facciamo ora mosse del tipo $(a-1,b)$ fino ad arrivare a $(0,6)$ (osserviamo che tutte queste mosse non fanno perdere soldi, ma al contrario li fanno guadagnare). Facciamo ora tutte mosse del tipo $(a,b-1)$ fino ad arrivare a $(0,0)$ (anche queste hanno tutte costo negativo, quindi non possiamo sforare la cifra che abbiamo). Quindi 16 euro bastano e sono necessari.
Per il punto b), $(1,5)$, ha peso negativo, quindi prima sarà stato raggiunto il peso 0. Quindi anche qui 16 sono necessari, in modo simile alla prima si può dimostrare che sono sufficienti.


Fammi sapere se ci sono errori. Chiedo scusa fosse poco chiara in quanto ho scritto velocemente.

[Gandalf73]

Ciao carissimo e sono io a scusarmi per aver risposto in ritardo ma sono riuscito solo ora a metterci mano per analizzarla.
Costruisci una funzione "peso" che affianchi a quella "costo" e ti muovi con quella per capire in modo lampante dove c'è la perdita e dove il ricavo.
Prendi come riferimento il "peso" zero perchè rappresenta la "condizione" di minimo per la funzione costo se non ho capito male.
Ossia da li si inizia a guadagnare o il costo diviene negativo e blocca tutto il "processo"..corretto?
Si passa poi ai meri valori numerici.
Per il caso (1,5) ancora non ho ben chiaro il ragionamento se non che in quel punto il peso "sarebbe" negativo per cui ci si arriva (rispettando le regole del gioco ) solo attraverso passaggi che implichino un "guadagno" maggiore o uguale ad 8.Corretto?
Un saluto ed ancora grazie per il preziosissimo aiuto
A.

[Stef2008]

Prendi come riferimento il "peso" zero perchè rappresenta la "condizione" di minimo per la funzione costo se non ho capito male.

Esatto, infatti la coppia $(0,0)$ ha peso $0$, quindi per arrivare a tale posizione bisogna arrivare a peso $0$, e per fare questo bisogna spendere almeno il numero di monete calcolato.

Ossia da li si inizia a guadagnare o il costo diviene negativo e blocca tutto il "processo"..corretto?

Sì, dopo essere arrivati alla posizione $(5,5)$, che ha peso 0, passiamo alla posizione $(5,6)$ con guadagno di un euro. Da lì le mosse descritte portano sempre ad agire su posizione con peso negativo che fanno sempre guadagnare. Questo fino ad arrivare a alla posizione finale $(0,0)$. Quindi gli unici soldi di cui abbiamo avuto bisogno sono quello per arrivare a una posizione di peso 0

Per il caso (1,5) ancora non ho ben chiaro il ragionamento se non che in quel punto il peso "sarebbe" negativo per cui ci si arriva (rispettando le regole del gioco ) solo attraverso passaggi che implichino un "guadagno" maggiore o uguale ad 8.Corretto?

Non mi è del tutto chiara la domanda... scrivo un po' il procedimento sperando che si chiaro.
Per il caso $(1,5)$, noi partiamo sempre da $(5,1)$ e vogliamo arrivare a $(1,5)$. Osserviamo che $(1,5)$ ha peso negativo, mentre noi partiamo da $(5,1)$ che ha peso positivo. Dato che una mossa fa variare il peso di un unità; noi partiamo da peso $4$ e dobbiamo arrivare a $-4$. Quindi avremmo raggiunto tutti i pesi in mezzo (perchè il peso varia a uno alla volta). Anche lo 0 è stato raggiunto, ma per raggiungere Peso 0 serve almeno il valore calcolato nel punto $ (a) $ (che mi pare fosse 16). Questi sono sufficienti in quanto dopo essere arrivati alla posizione $(5,6)$ in modo analogo al punto $(a)$, facciamo mosse che portano in sequenza a $(4,6),(3,6),...,(1,6),(1,5)$. Tutte queste posizioni hanno peso negativo (quindi c'è guadagno nel fare le mosse). Quindi il numero minimo di monete iniziali $N$ è 16 € che sono necessari e sufficienti in entrambi i casi: (a) e (b).

Un saluto ed ancora grazie per il preziosissimo aiuto.

Di nulla, è stato un piacere. Un saluto

[FraGhila]

Salve a tutti,
mi sto preparando per sostenere l'esame di ammissione della SNS e ho trovato questo post cercando la soluzione di questo esercizio. Esaminando la soluzione di Stef2008 credo di aver trovato un errore ma forse ho capito male io. Nella soluzione, Stef2008 ha descritto il percorso per andare dal punto (5, 1) al punto (0, 0):

La mossa meno costosa che fa diminuire il peso è quella da (a,b) a (a,b+1). Usiamola fino ad avere peso 0.La somma dei costi è 2×4−1+2×3−1+2×2−1+2−1=16. Osserviamo che abbiamo scelto la mossa di sopra invece della mossa (a−1,b) perchè è più economica quella usata sopra perchè l'addendo 1 è negativo. Ora siamo in una posizione con peso 0, in partcolare in (5,5). Ora abbiamo capito che abbiamo bisogno di almeno 16 euro. Dimostriamo che sono sufficienti. Facciamo un altra mossa del tipo (a,b+1) e arriviamo allo posizione (5,6) guadagnando un euro. Facciamo ora mosse del tipo (a−1,b) fino ad arrivare a (0,6) (osserviamo che tutte queste mosse non fanno perdere soldi, ma al contrario li fanno guadagnare). Facciamo ora tutte mosse del tipo (a,b−1) fino ad arrivare a (0,0) (anche queste hanno tutte costo negativo, quindi non possiamo sforare la cifra che abbiamo). Quindi 16 euro bastano e sono necessari.

Questo percorso, se ho capito bene il testo, dovrebbe essere quello tracciato in nero nell'immagine allegata (accanto a ogni freccia rappresentante una mossa è scritto il relativo costo), giusto? Questo percorso però necessita di un quantitativo di euro iniziale N = 38, mentre il percorso tracciato in rosso richiede solo N = 28 euro. Non mi è chiaro quindi come possano bastare N = 16 euro per arrivare dal punto (5, 1) al punto (0, 0).

Inoltre non ho capito il seguente passaggio:

Il costo è minimo se ho fatto solo questo tipo di mosse prima di arrivare a Peso 0 (quindi facendo solo mosse che diminuiscono il peso).

Infatti dato che il costo di una mossa dipende sia dal peso del punto da cui parte sia dalla direzione della mossa stessa (in particolare il costo C di una mossa da un punto M in una certa direzione è -C', dove C' è il costo di una mossa sempre dal punto M ma nella direzione opposta), non è ovvio che un percorso in cui ogni mossa diminuisce il peso (ammesso che esista) sia anche il percorso meno costoso. Io all'inizio avevo ipotizzato che il percorso più corto fosse anche quello che richiede una minor quantità di euro iniziale e sperimentando un po' con le regole del gioco non sono riuscito a trovare controesempi, anzi sono stato portato a ipotizzare che il costo totale di un percorso dal punto M al punto N dipenda esclusivamente dalle coordinate di M e N e dalla lunghezza del percorso (intesa come numero di mosse del percorso stesso), anche se non sono ancora riuscito a dimostrarlo formalmente.
Ripeto che potrei semplicemente essermi perso qualche punto chiave, quindi Stef2008 ti sarei molto grato se riuscissi a spiegarmi questi due passaggi. Grazie mille per l'aiuto, un saluto.

[Stef2008]

Questo percorso, se ho capito bene il testo, dovrebbe essere quello tracciato in nero nell'immagine allegata (accanto a ogni freccia rappresentante una mossa è scritto il relativo costo), giusto? Questo percorso però necessita di un quantitativo di euro iniziale N = 38, mentre il percorso tracciato in rosso richiede solo N = 28 euro. Non mi è chiaro quindi come possano bastare N = 16 euro per arrivare dal punto (5, 1) al punto (0, 0).

Ciao, comincio a chiederti una curiosità, che programma hai usato per fare la figura, perchè mi piace molto come è venuta .
Ti confesso però che alcune cose che dici non mi sono chiare (credo che siano errate, poi magari sono io ad essere in errore). Ad esempio dal disegno sembra che secondo te per andare da $(0,6)$ a $(0,5)$ si spendino 13 monete... tuttavia il costo è $2a-2b+1=2×0-2×6+1=-11$ quindi il costo è negativo (guadagni soldi)... cosa analoga per le mosse successive...

Inoltre non ho capito il seguente passaggio:

Il costo è minimo se ho fatto solo questo tipo di mosse prima di arrivare a Peso 0 (quindi facendo solo mosse che diminuiscono il peso).

Infatti dato che il costo di una mossa dipende sia dal peso del punto da cui parte sia dalla direzione della mossa stessa (in particolare il costo C di una mossa da un punto M in una certa direzione è -C', dove C' è il costo di una mossa sempre dal punto M ma nella direzione opposta), non è ovvio che un percorso in cui ogni mossa diminuisce il peso (ammesso che esista) sia anche il percorso meno costoso. Io all'inizio avevo ipotizzato che il percorso più corto fosse anche quello che richiede una minor quantità di euro iniziale e sperimentando un po' con le regole del gioco non sono riuscito a trovare controesempi, anzi sono stato portato a ipotizzare che il costo totale di un percorso dal punto M al punto N dipenda esclusivamente dalle coordinate di M e N e dalla lunghezza del percorso (intesa come numero di mosse del percorso stesso), anche se non sono ancora riuscito a dimostrarlo formalmente.
Ripeto che potrei semplicemente essermi perso qualche punto chiave, quindi Stef2008 ti sarei molto grato se riuscissi a spiegarmi questi due passaggi. Grazie mille per l'aiuto, un saluto.

In breve una mossa costa $2a-2b±1=2P_{(a,b)}±1$, questo diciamo spiega il tuo dubbio credo. Guarda come è stato definito il peso nel mio primo post

[Stef2008]

Salve a tutti ,
sto svolgendo alcuni esercizi degli anni passati dei tests della scuola normale .
Di quello che vi posto non ho trovato nel web alcuna soluzione se non qualche indicazione che arriva (per problemi analoghi) dalla "programmazione dinamica".
A seguire il testo (scusandomi in anticipo se avessi sbagliato sezione).
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 $ € per effettuare la mossa,mentre se $ C<0 $ muovendo la pedina si ricevono $ |C| $ € . Sono vietate tutte le mosse il cui costo è strettamente maggiore di ciò che si ha a disposizione ad inizio turno. Ad ogni turno il numero di € non può mai diventare negativo. Si inizia con la pedina nella casella $ (5,1) $ ed $ N $ € 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

@FraGhila, a quanto pare il test postato qui è diverso da quello originale. Qua c'è scritto che le mosse costano tutte nell'ordine $ 2a−2b−1;2a−2b+1;2a−2b−1;2a−2b+1 $.
La mia soluzione è quella relativa al problema postato qui sul forum... non sapevo che il testo originale fosse diverso. Nel testo originale che ho letto ora alcune sono della forma 2b-2a±1. La mia soluzione era relativa al problema che è stato postato qui. Ecco il perchè delle nostre incomprensioni...
@Gandalf73, credo che questo interessi anche a te, quando ho tempo risolvo la versione originale del problema.

[Gandalf73]

@Stef2008:sorry ma forse avrò letto male io ed ecco il perchè dell'incongruenza.Era messo a disposizione nel sito dell'SNS.Ho forse errato con qualche dato del problema?
Nel caso mi scuso e lo correggo.Sono un po "carico" questi gg a breve lo ricontrollo e posto le correzioni qualora vi fossero.
Nel frattempo grazie a tutti per le risposte!
A.

[Stef2008]

@Stef2008:sorry ma forse avrò letto male io ed ecco il perchè dell'incongruenza.Era messo a disposizione nel sito dell'SNS.Ho forse errato con qualche dato del problema?
Nel caso mi scuso e lo correggo.Sono un po "carico" questi gg a breve lo ricontrollo e posto le correzioni qualora vi fossero.
Nel frattempo grazie a tutti per le risposte!
A.

Ciao, non ti preoccupare capita a tutti di sbagliare... Questo dovrebbe essere il testo corretto:
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:
$ 2b−2a−1;2a−2b+1;2a−2b−1;2b−2a+1.$
Se C≥0 occorre sborsare C € per effettuare la mossa,mentre se C<0 muovendo la pedina si ricevono |C| € . Sono vietate tutte le mosse il cui costo è strettamente maggiore di ciò che si ha a disposizione ad inizio turno. Ad ogni turno il numero di € non può mai diventare negativo. Si inizia con la pedina nella casella (5,1) ed N € 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)



Nel testo sopra le mosse erano tutte della forma $2a-2b±1$...
Onestamente sono un po' occupato con altri problemi... intuitivamente la risposta sembra quella di FraGhila... formalizzare è più difficile... Ho provato un'oretta è poi ho smesso... quando avrò un po' di tempo darò un'altra occhiata.

[FraGhila]

Ciao a tutti.
Ultimamente ho lavorato un po' a questo problema e ho avuto un'intuizione che potrebbe essere utile per risolvere il problema. La funzione [math]C(*, a, b) = \pm 2(a - b) \pm 1 per il costo di una mossa generica [math]* dal punto [math](a, b) descrive una retta nel piano cartesiano ([math]a corrisponde alla coordinata [math]x e [math]b corrisponde alla coordinata [math]y). Dato che con ogni mossa [math](a' = a \pm 1 \land b' = b) \oplus (a' = a \land b' = b \pm 1), allora [math]\Delta C(*) = C(*, a', b') - C(*, a, b) = \pm 2. In particolare dopo una mossa verso l'alto o verso sinistra [math]\Delta C(\rightarrow) = \Delta C(\downarrow) = 2 e [math]\Delta C(\leftarrow) = \Delta C(\uparrow) = -2, mentre dopo una mossa verso il basso o verso destra succede l'opposto, ovvero [math]\Delta C(\rightarrow) = \Delta C(\downarrow) = -2 e [math]\Delta C(\leftarrow) = \Delta C(\uparrow) = 2.
Questo semplifica un po' alcuni ragionamenti, anche se non sono ancora riuscito a capire esattamente come usarlo per risolvere il problema.

[Stef2008]

Beh... nonostante può semplificare i calcoli mi sembra ancora lontano dalla soluzione completo... avevo dimostrato tempo fa qualche risultato più forte (ad esempio se ricordo bene fissata casella iniziale e finale ogni percorso di lunghezza minima che li collega ha lo stesso costo...). Tuttavia non sono riuscito a concludere... in definitiva è secondo me il problema più difficile di quell'anno dato che gli altri li avevo risolti (o forse è facile, ma a me non è venuta l'idea giusto)


Edit: anche quello sul cubo era decisamente difficile... anche se con i giusti lemmi si demolisce (ma questi vanno dimostrati e qui la situzione si complica)... gli altri tutti più facili

[Gandalf73]

Grazie infinite dell'analisi preziosa e del contributo che fornite.
Dalla definizione e dai dati del problema (ossia che non si può effettuare una mossa che porti C in negativo), il minimo di C , rappresenta il "pagamento più conveniente". Questo perchè se C è positivo non può diventare negativo con una mossa ma può solo "ridursi" rimanendo > di 0 (il testo indica strettamente positivo). Il dubbio però arriva spontaneo (ammesso abbia interpretato bene il testo): se giungessimo esattamente a zero , posso ritenere consentita una mossa che mi porti il costo ad essere negativo e magari far si che questo lo diventi sempre di più ad ogni mossa?
Un saluto e grazie per l'aiuto
A.

ps ha sempre più le parvenze di un problema risolvibile con la programmazione dinamica, qualcosa che ha a che fare con i grafi.