Da God Plays Dice ho trovato un link a un giochino facile facile scritto in flash: Shinju. Scopo del gioco è trovare in quattro mosse al massimo quale delle ostriche presenti nel reticolo nasconde una perla. Quando si clicca su un’ostrica, i casi sono due: o c’è una perla – e allora si passa al livello successivo – oppure compare un numero che indica la distanza di Chebyshev tra la posizione scelta e la perla. Scritto così può spaventarvi, ma non è difficile: è il numero di passi che occorre a un re degli scacchi per spostarsi da una casella all’altra. Se siete un po’ più matematici, potete pensarla come il massimo tra la distanza in unità orizzontali e quella in unità verticali; se siete parecchio matematici, è quella data dalla norma L∞.
La parte matematica del tutto consiste nel dimostrare che è sempre possibile trovare la perla in quattro tentativi. È vero che così si perde il piacere di giocare al giochino, ma tanto dopo qualche schema ci si scoccerebbe comunque, e almeno si dovrebbe avere il piacere di mettersi alla prova con una dimostrazione. Confesso che non mi sono messo a trovare la dimostrazione nel caso pratico del gioco, ma al momento mi sono limitato al caso più semplice in cui sia possibile cliccare su una qualunque casella, anche se non ci sono perle. Volete provarci anche voi? E cosa succede se invece che la norma L∞ abbiamo la norma L1, cioè calcoliamo la somma delle distanze orizzontali e verticali? Anche in questo caso si è sicuri di risolvere il gioco in quattro mosse al più? Buona dimostrazione: se proprio non ce la fa nessuno, posterò qualche aiutino. Un’unica avvertenza: se volete postare una soluzione, scrivete SPOILER in maiuscolo all’inizio del commento!
Ultimo aggiornamento: 2008-11-18 14:30
Questi sono i classici casi in cui si rischia la figuraccia. :)
Io provo con quella semplice.
SPOILER
*
*
*
*
*
*
*
*
Ti dò già l’algoritmo nella sua versione più inefficiente. :P
1. Si clicca [0,0]. Se si trova, fine. Altrimenti si ottiene D / esiste x e la soluzione è {[D,x] o [x,D]}
2. Si clicca [1,0]. Se si trova, fine. Altrimenti si ottiene R.
A) Se R == D, vuol dire che non ci siamo avvicinati e la soluzione è del tipo [x,D].
3. Si clicca [0, D] (azzerando la distanza nota). Se si trova, fine. Altrimenti si ottiene S. A questo punto la soluzione è [S,D] (4)
B) Se R minore di D, vuol dire ch ci siamo avvicinati, quindi la soluzione è del tipo [D,x]
3. Si clicca [D, 0] (azzerando la distanza nota). Se si trova, fine. Altrimenti si ottiene S. A questo punto la soluzione è [D,S] (4)
Per C1 non ci voglio neanche pensare, mi spiace. :)
Ma, ad occhio, direi che non è possibile.
> dalla norma C∞
???
intendi dire dalla norma l^∞? non mi sembra che sia la norma di C∞ – tanto piú che, in effetti, C∞ è solo uno spazio di frechet…
SPOILER SPOILER SPOILER
Che poi se qualcuno legge è colpa sua!
Allora, se si parlasse di distanza euclidea la cosa sarebbe semplice poiché dati tre punti distinti e tre distanze si individuano tre circonferenze e tre circonferenze distinte su un piano individuano al più un solo punto, il quarto punto da selezionare per vincere.
Con la distanza di Chebyshev bisogna innanzi tutto capire qual’è il luogo dei punti individuato dal punto cercato e dalla distanza di Chebyshev. Questo luogo è un quadrato con assi paralleli agli assi coordinati, lato doppio della distanza e centro il punto individuato. La cosa è facilmente dimostrabile osservando che bisogna ognuno dei due termini della funzione Max individua due rette parallele rispettivamente all’asse x e all’asse y ed il quadrato è quello ottenuto dall’intersezione delle due rette.
In generale l’intersezione di due quadrati su un piano può individuare un singolo punto (ed è fatta!), due punti (ed è facile, se uno è sbagliato si sceglie l’altro), un segmento, un segmento e un punto o due segmenti. Nel caso venga individuato un segmento è sufficiente scegliere uno dei due vertici per avere la distanza dal vertice e quindi individuare il punto poiché su una semiretta conoscendo la distanza dall’origine si individua un unico punto. Negli ultimi due casi si è sfortunati e il gioco non funziona.
Se tuttavia si adotta una tattica si può vincere in quattro mosse; se infatti, dopo aver fallito il primo punto si sceglie come secondo punto uno dei quattro vertici del quadrato, se non si è vinto si possono individuare due soli punti e quindi è fatta (due punti da provare e due disponibili!).
La dimostrazione di questo è piuttosto semplice, vi sono due semirette con origine in comune ed una distanza da misurare su entrambe.
Spero di essere stato chiaro (ma temo di no!)
Quanto al caso C1 la dimostrazione è identica posto di osservare che il luogo dei punti è un quadrato con lati inclinati di 45 gradi rispetto agli assi coordinati.
Si dimostra facilmente traslando il punto scelto nell’origine ed espandendo i valori assoluti si ottiene il sistema di equazioni x+y=d, x-y=d, -x+y=d e -x-y=d che individuano due rette con pendenza +1 passanti in x=d e x=-d e due rette con pendenza -1 passanti per x=d e x=-d.
Ovviamente la forma individuata è invariante ad ogni traslazione.
Ciao
@delio: è ovvio che mi sono dimenticato praticamente tutto dopo venticinque anni.
Ovviamente data l’ora a cui ho tentato la soluzione ero già fuso ed ho sbagliato, mi correggo:
RE SPOILER
Se seleziono il secondo punto su un vertice potrei trovarmi nella situazione di avere i due lati opposti al vertice; la scelta migliore è dunque scegliere un punto su un lato con entrambe le coordinate diverse dal primo punto. Il caso peggiore è individuare un segmento o un punto ma si può facilmente dimostrare che il segmento è più corto della minima distanza tra il segmento ed il punto rendendo semplice la selezione degli ultimi due punti.
Sono stato confuso ma ho fretta :-)
Ciao
A questo punto, però, ci devi far vedere la tua. :)
Già mi immagino spazi non euclidei a N dimensioni intersecati tra di loro… (mathbubble) :-D
@Fang:
(SPOILER SPOILER)
.
.
.
.
.
.
.
comincio anch’io con il lato in basso a sinistra (0,0) ma continuo con il vertice opposto del quadrato, cioè (D,D). In questo modo, se al secondo tentativo non sono stato fortunato e ottengo una distanza E, ho individuato esattamente due punti possibili: (D-E,D) e (D,D-E). In questo modo, la probabilità di trovare la perla in al più tre tentativi è leggermente superiore al 50% (“leggermente superiore” perché avrei potuto trovarla nei primi due tentativi). Per la norma L1, dovrebbero bastare tre tentativi.
@.mau.
Tre per L1? Il mio occhio non funziona. :)
Ok, adesso mi hai incuriosito, proviamo L1.
SPOILER
*
*
*
*
*
*
*
*
Soluzione [X,Y]
1.Premo [0,0]. Ottengo D=X+Y
2.Premo [K,0].
A)Se K maggiore di X, ottengo E=K-X+Y
X=K+Y-E, Y=D-X
X=K+D-X-E -> 2X=K+D-E -> X=(K+D-E)/2, Y=-(K-E-D)/2 e ci arrivo in 3. Ok.
B)Se K minore di X, ottengo E=X-K+Y che però non mi porta da nessuna parte.
Quindi devo prendere K=limite estremo opposto, per essere sicuro che sia sempre maggiore (o uguale) X ed essere sicuro di essere sempre nel caso A. Ok.
Vabbé, poi mi metto gli occhiali. :P
@Fang:
SPOILER
.
.
.
.
.
.
anche qua, se il tuo reticolo parte da (0,0) e arriva a (M,N), inizi con (0,0) e ottieni D. Se D
@.mau.
Uhm… sei stato un po’ troppo sintetico.
:-D
Comunque la soluzione che ho proposto l’ho provata a manina e pare funzionare, se ho capito cos’è L1. Del resto i conti son lì.
Se poi addesso dimostri che riesci a farcela con due colpi, ti mando a… :)
@Fang: Usi bene la norma L1, ma non capisco il “K=limite estremo opposto”. Faccio un esempio numerico: abbiamo il reticolo 11×11 da (0,0) a (10,10), e la perla è nascosta in (9,4); quindi hai D=13. Che K scegli?
@.mau.
Sì, scrivo in maniera vergognosa. :)
SPOILER
*
*
*
*
*
*
Il massimo (sull’asse X) del reticolo. Questo perché, come da commento, devo essere sicuro che K maggiore (o uguale) X.
Ho scritto “limite estremo opposto” perché ero concentrato su [0,0] e il limite estremo opposto era “ovviamente” (nella mia testa) [N,0].
Nel tuo esempio, K=10
1. [0,0] D =9+4=13
2. [10,0] E= 1+4=5
X= (K+D-E)/2, Y=-(K-E-D)/2
X= (10+13-5)/2=9
Y=-(10-5-13)/2=4
Non mi chiedere l’estensione al caso reale del gioco perché è banale :-D