Sant'anna 2017 - Matematica esercizio 3

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Rispondi
Nadal21
Messaggi: 164
Iscritto il: 12 mar 2015, 15:30

Sant'anna 2017 - Matematica esercizio 3

Messaggio da Nadal21 » 14 ago 2019, 00:08

Una scacchiera $ n \times m $ (in figura quella $ 3 \times 5 $) contiene $ nm-1 $ piastrelle quadrate ed uno spazio vuoto (in nero nella figura). Una mossa è lo spostamento di una piastrella in un quadrato adiacente (che deve essere necessariamente vuoto).
  • Mostrare che per spostare lo spazio vuoto dalla posizione $ (h,k) $ alla posizione $ (h+p, k+q) $ il numero di mosse minimo è $ \left| p \right| + \left| q \right| $.
  • Nel caso di scacchiera $ 3 \times 5 $ determinare il minimo numero di mosse per portare una piastrella dalla posizione $ (1,1) $ alla posizione $ (3,5) $ nel caso in cui lo spazio vuoto si trovi inizialmente in $ (2,1) $ e nel caso in cui lo spazio vuoto si trovi inizialmente in $ (1,2) $ .
  • ]Nel caso di scacchiera $ 3 \times 5 $ sapendo che lo spazio vuoto potrebbe trovarsi in un aqualsiasi casella diversa da $ (1,1) $ determinare il Valor Medio del numero minimo di mosse per spostare una piastrella dalla posizione $ (1,1) $ alla posizione $ (3,5) $
Allegati
disegno scacchiera.pdf
(110.05 KiB) Scaricato 33 volte

TeoricodeiNumeri
Messaggi: 17
Iscritto il: 14 lug 2019, 09:58

Re: Sant'anna 2017 - Matematica esercizio 3

Messaggio da TeoricodeiNumeri » 14 ago 2019, 10:55

[math]
Testo nascosto:
1)Dalla considerazione che servono almeno $\vert p \vert$ mosse per cambiare colonna $\vert p \vert$ volte e $\vert q\vert$ mosse per cambiare colonna almeno $\vert q \vert$ volte e ogni mossa cambia o riga o colonna (ma non entrambe), allora un lower bound per il numero minimo di mosse necessarie è proprio $\vert p\vert +\vert q\vert$. D'altro canto è facile vedere che esiste sempre una maniera di eseguire esattamente $\vert p\vert +\vert q\vert$ mosse.
2-3) Partiamo con una considerazione banale: per poter muovere una piastrella è necessario e sufficiente che una delle caselle ad essa adiacenti sia vuota. Un'altra considerazione banale: quando muoviamo una piastrella, a meno di considerare le piastrelle indistinguibili, la configurazione finale è sempre la stessa, ovvero la casella vuota sarà sempre e solo quella precedentemente occupata dalla piastrella che abbiamo appena mosso. Ciò ci permette di dire che, scelto il percorso, sarà sufficiente ridurre al minimo il numero di mosse necessario per ogni spostamento (cioè non si può trarre vantaggio a lungo termine dall'aver sprecato delle mosse per spostarsi da una casella a quella adiacente). Supponiamo ora di aver eseguito una mossa.
I casi da considerare sono 2:
a) decidiamo di cambiare direzione rispetto alla mossa precedente. Allora, scelta la casella su cui andare sono necessarie e sufficienti esattamente $3$ mosse per spostare nuovamente la piastrella. Difatti supponete di avere una mini-scacchiera $2\times 2$ in cui la casella $(1;1)$ è vuota mentre tutte le altre sono piastrellate. Vogliamo muovere la piastrella in $(2;1)$ in $(2;2)$. Lo possiamo fare in $3$ mosse perché ci basta spostare la piastrella in $(1;2)$ nella casella $(1;1)$, quella in $(2;2)$ nella casella $(1;2)$ e infine la piastrella in $(2;1)$ nell'ormai libera casella $(2;2)$. E' facile vedere che il numero di mosse non può essere minore (contate quante piastrelle al più si dovrebbero muovere per minimizzare ulteriormente il numero di mosse);
b) non cambiare direzione (e non tornare indietro ovviamente): qua sono necessarie e sufficienti $5$ per spostare la piastrella (considerate il caso di un rettangolino $3\times 2$ in cui la casella vuota si trova in $(1;1)$ e volete spostare la piastrella in $(2;1)$ nella casella $(3;1)$; poi fate vedere che non si può far di meglio).
Con la considerazione che in ogni caso ritornare su una riga o una colonna in cui si era già precedentemente passati non può far altro che aumentare il numero di mosse necessarie per raggiungere una data posizione, il numero minimo di mosse si calcola con la seguente espressione
\begin{equation}
m+1+3c+5i
\end{equation}
dove $m$ è il numero di mosse necessarie alla casella vuota per raggiungere una posizione adiacente alla piastrella da muovere che non faccia "tornare indietro"(ci sarebbe da porre la condizione che suddetta casella massimizzi il numero di cambi di direzione, ma è facile notare che per le due caselle possibili i cambi di direzione possibili sono sempre gli stessi), $1$ che è la mossa iniziale della piastrella, $3c$ che è il numero di cambi di direzione possibili della piastrella moltiplicati per $3$ che è il numero minimo di mosse necessario per il cambio di direzione (ripeto: senza tornare indietro) e $5i$ che il numero di mosse restanti che si ottiene moltiplicando per $5$ il numero di volte in cui non cambiamo direzione senza tornare indietro.

Perciò, sia nel primo che nel secondo caso del punto $2$ le mosse sono $0+1+3\cdot 3+2\cdot 5=20$.

Per il punto $3$ scrivete un numero su ogni casella che rappresenta il numero minimo di mosse necessarie alla casella vuota per raggiungere la posizione più vicina fra $(1;2)$ e $(2;1)$, sommate (vi dovrebbe venire $31$), dividete per $14$ e sommate $20$ ,ottenendo $\frac{31}{14}+20\approx 22,214$ che è il valor medio.
Ultima modifica di TeoricodeiNumeri il 14 ago 2019, 20:51, modificato 1 volta in totale.

Nadal21
Messaggi: 164
Iscritto il: 12 mar 2015, 15:30

Re: Sant'anna 2017 - Matematica esercizio 3

Messaggio da Nadal21 » 14 ago 2019, 11:38

Bella soluzione :wink: :D

Rispondi