Regine, torre e alfiere su una scacchiera

Il forum di Base5, dove è possibile postare problemi, quiz, indovinelli, rompicapo, enigmi e quant'altro riguardi la matematica ricreativa e oltre.

Moderatori: Gianfranco, Bruno

Rispondi
panurgo
Livello 9
Livello 9
Messaggi: 1457
Iscritto il: sab nov 19, 2005 3:45 pm
Località: Padova

Regine, torre e alfiere su una scacchiera

Messaggio da panurgo »

Domanda n. 1

Trovare la probabilità che due regine, piazzate aleatoriamente su una scacchiera $8\times8$, si attacchino a vicenda. Una regina controlla la riga, la colonna e le diagonali che si intersecano nella casella da essa occupata.

Generalizzare al caso di una scacchiera $n\times n$

Domanda n. 2

Trovare la probabilità che almeno uno dei due pezzi, torre e alfiere, piazzati a caso su una scacchiera $8\times8$ sia minacciato dall’altro.

Diophante.fr
il panurgo

Principio di Relatività: {\bb m} \not \right {\bb M} \ \Longleftrightarrow \ {\bb M} \not \right {\bb m}
"Se la montagna non va a Maometto, Maometto NON va alla montagna"

franco
Livello 9
Livello 9
Messaggi: 1355
Iscritto il: mar dic 12, 2006 12:57 pm
Località: Bèrghem (Sardegna)

Re: Regine, torre e alfiere su una scacchiera

Messaggio da franco »

Uhm ... può essere che (per la scacchiera 8x8) la risposta alle due domande sia identica?
Franco

ENGINEER
noun. (en-juh-neer)
someone who does precision guesswork based on unreliable data provided by those of questionable knowledge.
See also wizard, magician

Quelo
Livello 7
Livello 7
Messaggi: 757
Iscritto il: ven giu 16, 2006 3:34 pm

Re: Regine, torre e alfiere su una scacchiera

Messaggio da Quelo »

Domanda 1: Le regine

Se non ho sbagliato i calcoli, la probabilità è $\displaystyle P_{RvsR}=0,36\overline{1}$

Nella cornice esterna, dovunque si trovi la regina, minaccia sempre 21 caselle
Se passiamo alla seconda cornice le caselle minacciate aumentano di 2, e così via fino alle quattro caselle centrali dove le caselle minacciate dalla regina sono 27
La cornice esterna ha 28 caselle, la seconda 20, la terza 12 e la quarta 4
La probabilità che la seconda regina sia posizionata su una casella minacciata dalla prima regina è:

$\displaystyle P_{RvsR}=\frac{28}{64}\cdot\frac{21}{63}+\frac{20}{64}\cdot\frac{23}{63}+\frac{12}{64}\cdot\frac{25}{63}+\frac{4}{64}\cdot\frac{27}{63}=\frac{13}{36}$

Generalizzando, ogni cornice ha $8k+4$ caselle, con $k$ che va da $0$ a $\displaystyle \frac{n}{2}-1$ e la regina minaccia $4n-2k-5$ caselle

$\displaystyle P_{RvsR}=\sum_{k=0}^{\frac{n}{2}-1}\frac{(8k+4)(4n-2k-5)}{n^2(n^2-1)}=\frac{2(5n-1)}{3n(n+1)}$
Ultima modifica di Quelo il mar set 13, 2022 7:12 am, modificato 1 volta in totale.
[Sergio] / $17$

franco
Livello 9
Livello 9
Messaggi: 1355
Iscritto il: mar dic 12, 2006 12:57 pm
Località: Bèrghem (Sardegna)

Re: Regine, torre e alfiere su una scacchiera

Messaggio da franco »

Quelo ha scritto:
lun set 12, 2022 5:37 pm
Domanda 1: Le regine

Se non ho sbagliato i calcoli, la probabilità è $\displaystyle P_{RvsR}=0,36\overline{1}$
Concordo, e come dicevo nel post precedente, penso che anche la risposta al secondo quesito sia $\displaystyle P_{TvsA}=0,36\overline{1}$
P.S. naturalmente, nel secondo caso se la torre minaccia l'alfiere non è possibile il contrario (e viceversa)
Franco

ENGINEER
noun. (en-juh-neer)
someone who does precision guesswork based on unreliable data provided by those of questionable knowledge.
See also wizard, magician

Quelo
Livello 7
Livello 7
Messaggi: 757
Iscritto il: ven giu 16, 2006 3:34 pm

Re: Regine, torre e alfiere su una scacchiera

Messaggio da Quelo »

