Il drago si nasconde in una casella di una tabella 2015×2015. Ad ogni mossa possiamo colpire una casella. Se quella scelta contiene il drago questo viene ferito e fugge su una casella adiacente (con un lato in comune), altrimenti rimane fermo. Se il drago viene ferito due volte, muore. Quante mosse sono necessarie, al minimo, per essere certi di uccidere il drago non sapendo n è in quale casella si trova, n è quando o dove si sposta una volta ferito?
Ho fatto questo problema, mi è sembrato carino, magari qualcuno può provare...
Semplice ma carino [L03]
Re: Semplice ma carino [L03]
Piccolo hint;
Testo nascosto:
Re: Semplice ma carino [L03]
Cosa intendi che non sappiamo quando si sposta? Che non sappiamo se abbiamo colpito il drago?
Si sposta subito appena colpito?
Si sposta subito appena colpito?
Re: Semplice ma carino [L03]
Sì, se viene colpito si sposta subito (in una casella adiacente). Significa proprio che non sappiamo quando facciamo una mossa se il colpo va a vuoto o riesce a colpire il drago... non so se mi sono spiegato bene...
Re: Semplice ma carino [L03]
Una prima idea, che forse non è l'ottimo....
Testo nascosto:
Re: Semplice ma carino [L03]
L'idea è, in realtà, proprio questa... bisogna però dimostrare che è ottimale