Preciso che la generalizzazione vista prima vale per scacchiere di lato pari, per quelle di lato dispari bisogna considerare $(8k+1)$ caselle in ogni cornice
Quindi dovrebbe essere

$\displaystyle P_{RvsR}=\sum_{k=0}^{\frac{n}{2}-1}\frac{(8k+1)(4n-2k-5)}{n^2(n^2-1)}=\frac{40n^2-111n+80}{12n(n^2-1)}$

SE&O
[/quote]
Ultima modifica di Quelo il mar set 13, 2022 9:09 am, modificato 1 volta in totale.
[Sergio] / $17$

Quelo
Livello 7
Livello 7
Messaggi: 757
Iscritto il: ven giu 16, 2006 3:34 pm

Re: Regine, torre e alfiere su una scacchiera

Messaggio da Quelo »

franco ha scritto:
lun set 12, 2022 9:56 pm
Concordo, e come dicevo nel post precedente, penso che anche la risposta al secondo quesito sia $\displaystyle P_{TvsA}=0,36\overline{1}$
Confermo, per l'alfiere si ragiona come per la regina considerando solo le digonali, quindi 4 caselle con copertura 13, 12 caselle con copertua 11, ecc...
Quindi la probabilità che la torre cada sun una casella minacciata dall'alfiere è

$\displaystyle P_{A}=\frac{4\cdot13+12\cdot11+20\cdot9+28\cdot7}{64\cdot63}=\frac{5}{36}$

Anche qui si può generalizzare

$\displaystyle P_{A}=\sum_{k=0}^{\frac{n}{2}-1}\frac{(8k+4)(2n-2k-3)}{n^2(n^2-1)}=\frac{2(2n-1)}{3n(n+1)}$

Per la torre la probabilità è costante $\displaystyle P_{T}=\frac{2(n-1)}{n^2-1}=\frac{14}{63}=\frac{8}{36}$

$\displaystyle P_{TvsA}=\frac{2(5n-1)}{3n(n+1)}$ sempre per scacchiere con lato pari
[Sergio] / $17$

Quelo
Livello 7
Livello 7
Messaggi: 757
Iscritto il: ven giu 16, 2006 3:34 pm

Re: Regine, torre e alfiere su una scacchiera

Messaggio da Quelo »

Quelo ha scritto:
lun set 12, 2022 11:06 pm
Preciso che la generalizzazione vista prima vale per scacchiere di lato pari, per quelle di lato dispari bisogna considerare $(8k+1)$ caselle in ogni cornice
Quindi dovrebbe essere

$\displaystyle P_{RvsR}=\sum_{k=0}^{\frac{n}{2}-1}\frac{(8k+1)(4n-2k-5)}{n^2(n^2-1)}=\frac{40n^2-111n+80}{12n(n^2-1)}$

SE&O
Rettifico quanto detto in precedenza, rifacendo tutti i calcoli con le considerazioni del caso, risulta che la formula per le scacchiere lato pari vale anche anche per quelle lato dispari
[Sergio] / $17$

panurgo
Livello 9
Livello 9
Messaggi: 1457
Iscritto il: sab nov 19, 2005 3:45 pm
Località: Padova

Re: Regine, torre e alfiere su una scacchiera

Messaggio da panurgo »

Due pezzi vengono posizionati su una scacchiera ($n\times n$). Non sappiamo dove sono quindi dobbiamo, in base al Principio di Indifferenza, assegnare la stessa probabilità a tutte le configurazioni possibili che sono $n^2\left(n^2-1\right)$: questi sono, secondo una vecchia nomenclatura, i “Casi Possibili”; fattorizzato

$\displaystyle p\left(n\right)=n^2\left(n+1\right)\left(n-1\right)$

Dobbiamo ora contare i “Casi Favorevoli” per ciascun pezzo, cominciando dal più semplice: la Torre.
La Torre attacca lo stesso numero di caselle ovunque sia posta sulla scacchiera
G110.0.1.png
G110.0.1.png (7.96 KiB) Visto 146 volte
dunque i casi favorevoli sono $2\left(n-1\right)$ per ciascuna casella: in totale

$\displaystyle a\left(n\middle|♖\right)=2n^2\left(n-1\right)$

Possiamo calcolare la probabilità che un pezzo posto a caso su una scacchiera $n\times n$ dove c’è già una Torre sia minacciato da essa

$\displaystyle \Pr\left(S\middle|♖\wedge n\wedge\top\right)=\frac{ a\left(n\middle|♖\right)}{p\left(n\right)}=\frac{2n^2\left(n-1\right)}{n^2\left(n+1\right)\left(n-1\right)}=\frac2{n+1}$

Per l’Alfiere le cose sono meno semplici perché il numero di caselle attaccate dipende dalla posizione sulla scacchiera: se lo mettiamo su una casella esterna della scacchiera il numero di caselle attaccate rimane costante
G110.0.2.png
G110.0.2.png (27.77 KiB) Visto 146 volte
È sufficiente testare le caselle della prima metà di un lato perché tutte le altre caselle sono equivalenti per simmetria a una di queste: comunque spostando l’Alfiere una delle due diagonali si allunga di quanto l’altra si accorcia.
Se ora aggiungiamo una cornice esterna
G110.0.3.png
G110.0.3.png (30.57 KiB) Visto 146 volte
osserviamo che ciascuna delle due diagonali aumenta sempre di due caselle (perché tutte le diagonali della scacchiera aumentano di due caselle): ciò implica che il numero di caselle attaccate è costante per ogni cornice.
Per contare le caselle attaccate per una data cornice possiamo semplificarci la vita mettendo l’Alfiere su una diagonale principale della scacchiera:
G110.0.4.png
G110.0.4.png (30.36 KiB) Visto 146 volte
in questo modo, il numero di caselle in una delle due diagonali rimane costante mentre quello dell’altra aumenta di due caselle passando da una cornice a quella subito più interna; per una data cornice la somma dei due contributi vale

$\displaystyle a\left(n,k\middle|♗\right)=\left(n-1\right)+2\left(k-1\right)=n-3+2k$

dove $k$ è il numero della cornice contando dall’esterno verso l’interno (vedi figura).
Per calcolare il numero di caselle attaccate dall’Alfiere dobbiamo contare le caselle di ogni cornice, $c\left(n,k\right)$, ed eseguire la sommatoria

$\displaystyle a\left(n\middle|♗\right)=\sum_k c\left(n,k\right) a\left(n,k\middle|♗\right)$

Quanto vale $c\left(n,k\right)$? Osserviamo che (vedi figura)
G110.0.5.png
G110.0.5.png (29.66 KiB) Visto 146 volte
le caselle della cornice esterna di una scacchiera $n\times n$ sono

$\displaystyle c\left(n,n\right)=\left\{\begin{array}{lC} 1 & n=1 \\ 4\left(n-1\right) & n > 1 \end{array}\right.$

Di conseguenza, le caselle della $k$-esima cornice di una scacchiera $n\times n$ saranno, contando dall’esterno verso l’interno

$\displaystyle c\left(n,k\right)=\left\{\begin{array}{lC} 1 & n=2m+1\wedge k=1 \\ 4\left[\left(n-1\right)-2\left(k-1\right)\right]=4\left(n+1-2k\right) & k > 1 \end{array}\right.$

e la nostra sommatoria sarà

$\displaystyle a\left(n\middle|♗\right)=\left\{\begin{array}{lC}
\displaystyle\sum_k^{\frac{n}2} 4\left(n+1-2k\right)\left(n-3+2k\right) & n=2m \\
\displaystyle2\left(n-1\right)+\sum_k^{\frac{n-1}2} 4\left(n+1-2k\right)\left(n-3+2k\right) & n=2m +1
\end{array}\right.$

La distinzione sorge perché per, n dispari, la cornice centrale non segue la regola generale.
Chiediamo a WolframAlpha di eseguire il calcolo ottenendo in entrambi i casi lo stesso risultato

$\displaystyle a\left(n\middle|♗\right)=\frac{2n\left(n-1\right)\left(2n-1\right)}3$

La probabilità che un pezzo posto a caso su una scacchiera $n\times n$ dove c’è già un Alfiere sia minacciato sarà

$\displaystyle \Pr\left(S\middle|♗\wedge n\wedge\top\right)=\frac{ a\left(n\middle|♗\right)}{p\left(n\right)}=\frac{2n\left(n-1\right)\left(2n-1\right)}{n^2\left(n+1\right)\left(n-1\right)}=\frac{2\left(2n-1\right)}{3n\left(n+1\right)}$

La Regina fa le mosse della Torre e quelle dell’Alfiere: siccome la Torre attacca parallelamente ai lati mentre l’Alfiere lo fa sulle diagonali i due set di mosse sono indipendenti.
G110.0.6.png
G110.0.6.png (28.43 KiB) Visto 146 volte
La probabilità che un pezzo posto a caso su una scacchiera $n\times n$ dove c’è già una Regina sia minacciato sarà la somma della probabilità per la Torre e per l’Alfiere

$\displaystyle \Pr\left(S\middle|♕\wedge n\wedge\top\right)=\Pr\left(S\middle|♖\wedge n\wedge\top\right)+\Pr\left(S\middle|♗\wedge n\wedge\top\right)=\frac2{n+1}+\frac{2\left(2n-1\right)}{3n\left(n+1\right)}=\frac{2\left(5n-1\right)}{3n\left(n+1\right)}$

La risposta alla seconda domanda, qual è la probabilità di essere attaccati o da una Torre (se sei l’Alfiere) o da un Alfiere (se sei la Torre), è la stessa (set di mosse indipendenti, somma delle probabilità)

$\displaystyle \Pr\left(S\middle|\left(♖\vee♗\right)\wedge n\wedge\top\right)=\Pr\left(S\middle|♖\wedge n\wedge\top\right)+\Pr\left(S\middle|♗\wedge n\wedge\top\right)=\frac{2\left(5n-1\right)}{3n\left(n+1\right)}$

Per la scacchiera $8\times 8$, $13/36$.
il panurgo

Principio di Relatività: {\bb m} \not \right {\bb M} \ \Longleftrightarrow \ {\bb M} \not \right {\bb m}
"Se la montagna non va a Maometto, Maometto NON va alla montagna"

Quelo
Livello 7
Livello 7
Messaggi: 757
Iscritto il: ven giu 16, 2006 3:34 pm

Re: Regine, torre e alfiere su una scacchiera

Messaggio da Quelo »

Il caso delle regine si dovrebbe poter estendere a scacchiere con più di 2 dimensioni

Partiamo da 2 dimensioni e immaginiamo la regina, posta nell’angolo della scacchiera, come se fosse nell’origine degli assi. Da questa posizione ha 3 direzioni di movimento: 2 lungo gli assi e 1 lungo una diagonale nel piano $(2^2-1)$. Quindi le caselle minacciate sono $3(n-1)$
Il discorso è analogo per tutta la cornice esterna, le diagonali diventano 2 ma la lunghezza complessiva della diagonale è sempre $n-1$
Quando ci spostiamo nella seconda cornice la regina si trova al centro di un quadrato 3x3 e si può muovere in 4 direzioni $\displaystyle(\frac{3^2-1}{2})$, la nuova diagonale introduce 2 caselle in più, quindi le caselle minacciate sono $3(n-1)+2$
Ad ogni cornice si aggiungono 2 caselle, fino al centro della scacchiera: +4, +6, …

La cornice esterna ha $n^2-(n-2)^2$ caselle, la seconda $(n-2)^2-(n-4)^2$, ecc…

La probabilità si calcola facilmente come sommatoria

Passiamo ora a 3 dimensioni
La regina nel guscio esterno ha 7 direzioni di movimento, 3 lungo gli assi, 3 lungo le diagonali dei piani formati dalle coppie di assi e 1 lungo la diagonale del cubo $(2^3-1)$, i cubetti minacciati sono $7(n-1)$
Nella seconda cornice si trova al centro di un cubo 3x3x3 e ha 13 direzioni di movimento $\displaystyle(\frac{3^3-1}{2})$ con 6 diagonali in più, ognuna delle quali introduce 2 cubetti, quindi +12, +24, +36, ecc…
Il guscio esterno ha $n^3-(n-2)^3$ cubetti, il secondo $(n-2)^3-(n-4)^3$, ecc…

Con 4 dimensioni abbiamo 4 assi, 6 piani, 4 cubi e 1 ipercubo, totale 15 direzioni $(2^4-1)$ e $15(n-1)$ "caselle" minacciate
Quando la regina si trova al centro di un ipercubo 3x3x3x3 ha 40 direzioni di movimento $\displaystyle(\frac{3^4-1}{2})$
L'ipersuperficie esterna ha $n^4-(n-2)^4$ "caselle"

In conclusione possiamo scrivere una formula che calcola la probabilità in funzione delle misure della scacchiera (n) e del numero di dimensioni (m)

$\displaystyle P_{RvsR}=\sum_{k=0}^{\frac{n}{2}-1}\frac{[(n-2k)^m-(n-2k-2)^m][(2^m-1)(n-1)+2k(\frac{3^m-1}{2}-2^m+1)]}{n^m(n^m-1)}$

Per m=1 esce 1 come ci si aspetterebbe
Per m=2 esce la formula già vista

SE&O

Si potrebbe pensare anche a una situazione più variegata, tipo Alfiere-Cavallo
[Sergio] / $17$

Rispondi