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: 1466
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: 1364
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: 789
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: 1364
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: 789
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: 789
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: 789
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: 1466
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 873 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 873 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 873 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 873 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 873 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 873 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: 789
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$

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

Re: Regine, torre e alfiere su una scacchiera

Messaggio da panurgo »

Quelo ha scritto:
gio set 15, 2022 10:17 pm
Il caso delle regine si dovrebbe poter estendere a scacchiere con più di 2 dimensioni
Visto quanto sopra non ho potuto esimermi dal raccogliere il guanto lanciato da Sergio. Il percorso è stato lungo e il mio post non può che esserlo anch’esso: vi chiedo venia e vi invito a non scoraggiarvi e a leggerlo lo stesso.

Fin da subito il risultato di Sergio mi ha lasciato perplesso perché la sua derivazione mi sembrava un po’ troppo facile: effettivamente, se consideriamo la scacchiera $3\times 3\times 3$, la fomula diventa

$\displaystyle\sum_{k=0}^{\frac32-1}\frac{\left[\left(3-2k\right)^3-\left(1-2k\right)^3\right]\left(14+12k\right)}{702}$

Abbiamo solo $k=0$ e il conteggio è

$\displaystyle\frac{\left(3^3-1^3\right)14}{702}=\frac{364}{702}=\frac{14}{27}$

Non è difficile contare quante sono le caselle controllate da una regina su questa scacchiera (cfr. figura)
G110.20.01.png
G110.20.01.png (93.34 KiB) Visto 255 volte
dalla casella centrale si controllano $26$ caselle, da una casella “di faccia” se ne controllano $18$, da una “di spigolo” e da una “di vertice” $14$: mettiamo tutto in tabella

$\begin{array}{|lrrr|C}
\hline
\text{centro} & 1 & 26 & 26 \\
\text{faccia} & 6 & 18 & 108 \\
\text{spigolo} & 12 & 14 & 168 \\
\text{vertice} & 8 & 14 & 112 \\
\hline
\text{totale} & & & 414 \\
\hline
\end{array}$

Quindi il risultato corretto dovrebbe essere

$\displaystyle\frac{414}{702}=\frac{23}{39}$

Ho cominciato dunque a ripetere in tre dimensioni l’analisi che avevo compiuto per la scacchiera $n\times n$ e mi sono reso conto immediatamente che l’intuizione geometrica che mi aveva guidato in quel caso non bastava in questo.
Infatti, io pensavo alla scacchiera come “righe e colonne” contrapposte a “diagonali”, con l’Alfiere che si muove su diagonali formate da caselle dello stesso colore e la Torre che si muove su righe e colonne formate da caselle di colore alternato: ora, nella scacchiera tridimensionale vi sono le “righe e colonne” e vi sono le “diagonali” ma alcune di quest’ultime sono monocolori, altre sono a colori alternati. Ecco dunque che il trattare tutte le direzioni che non sono perpendicolari alle facce del cubo nella stessa maniera, il termine $2k\left(\left(3^m-1\right)/2-2^m+1\right)$ della formula di Sergio, non sembra adeguato.
Il concetto di “diagonali” contrapposte a “righe e colonne” viene a perdere il suo significato al crescere del numero di dimensioni e l’astrazione, che Sergio ha fatto implicitamente, di passare al concetto più generale di “direzione” consente di sfruttare meglio le simmetrie, come vedremo. Il secondo passaggio verso l’astratto è stato quello di abbandonare del tutto l’intuizione geometrica per passare all’algebra: ecco qua il mio viaggio.
Una regina posta in una casella interna di una scacchiera $n^d$ è completamente circondata da caselle adiacenti: ciò significa che possiamo vedere un po’ di luce studiando il caso più semplice di una regina posta al centro di una scacchiera $3^d$.
Identifichiamo tale casella mediante la $d$-pla ordinata $\left(2,2,\ldots,2\right)$; le caselle adiacenti differiranno almeno per il valore di uno degli indici, ad esempio $\left(1,2,\ldots,2\right)$ o $\left(3,2,\ldots,2\right)$: osserviamo che le caselle $\left(1,2,\ldots,2\right)$ e $\left(3,2,\ldots,2\right)$ sono simmetriche rispetto al centro.
Naturalmente possono variare quanti e quali indici si vogliono, ad esempio i primi due: $\left(1,1,\ldots,2\right)$, $\left(1,3,\ldots,2\right)$, $\left(3,1,\ldots,2\right)$ e $\left(3,3,\ldots,2\right)$, con $\left(1,1,\ldots,2\right)$, $\left(1,3,\ldots,2\right)$ e $\left(3,1,\ldots,2\right)$, $\left(3,3,\ldots,2\right)$ simmetriche a coppie rispetto al centro.
Conveniamo di classificare le caselle in funzione del numero di indici che variano rispetto alla casella centrale osservando che per caselle adiacenti tutti gli indici che variano, variano di $\pm 1$ cioè della stessa quantità in valore assoluto.
Scriviamo ora l’enunciato del Teorema Binomiale

$\displaystyle 3^d=\left(2+1\right)^d={d\choose 0}2^0+{d\choose 1}2^1+\cdots+{d\choose d}2^d$

Precisamente, abbiamo ${d\choose k}2^k$ caselle di classe $k$ perché ci sono ${d\choose k}$ modi di scegliere $k$ indici e due valori possibili per ciascuno dei $k$ indici che variano: mettiamo in tabella tali coefficienti

$\begin{array}{l|ccccccC}
d\text{ \ }k & 0& 1 &2 & 3 & 4 & \cdots \\
\hline
0 & 1 & & & & & \\
1 & 1 & 2 & & & & \\
2 & 1 & 4 & 4 & & & \\
3 & 1 & 6 & 12 & 8 & & \\
4 & 1 & 8 & 24 & 32 & 16 & \\
\vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \ddots &
\end{array}$

Il significato di tutto ciò è che un punto ha solo un centro, un segmento ha un centro e due estremi, un quadrato ha un centro, quattro lati e quattro vertici mentre un cubo ha un centro, sei facce, dodici spigoli e otto vertici; il tesseratto o $4$-cubo ha un centro, $8$ facce cubiche, $24$ facce quadrate, $32$ spigoli e $16$ vertici ecc.
Ogni coppia di caselle tra loro simmetriche rispetto al centro identifica una direzione: avremo dunque ${d\choose 1}2^0$ direzioni di classe $1$, ${d\choose 2}2^1$ direzioni di classe $2$ e, in generale, ${d\choose k}2^{k-1}$ direzioni di classe $k$ per un totale di $\frac{3^d-1}2$ direzioni (vi ricorda qualcosa?).
Osserviamo ora come sono fatte le scacchiere $3^d$, diagrammando le sezioni bidimensionali per $d>2$.
$d=0$
G110.20.02.png
G110.20.02.png (875 Byte) Visto 255 volte
$d=1$
G110.20.03.png
G110.20.03.png (1.79 KiB) Visto 255 volte
$d=2$
G110.20.04.png
G110.20.04.png (3.44 KiB) Visto 255 volte
$d=3$
G110.20.05.png
G110.20.05.png (8.66 KiB) Visto 255 volte
$d=4$
G110.20.06.png
G110.20.06.png (22.7 KiB) Visto 255 volte
Le direzioni di classe $k$ compaiono per la prima volta nella scacchiera $3^k$ e si ripetono identiche, solo in numero maggiore, nelle scacchiere successive, per esempio
G110.20.07.png
G110.20.07.png (5.93 KiB) Visto 255 volte
(ricordiamoci che parliamo di direzioni passanti per una data casella).
Possiamo stabilire dunque, per ciascuna scacchiera $n^k$, il numero medio $\mu_k$ di caselle controllate parallelamente a una delle direzioni di classe $k$ e usarlo per calcolare il numero di caselle controllate lungo tutte le direzioni di classe $k$ di questa scacchiera e delle scacchiere successive mediante la formula

$\displaystyle a_{d,k}={d\choose k}2^{k-1}n^d\mu_k$

cioè numero delle direzioni di classe $k$ di una scacchiera $n^d$ per numero di caselle della scacchiera stessa per numero medio di caselle per la direzione di classe $k$: il numero totale di mosse della regina per la scacchiera $n^d$ sarà

$\displaystyle a_d=\sum_{k=1}^d a_{d,k}=n^d\sum_{k=1}^d{d\choose k}2^{k-1}\mu_k$

Continua...
Ultima modifica di panurgo il gio nov 17, 2022 1:26 pm, modificato 1 volta in totale.
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"

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

Re: Regine, torre e alfiere su una scacchiera

Messaggio da panurgo »

Torna a pag. 1

Cominiciamo con calcolare i vari $\mu_k$: evidentemente $\mu_1=n-1$ e $a_1=a_{1,1}=n\left(n-1\right)$.
Per $d>1$ procediamo a contare per ciascuna casella il numero di caselle controllate nella direzione della diagonale principale cioè quella che passa per le caselle $\left(1,\ldots,1\right)$ e $\left(n,\ldots,n\right)$: per esempio, l’usuale scacchiera $8\times 8$ ha i seguenti valori
G110.20.08.png
G110.20.08.png (13.03 KiB) Visto 253 volte
L’altra direzione, perpendicolare ha questa, non può che avere gli stessi conteggi essendo equivalente per simmetria
G110.20.09.png
G110.20.09.png (12.95 KiB) Visto 253 volte
e lo stesso vale per tutte le direzioni di classe $k$ di una data scacchiera.
Per eseguire il conteggio, senza perderci in sommatorie varie, assumiamo che $n^2\mu_2$ sia un polinomio di terzo grado in $n$

$\displaystyle n^2\mu_2=a+bn+cn^2+dn^3$

così come

$\displaystyle n\mu_1=n\left(n-1\right)$

è un polinomio di secondo grado.
Per individuare i quattro coefficienti contiamo il numero di caselle controllate per $n$ da $1$ a $4$
G110.20.10.png
G110.20.10.png (10.17 KiB) Visto 253 volte
e scriviamo il sistema di equazioni

$\left\{\begin{array}{lC}
a+b+c+d=0 \\
a+2b+4c+8d=2 \\
a+3b+9c+27d=10 \\
a+4d+16c+64d=28
\end{array}\right.$

la cui soluzione è

$\left\{\begin{array}
\displaystyle a=0 \\
\displaystyle b=\frac13 \\
\displaystyle c=-1 \\
\displaystyle d=\frac23
\end{array}\right.$

ovvero

$\displaystyle\mu_2=\frac{n-3n^2+2n^3}{3n^2}=\frac{\left(n-1\right)\left(2n-1\right)}{3n}$

Per $d=3$ è possibile utilizzare una strategia simile se osserviamo che, come per $d=2$ vi sono due diagonali adiacenti alla diagonale principale, una “sopra” e una “sotto”,
G110.20.11.png
G110.20.11.png (5.53 KiB) Visto 253 volte
per $d=3$ le “diagonali adiacenti” sono sei
G110.20.12.png
G110.20.12.png (77.06 KiB) Visto 253 volte
quelle che si ottengono ruotando i due cubi di partenza della base della scacchiera (uno di classe $1$ e uno di classe $2$, quelli azzurri in figura) intorno alla diagonale principale che è un asse ternario di simmetria
G110.20.13.png
G110.20.13.png (6.55 KiB) Visto 253 volte
Per $d=2$ le successive “diagonali adiacenti” sono sempre due
G110.20.14.png
G110.20.14.png (5.69 KiB) Visto 253 volte
mentre per $d=3$ sono $12$, $18$ ecc. (vedi gli altri colori nella figura precedente a quella qui sopra): la diagonale principale contiene $n$ caselle da ciascuna delle quali si controllano le altre $n-1$ mentre le $3k$ “diagonali adiacenti” contengono $n-k$ caselle da ciascuna delle quali si controllano le altre $n-k-1$.
In totale

$\displaystyle n\left(n-1\right)+\sum_{k=0}^{n-1} 3k\left(n-k\right)\left(n-k-1\right)$

Scriveremo perciò

$\displaystyle n^3\mu_3=a+bn+cn^2+dn^3+en^4$

faremo i nostri conti per $n$ da $1$ a $5$

$\begin{array}{lC}
1\cdot\left(1\cdot 0\right)=0 \\
1\cdot\left(2\cdot 2\right)+6\cdot\left(1\cdot 0\right)=2 \\
1\cdot\left(3\cdot 2\right)+6\cdot\left(2\cdot 1\right)+12\cdot\left(1\cdot 0\right)=18 \\
1\cdot\left(4\cdot 3\right)+6\cdot\left(3\cdot 2\right)+12\cdot\left(2\cdot 1\right)+18\cdot\left(1\cdot 0\right)=78 \\
1\cdot\left(5\cdot 4\right)+6\cdot\left(4\cdot 3\right)+12\cdot\left(3\cdot 2\right)+18\cdot\left(2\cdot 1\right)+24\cdot\left(1\cdot 0\right)=200
\end{array}$

e avremo il sistema di equazioni

$\left\{\begin{array}{lC}
a+b+c+d+e=0 \\
a+2b+4c+8d+16e=2 \\
a+3b+9c+27d+81e=18 \\
a+4b+16c+64d+256e=72 \\
a+5b+25c+125d+625e=200
\end{array}\right.$

la cui soluzione è

$\left\{\begin{array}
\displaystyle a=0 \\
\displaystyle b=0 \\
\displaystyle c=\frac12 \\
\displaystyle d=-1 \\
\displaystyle e= \frac12
\end{array}\right.$

ovvero

$\displaystyle\mu_3=\frac{n^2-2n^3+n^4}{2n^3}=\frac{\left(n-1\right)^2}{2n}$

Mettiamo insieme quello che abbiamo finora

$\left\{\begin{array}{lC}
\displaystyle\mu_1=n-1 \\
\displaystyle\mu_2=\frac{n-3n^2+2n^3}{3n^2}=\frac{\left(n-1\right)\left(2n-1\right)}{3n} \\
\displaystyle\mu_3=\frac{n^2-2n^3+n^4}{2n^3}=\frac{\left(n-1\right)^2}{2n}
\end{array}\right.$

e

$\left\{\begin{array}{lC}
\displaystyle a_1=n{1\choose 1}2^0\mu_1=n\left(n-1\right) \\
\displaystyle a_2=n^2\sum_{k=1}^2{2\choose k}2^{k-1}\mu_k=\frac{2n\left(n-1\right)\left(5n-1\right)}3 \\
\displaystyle a_3=n^3\sum_{k=1}^3{3\choose k}2^{k-1}\mu_k=n^2\left(n-1\right)\left(9n-4\right)
\end{array}\right.$

con probabilità uguali a

$\left\{\begin{array}{lC}
\displaystyle p_1=\frac{n\left(n-1\right)}{n\left(n-1\right)}=1 \\
\displaystyle p_2=\frac{2n\left(n-1\right)\left(5n-1\right)}{3n^2\left(n^3-1\right)}=\frac{2n\left(5n-1\right)}{3n\left(n+1\right)} \\
\displaystyle p_3=\frac{n^2\left(n-1\right)\left(9n-4\right)}{n^3\left(n^3-1\right)}=\frac{9n-4}{n\left(n^2+n+1\right)}
\end{array}\right.$

Continua...
Ultima modifica di panurgo il ven nov 18, 2022 7:51 am, modificato 2 volte in totale.
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"

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

Re: Regine, torre e alfiere su una scacchiera

Messaggio da panurgo »

Torna a pag. 1

Torna a pag.2

Questo modo di procedere presenta due inconvenienti: il primo è che diventa sempre più difficile trovare un modo per contare le direzioni adiacenti alla diagonale principale; il secondo è che ci piacerebbe avere, se non una forma chiusa, perlomeno una sommatoria uguale per tutte le dimensioni che usi $d$ come estremo della sommatoria stessa.
Un modo di contare le mosse che dipenda solo dalla casella in cui si trova la regina viene, per qualsiasi dimensione, dalla buona vecchia Geometria Analitica.
Per una scacchiera $n^d$, delle $2^{d-1}$ direzioni di classe $d$ che passano per la casella $\text{C}\equiv\left(i_1,i_2,\ldots,i_d\right)$ consideriamo quella parallela alla diagonale passante per le caselle $\left(1,1,\ldots,1\right)$ e $\left(n,n,\ldots,n\right)$, la cui equazione è

$\displaystyle\frac{x_1-i_1}{c_1}=\frac{x_2-i_2}{c_2}=\cdots=\frac{x_d-i_d}{c_d}$

Sappiamo che, come tutte le nostre direzioni, anche questa passa per caselle adiacenti per cui i coefficienti direttori sono tutti uguali dato che tutti gli indici variano della stessa quantità: l’equazione diventa

$\displaystyle x_1-i_1=x_2-i_2=\cdots=x_d-i_d$

La scacchiera è delimitata da spazi $d-1$: punti per una scacchiera lineare, rette per una scacchiera quadrata, piani per una scacchiera cubica ecc.
Le equazioni dei sottospazi limite sono

$\begin{array}{cC}
x_1=1 & x_2=1 & \cdots & x_d=1
\end{array}$

da una parte e

$\begin{array}{cC}
x_1=n & x_2=n & \cdots & x_d=n
\end{array}$

dall’altra.
Le intersezioni della retta con tali sottospazi si ottengono rifacendo mutatis mutandis il seguente ragionamento

$\left\{\begin{array}{lC}
x_1-i_1=x_2-i_2=\cdots=x_d-i_d \\
x_1=1
\end{array}\right.
\qquad\Longrightarrow\qquad
1-i_1=x_2-i_2=\cdots=x_d-i_d $

cioè

$\left\{\begin{array}{lC}
x_1=1 \\
x_2=i_2-i_1+1 \\
\vdots \\
x_d=i_d-i_1+1
\end{array}\right.$

e sono

$\begin{array}{cC}
\text{I}_1=\left(\;\mathbf{1}\;,i_2-i_1+1,\ldots,i_d-i_1+1\right) \\
\\
\text{I}_2=\left(i_1-i_2+1,\;\mathbf{1}\;,\ldots,i_d-i_2+1\right) \\
\\
\vdots \\
\\
\text{I}_d=\left(i_1-i_d+1,i_2-i_d+1,\ldots,\;\mathbf{1}\;\right)
\end{array}$


da una parte e


$\begin{array}{cC}
\text{J}_1=\left(\;\mathbf{n}\;,i_2-i_1+n,\ldots,i_d-i_1+n\right) \\
\\
\text{J}_2=\left(i_1-i_2+n,\;\mathbf{n}\;,\ldots,i_d-i_2+n\right) \\
\\
\vdots \\
\\
\text{J}_d=\left(i_1-i_d+n,i_2-i_d+n,\ldots,\;\mathbf{n}\;\right)
\end{array}$


dall’altra.
La distanza di $\text{C}$ da ciascuna intersezione, misurata in numero di caselle, è uguale per tutte le coordinate (caselle adiacenti, coefficienti direttori uguali ecc.) quindi avremo semplicemente

$\begin{array}{cC}
\overline{\text{CI}_1}=i_1-1\quad & \quad\overline{\text{CI}_2}=i_2-1\quad & \cdots & \quad\overline{\text{CI}_d}=i_d-1
\end{array}$

da una parte e

$\begin{array}{cC}
\overline{\text{CJ}_1}=n-i_1\quad & \quad\overline{\text{CJ}_2}=n-i_2\quad & \cdots & \quad\overline{\text{CJ}_d}=n-i_d
\end{array}$

dall’altra.

Osserviamo, prendendo come esempio la proiezione nel sottospazio bidimensionale misurato da $x_1$ e $x_2$, che una delle distanze sarà in generale più corta delle altre.
G110.20.15.png
G110.20.15.png (18.29 KiB) Visto 251 volte
Per ottenere il numero di caselle controllate da una regina posta in $\text{C}$ non dobbiamo fare altro che sommare tra loro la minore delle distanze in entrambi i versi

$a\left(C\right)=\min\left(\underline{i}-1\right)+\min\left(n-\underline{i}\right)$

dove $\underline{i}$ è il vettore dei coefficienti. Ma

$\min\left(\underline{i}-1\right)=\min\underline{i}-1$

e

$\min\left(n-\underline{i}\right)=n-\max\underline{i}$

per cui

$a\left(C\right)=\left(n-1\right)-\left(\max\underline{i}-\min\underline{i}\right)$

Ci conforta osservare che questo è esattamente ciò che abbiamo visto per la scacchiera ordinaria $8\times 8$
G110.20.16.png
G110.20.16.png (13.03 KiB) Visto 251 volte
Nel caso generale, il numero medio di caselle controllate dalla regina parallelamente alla direzione di classe $d$ è dato dalla sommatoria

$\displaystyle\mu_d=\frac1{n^d}\sum_{i_1=1}^n\cdots\sum_{i_d=1}^n\left[\left(n-1\right)-\left(\max\underline{i}-\min\underline{i}\right)\right]=\left(n-1\right)-\frac1{n^d}\sum_{i_1=1}^n\cdots\sum_{i_d=1}^n\left(\max\underline{i}-\min\underline{i}\right)$

Per affrontare questa sommatoria dall’apparenza temibile cominciamo a considerare i casi più semplici: per $d=1$

$\displaystyle\mu_1=\left(n-1\right)-\frac1{n^1}\sum_{i_1=1}^n\left(\max\underline{i}-\min\underline{i}\right)=\left(n-1\right)$

poichè, avendo una sola dimensione, $\max\underline{i}=\min\underline{i}=i_1$ e lo scarto è zero.

Per $d=2$

$\displaystyle\mu_2=\left(n-1\right)-\frac1{n^2}\sum_{i_1=1}^n\sum_{i_2=1}^n\left[\max\left(i_1,i_2\right)-\min\left(i_1,i_2\right)\right]$

Per ogni valore di $i_1$ prima $i_2<i_1$, ad un certo punto $i_2=i_1$ e dopo $i_2>i_1$
G110.20.17.png
G110.20.17.png (17.93 KiB) Visto 251 volte
Possiamo quindi spezzare la somma in tre parti

$\displaystyle\mu_2=\left(n-1\right)-\frac1{n^2}\left\{\sum_{i_1=2}^n\sum_{i_2=1}^{i_1-1}\left(i_1-i_2\right)+\sum_{i_1=1}^n\sum_{i_2=i_1}^{i_1}\left(i_1-i_2\right)+\sum_{i_1=1}^{n-1}\sum_{i_2=i_1+1}^n\left(i_2-i_1\right)\right\}$

Osserviamo che per $i_2=i_1$ la doppia sommatoria si comporta come una sommatoria unica poiché i due indici corrono insieme; inoltre, massimo e minimo degli indici coincidono e

$\displaystyle\sum_{i_1=1}^n\sum_{i_2=i_1}^{i_1}\left(i_1-i_2\right)=\sum_{i_1=i_2=1}^n\left(i_1-i_2\right)=0$

come nel caso monodimensionale.
Le altre due sommatorie sono equivalenti per simmetria, lo scambio di $i_1$ con $i_2$, come si può vedere riordinando i termini della seconda sommatoria

$\displaystyle\sum_{i_1=1}^{n-1}\sum_{i_2=i_1+1}^n\left(i_2-i_1\right)=\sum_{i_2=2}^n\sum_{i_1=1}^{i_2-1}\left(i_2-i_1\right)=\sum_{i_1=2}^n\sum_{i_2=1}^{i_1-1}\left(i_1-i_2\right)$

o, sinteticamente, sulla scacchiera $8\times 8$ di prima
G110.20.16.png
G110.20.16.png (13.03 KiB) Visto 251 volte
dalla quale si evince che la metà con $i_2<i_1$ e quella con $i_1<i_2$ danno la stessa sommatoria.
Abbiamo dunque

$\displaystyle\mu_2=\left(n-1\right)-\frac{S_1+2S_2}{n^2}$

dove

$\displaystyle S_1=\sum_{i_1=1}^n\left(i_1-i_1\right)=0$

e

$\displaystyle S_2=\sum_{i_1=2}^n\sum_{i_2=1}^{i_1-1}\left(i_1-i_2\right)=\frac{\left(n+1\right)n\left(n-1\right)}6$

per cui

$\displaystyle\mu_2=\frac{\left(n-1\right)\left(2n-1\right)}{3n}$

come abbiamo trovato in precedenza.

Per $d=3$ abbiamo tre indici

$\begin{array}{|cc|C}
\hline
i_1\;\left(S_1\right) &
\begin{array}{|c|cC}
i_2<i_1\;\left(S_2\right) &
\begin{array}{cC}
i_3<i_2<i_1\;\left(S_3\right) \\
i_3=i_2<i_1\;\left(S_2\right) \\
i_2<i_3<i_1\;\left(S_3\right) \\
i_2<i_3=i_1\;\left(S_2\right) \\
i_2<i_1<i_3\;\left(S_3\right)
\end{array} \\
\hline
i_2=i_1\;\left(S_1\right) &
\begin{array}{cC}
i_3<i_2=i_1\;\left(S_2\right) \\
i_3=i_2=i_1\;\left(S_1\right) \\
i_2=i_1<i_3\;\left(S_2\right)
\end{array} \\
i_1<i_2\;\left(S_2\right) &
\hline
\begin{array}{cC}
i_3<i_1<i_2\;\left(S_3\right) \\
i_3=i_1<i_2\;\left(S_2\right) \\
i_1<i_3<i_2\;\left(S_3\right) \\
i_1<i_3=i_2\;\left(S_2\right) \\
i_1<i_2<i_3\;\left(S_3\right)
\end{array}
\end{array} \\
\hline
\end{array}$

cioè

$\displaystyle\mu_3=\left(n-1\right)-\frac{S_1+6S_2+6S_3}{n^3}$

con

$\displaystyle S_3=\sum_{i_1=3}^n\sum_{i_2=2}^{i_1-1}\sum_{i_3=1}^{i_2-1}\left(i_1-i_3\right)=\frac{\left(n+1\right)n\left(n-1\right)\left(n-2\right)}{12}$

e

$\displaystyle\mu_3=\frac{\left(n-1\right)^2}{2n}$

Per $d=4$ abbiamo un indice in più

$\begin{array}{|cc|C}
\hline
i_1\;\left(S_1\right) &
\begin{array}{|ccC}
i_2<i_1\;\left(S_2\right) &
\begin{array}{|ccC}
i_3<i_2<i_1\;\left(S_3\right) &
\begin{array}{|cC}
i_4<i_3<i_2<i_1\;\left(S_4\right) \\
i_4=i_3<i_2<i_1\;\left(S_3\right) \\
\vdots
\end{array}
\end{array}
\end{array} \\
\hline
\end{array}$

Non continuo la tabella perché ciò che avviene è evidente: l’indice aggiunto scorre lungo gli indici precedenti

$i_4<i_3<i_2<i_1\quad\to\quad i_4=i_3<i_2<i_1\quad\to\quad i_3<i_4<i_2<i_1\quad\to\quad\cdots\quad\to\quad i_3<i_2<i_1<i_4$

e produce (con questo set di indici) quattro somme con quattro indici e tre somme con tre indici; sappiamo che due indici uguali si comportano come un indice solo

$i_4<\left(i_3=i_2\right)<i_1\quad\to\quad i_4=\left(i_3=i_2\right)<i_1\quad\to\quad \left(i_3=i_2\right)<i_4<i_1\quad\to\quad\cdots\quad\to\quad \left(i_3=i_2\right)<i_1<i_4$

e (ancora in questo caso) lo scorrimento dell’indice aggiunto produce tre somme con tre indici e due con due indici.
La regola per scrivere i coefficienti è evidente: ogni raggruppamento dei $d$ indici equivalente a $k$ indici produce $k$ somme con $k$ indici e $k+1$ somme con $k+1$ indici ovvero

$\displaystyle T_{d+1,k+1}=\left(k+1\right)\left(T_{d,k}+T_{d,k+1}\right)$

Questo è l’inizio della tabella dei coefficienti

$\begin{array}{l|ccccccC}
d\text{ \ }k & 1& 2 & 3 & 4 & 5 & \cdots \\
\hline
1 & 1 & & & & & \\
2 & 1 & 2 & & & & \\
3 & 1 & 6 & 6 & & & \\
4 & 1 & 14 & 36 & 24 & & \\
5 & 1 & 30 & 150 & 240 & 120 & \\
\vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \ddots &
\end{array}$

Se ora dividiamo ciascun coefficiente per $k!$ otteniamo i seguenti numeri

$\begin{array}{l|ccccccC}
d\text{ \ }k & 1& 2 & 3 & 4 & 5 & \cdots \\
\hline
1 & 1 & & & & & \\
2 & 1 & 1 & & & & \\
3 & 1 & 3 & 1 & & & \\
4 & 1 & 7 & 6 & 1 & & \\
5 & 1 & 15 & 25 & 10 & 1 & \\
\vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \ddots &
\end{array}$

Questa tabella è il triangolo dei numeri di Stirling del secondo tipo, $\left\{\begin{array}{cC} d \\ k \end{array}\right\}$, numeri che contano in quanti modi un insieme di $d$ elementi può essere diviso in $k$ partizioni: un insieme di un elemento può essere diviso in una partizione in un solo modo

$\begin{array}{cC}
1 \quad & \quad\left\{1\right\}
\end{array}$

le partizioni di un insieme di due elementi sono

$\begin{array}{cC}
1 \quad & \quad\left\{1,2\right\} \\
2 \quad & \quad\left\{1|2\right\}
\end{array}$

quelle di un insieme di tre elementi sono

$\begin{array}{cC}
1 \quad & & \quad\left\{1,2,3\right\} & \\
2 \quad & \quad\left\{1,2|3\right\} & \quad\left\{1,3|,2\right\} & \quad\left\{1|2,3\right\} \\
3 \quad & & \quad\left\{1|2|3\right\} &
\end{array}$

ecc.

Come abbiamo già ripetuto, quando due o più indici sono uguali si comportano come un indice solo quindi un gruppo di $d$ indici corrispondente a $k$ indici è un insieme di $d$ oggetti con $k$ partizioni che possono essere ordinate in $k!$ modi: ecco perché i coefficienti sono $T_{d,k}=\left\{\begin{array}{cC} d \\ k \end{array}\right\}k!$.

Tornando a $\mu_4$ abbiamo

$\displaystyle\mu_4=\left(n-1\right)-\frac{S_1+14S_2+36S_3+24S_4}{n^4}$

con

$\displaystyle S_4=\sum_{i_1=4}^n\sum_{i_2=3}^{i_1-1}\sum_{i_3=2}^{i_2-1}\sum_{i_4=1}^{i_3-1}\left(i_1-i_4\right)=\frac{\left(n+1\right)n\left(n-1\right)\left(n-2\right)\left(n-3\right)}{40}$

ovvero

$\displaystyle\mu_4=\frac{\left(n-1\right)\left(2n-1\right)\left(3n^2-3n-1\right)}{15n^3}$

(N.B.: tutta quest’algebra e queste sommatorie le ho fatte fare a WolframAlpha).

I numeri di Stirling del secondo tipo hanno una bella formula

$\displaystyle\left\{\begin{array}{cC} d \\ k \end{array}\right\}=\frac1{k!}\sum_{j=0}^k\left(-1\right)^j{k\choose j}\left(k-j\right)^d$

che ci consente di calcolare facilmente i nostri coefficienti

$\displaystyle T_{d,k}=\left\{\begin{array}{cC} d \\ k \end{array}\right\}k!=\sum_{j=0}^k\left(-1\right)^j{k\choose j}\left(k-j\right)^d $

La formula per i numeri di Stirling del secondo tipo si dimostra con il Principio di Esclusione-Inclusione: io me ne guarderò bene.

Cerchiamo ora una forma chiusa per le somme $S_k$, chiedendo aiuto a WolframAlpha

$\begin{array}{lC}
\displaystyle S_1=0 \\
\displaystyle S_2=\frac{\left(n+1\right)n\left(n-1\right)}6 \\
\displaystyle S_3=\frac{\left(n+1\right)n\left(n-1\right)\left(n-2\right)}{12} \\
\displaystyle S_4=\frac{\left(n+1\right)n\left(n-1\right)\left(n-2\right)\left(n-3\right)}{40} \\
\displaystyle S_5=\frac{\left(n+1\right)n\left(n-1\right)\left(n-2\right)\left(n-3\right)\left(n-4\right)}{180}
\end{array}$

Se per questi esempi iniziali completiamo il fattoriale al numeratore otteniamo

$\begin{array}{lC}
\displaystyle S_1=0=0{{n+1}\choose{1+1}}=\left(1-1\right){{n+1}\choose{1+1}} \\
\displaystyle S_2=\frac{\left(n+1\right)n\left(n-1\right)\left(n-2\right)!}{6\left(n-2\right)!}=1{{n+1}\choose{2+1}}=\left(2-1\right){{n+1}\choose{2+1}} \\
\displaystyle S_3=\frac{\left(n+1\right)n\left(n-1\right)\left(n-2\right)\left(n-3\right)!}{12\left(n-3\right)!}=2{{n+1}\choose{3+1}}=\left(3-1\right){{n+1}\choose{3+1}} \\
\displaystyle S_4=\frac{\left(n+1\right)n\left(n-1\right)\left(n-2\right)\left(n-3\right)\left(n-4\right)!}{40\left(n-4\right)!}=3{{n+1}\choose{4+1}}=\left(4-1\right){{n+1}\choose{4+1}} \\
\displaystyle S_5=\frac{\left(n+1\right)n\left(n-1\right)\left(n-2\right)\left(n-3\right)\left(n-4\right)\left(n-5\right)!}{180\left(n-5\right)!}=4{{n+1}\choose{5+1}}=\left(5-1\right){{n+1}\choose{5+1}}
\end{array}$

cioè, per inferenza,

$\displaystyle S_k=\left(k-1\right){{n+1}\choose{k+1}}$

Mi accontento di questa congettura con la quale otteniamo

$\displaystyle\mu_m=\left(n-1\right)-\frac1{n^m}\sum_{k=1}^m\sum_{j=0}^k\left(-1\right)^j{k\choose j}{{n+1}\choose{k+1}}\left(k-1\right)\left(k-j\right)^m$

e le formule definitive

$\displaystyle a_d=n^d\sum_{m=1}^d{d\choose m}2^{m-1}\left[\left(n-1\right)-\frac1{n^m}\sum_{k=1}^m\sum_{j=0}^k\left(-1\right)^j{k\choose j}{{n+1}\choose{k+1}}\left(k-1\right)\left(k-j\right)^m\right]$

e

$\displaystyle p_d=\frac{a_d}{n^d\left(n^d-1\right)}=\frac1{n^d-1}\sum_{m=1}^d{d\choose m}2^{m-1}\left[\left(n-1\right)-\frac1{n^m}\sum_{k=1}^m\sum_{j=0}^k\left(-1\right)^j{k\choose j}{{n+1}\choose{k+1}}\left(k-1\right)\left(k-j\right)^m\right]$
Ultima modifica di panurgo il sab nov 19, 2022 11:42 am, modificato 3 volte in totale.
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: 789
Iscritto il: ven giu 16, 2006 3:34 pm

Re: Regine, torre e alfiere su una scacchiera

Messaggio da Quelo »

Grandioso! :D

Beh dai, c'ero quasi :P
[Sergio] / $17$

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

Re: Regine, torre e alfiere su una scacchiera

Messaggio da panurgo »

panurgo ha scritto:
gio nov 17, 2022 1:32 pm
cioè, per inferenza,

$\displaystyle S_k=\left(k-1\right){{n+1}\choose{k+1}}$

Mi accontento di questa congettura...
In realtà non sono il tipo che si accontenta facilmente e sto continuando a rimuginarci su. Qualche passetto in avanti lo ho fatto: lo scrivo per non dimenticarlo.

Consideriamo un $k$-cubo di lato $n$: il suo volume è

$\displaystyle V_k=\int_0^n\int_0^n\cdots\int_0^n dx_k\cdots dx_2 dx_1=n^k$

Il volume della parte del $k$-cubo nella quale $x_1>x_2>x_3>\cdots>x_k$ è

$\displaystyle v_k=\int_0^n\int_0^{x_1}\cdots\int_0^{x_{k-1}} dx_k\cdots dx_2 dx_1=\frac{n^k}{k!}$

poiché ognuna delle $k!$ diverse permutazioni degli indici

$\begin{array}{lC}
x_1>x_2>x_3>\cdots>x_k \\
x_2>x_1>x_3>\cdots>x_k \\
x_2>x_3>x_1>\cdots>x_k \\
\vdots \\
x_3>x_1>x_2>\cdots>x_k \\
x_3>x_2>x_1>\cdots>x_k \\
\vdots \\
x_k>x_{k-1}>x_{k-2}>\cdots>x_1
\end{array}$

corrisponde ad una parte del cubo diversa e tutte queste parti devono avere lo stesso volume per simmetria.
D’altra parte, l’integrale non è difficile da calcolare tenendo conto che

$\displaystyle\int\frac{x^k}{k!}dx=\frac1{k!}\int x^k dx=\frac1{k!}\cdot\frac{x^{k+1}}{k+1}=\frac{x^{k+1}}{\left(k+1\right)!}$

e il primo dei $k$ integrali è

$\displaystyle v_k=\int_0^n\int_0^{x_1}\cdots\int_0^{x_{k-1}} \frac{x_k^0}{0!}dx_k\cdots dx_2 dx_1$

quindi

$\displaystyle v_k=\int_0^n\int_0^{x_1}\cdots\int_0^{x_{k-2}} \left[\frac{x_k^1}{1!}\right]_0^{x_{k-1}}dx_{k-1}\cdots dx_2 dx_1=\int_0^n\int_0^{x_1}\cdots\int_0^{x_{k-2}} \frac{x_{k-1}^1}{1!} dx_{k-1}\cdots dx_2 dx_1$

Il risultato del $k$-esimo integrale sarà

$\displaystyle v_k=\left[\frac{x_1^k}{k!}\right]_0^n=\frac{n^k}{k!}$

QED

Osserviamo che per la corrispondente scacchiera $n^k$ la parte di caselle per le quali $ i_1>i_2>⋯>i_k $ è data dalla sommatoria

$\displaystyle s_k=\sum_{i_1=1}^n\sum_{i_2=1}^{i_1-1}\cdots\sum_{i_k=1}^{i_{k-1}-1} 1$

Anche questo è un volume, espresso come numero di caselle.

Consideriamo ora l’integrale

$\displaystyle I_k=\int_0^n\int_0^{x_1}\cdots\int_0^{x_{k-1}}\left(x_1-x_k\right)dx_k\cdots dx_2 dx_1$

che è l’analogo della sommatoria

$\displaystyle S_k=\sum_{i_1=1}^n\sum_{i_2=1}^{i_1-1}\cdots\sum_{i_k=1}^{i_{k-1}-1}\left(i_1-i_k\right)$

Questo integrale va via spedito

$\displaystyle I_k=I_1-I_2=\int_0^n\int_0^{x_1}\cdots\int_0^{x_{k-1}}x_1 dx_k\cdots dx_2 dx_1-\int_0^n\int_0^{x_1}\cdots\int_0^{x_{k-1}}x_k dx_k\cdots dx_2 dx_1$

con

$\left\{\begin{array}{lC}
\displaystyle I_1=\int_0^n x_1\int_0^{x_1}\cdots\int_0^{x_{k-1}} \frac{x_k^0}{0!}dx_k\cdots dx_2 dx_1 \\
\displaystyle I_2=\int_0^n\int_0^{x_1}\cdots\int_0^{x_{k-1}}\frac{x_k^1}{1!}dx_k\cdots dx_2 dx_1
\end{array}\right.$

quindi

$\left\{\begin{array}{lC}
\displaystyle I_1=\int_0^n x_1\int_0^{x_1}\cdots\int_0^{x_{k-2}} \frac{x_{k-1}^1}{1!}dx_{k-1}\cdots dx_2 dx_1 \\
\displaystyle I_2=\int_0^n\int_0^{x_1}\cdots\int_0^{x_{k-2}}\frac{x_{k-1}^2}{2!}dx_{k-1}\cdots dx_2 dx_1
\end{array}\right.$

e, alla fine,

$\left\{\begin{array}{lC}
\displaystyle I_1=\int_0^n x_1\frac{x_1^{k-1}}{\left(k-1\right)!}dx_1=\int_0^n\frac{x_1^k}{\left(k-1\right)!}dx_1=\frac{n^{k+1}}{\left(k-1\right)!\left(k+1\right)}=\frac{kn^{k+1}}{\left(k +1\right)!} \\
\displaystyle I_2=\int_0^n\frac{x_1^k}{k!}dx_1=\frac{n^{k+1}}{\left(k +1\right)!}
\end{array}\right.$

Riassumendo

$\displaystyle I_k=I_1-I_2=\frac{\overbrace{n\times n\times\cdots\times n}^{k+1}}{\left(k+1\right)!/\left(k-1\right)}$

mentre la mia congettura è

$\displaystyle S_k=\left(k-1\right){{n+1}\choose{k+1}}=\frac{\overbrace{\left(n+1\right)\times n\times\cdots\times\left(n-k+1\right)}^{k+1}}{\left(k+1\right)!/\left(k-1\right)}$

La parte numerica, il denominatore, è uguale: la differenza nei numeratori deriva, a mio avviso, da un “effetto di bordo” cioè dal fatto che la differenza minima tra un indice della sommatoria e il successivo è $1$ mentre due variabili successive possono avvicinarsi quanto vogliono.
A supporto di ciò osserviamo che

$\displaystyle\lim_{n\to\infty}\frac{S_k}{I_k}=\lim_{n\to\infty}\frac{\left(n+1\right)\times n\times\cdots\times\left(n-k+1\right)}{n^{k+1}}=1$

essendo numeratore e denominatore due polinomi di grado $k+1$ in $n$.

Continuerò a rimuginare...
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"

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

Re: Regine, torre e alfiere su una scacchiera

Messaggio da panurgo »

panurgo ha scritto:
gio nov 24, 2022 2:25 pm
Continuerò a rimuginare...
Rimuginai :roll:


Vi ricordate di questo integrale?

$\displaystyle\int_0^n\frac{x^k}{k!}dx=\frac{n^{k+1}}{(k+1)!}$

La sommatoria equivalente è

$\displaystyle\sum_{i=0}^n\frac{i(i-1)\cdots(i-k+1)}{k!}=\frac{(n+1)n(n-1)\cdots(n-k+1)}{(k+1)!}$

Osserviamo che

$\displaystyle\frac{i(i-1)\cdots(i-k+1)}{k!}=\frac{i(i-1)\cdots(i-k+1)}{k!}\cdot\frac{(i-k)!}{(i-k)!}={i\choose k}$

per cui la sommatoria diventa

$\displaystyle\sum_{i=0}^n\frac{i(i-1)\cdots(i-k+1)}{k!}=\frac{(n+1)n(n-1)\cdots(n-k+1)}{(k+1)!}\qquad\Longrightarrow\qquad\sum_{i=0}^n{i\choose k}={{n+1}\choose{k+1}}$

Il numeratore della frazione è il polinomio in $i$

$\displaystyle P(i)=i(i-1)\cdots(i-k+1)$

i cui zeri sono $\{0,1,\ldots,k-1 \}$: di conseguenza

$\displaystyle\sum_{i=0}^n{i\choose k}=\sum_{i=k}^n{i\choose k}={{n+1}\choose{k+1}}$

L’identità di destra è presto dimostrata:
G110.40.503x640.png
G110.40.503x640.png (46.89 KiB) Visto 45 volte
prendiamo dal triangolo di Pascal-Tartaglia, come esempio, l’elemento ${6\choose3}$ e osserviamo che è dato dalla somma di ${5\choose3}$ e ${5\choose2}$; ma ${5\choose3}$ è dato dalla somma di ${4\choose3}$ e ${4\choose2}$ ecc.: l’identità segue da ciò, dato che questo esempio fa uso solo della definizione ricorsiva ${n\choose k}={{n-1}\choose k}+{{n-1}\choose{k-1}}$, valida per tutti i coefficienti binomiali.

Consideriamo ora la sommatoria

$\displaystyle S_k=\sum_{i_1=1}^n\sum_{i_2=1}^{i_1-1}\cdots\sum_{i_k=1}^{i_{k-1}-1}(i_1-i_k)$

Come nel caso del corrispondente integrale la spezziamo in due termini

$\displaystyle S_k=S_1-S_2=\sum_{i_1=1}^n\sum_{i_2=1}^{i_1-1}\cdots\sum_{i_k=1}^{i_{k-1}-1}i_1-\sum_{i_1=1}^n\sum_{i_2=1}^{i_1-1}\cdots\sum_{i_k=1}^{i_{k-1}-1}i_k$

con

$\left\{\begin{array}{lC}
\displaystyle S_1=\sum_{i_1=1}^n i_1\sum_{i_2=1}^{i_1-1}\cdots\sum_{i_k=1}^{i_{k-1}-1}1 \\
\displaystyle S_2=\sum_{i_1=1}^n\sum_{i_2=1}^{i_1-1}\cdots\sum_{i_k=1}^{i_{k-1}-1}i_k
\end{array}\right.$

Ma $1$ può essere scritto come ${i_k\choose 0}$ e $i_k$ come ${i_k\choose1}$ per cui

$\left\{\begin{array}{lC}
\displaystyle S_1=\sum_{i_1=1}^n i_1\sum_{i_2=1}^{i_1-1}\cdots\sum_{i_k=1}^{i_{k-1}-1}{i_k\choose 0} \\
\displaystyle S_2=\sum_{i_1=1}^n\sum_{i_2=1}^{i_1-1}\cdots\sum_{i_k=1}^{i_{k-1}-1}{i_k\choose1}
\end{array}\right.$

La seconda sommatoria procede spedita

$\displaystyle S_2=\sum_{i_1=1}^n\sum_{i_2=1}^{i_1-1}\cdots\sum_{i_k=1}^{i_{k-1}-1}{i_k\choose1}
=\sum_{i_1=1}^n\sum_{i_2=1}^{i_1-1}\cdots\sum_{i_{k-1}=1}^{i_{k-2}-1}{i_{k-1}\choose2}
=\sum_{i_1=1}^n\sum_{i_2=1}^{i_1-1}\cdots\sum_{i_{k-2}=1}^{i_{k-3}-1}{i_{k-2}\choose3}$

fino a

$\displaystyle S_2
=\sum_{i_1=1}^n\sum_{i_2=1}^{i_1-1}{i_2\choose{k-1}}
=\sum_{i_1=1}^n{i_1\choose k}={{n+1}\choose{k+1}}$


Per la prima sommatoria vediamo cosa succede.

Il primo passo è

$\displaystyle \sum_{i_k=1}^{i_{k-1}-1}{i_k\choose0}=\sum_{i_k=1}^{i_{k-1}-1}1=(i_{k-1}-1)={i_{k-1}\choose1}-{i_{k-1}\choose0}$

il secondo passo è

$\displaystyle \sum_{i_{k-1}=1}^{i_{k-2}-1}\left[{i_{k-1}\choose1}-{i_{k-1}\choose0}\right]={i_{k-2}\choose2}-(i_{k-2}-1)={i_{k-2}\choose2}-{i_{k-2}\choose1}+{i_{k-2}\choose0}$

e così via fino a che arriviamo a

$\displaystyle S_1=\sum_{i_1=1}^n i_1\left[(-1)^0{i_1\choose{k-1}}+(-1)^1{i_1\choose{k-2}}+\cdots+(-1)^{k-1}{i_1\choose0}\right]=\sum_{i_1=1}^n i_1\sum_{j=0}^{k-1}(-1)^j{i_1\choose{k-1-j}}$

Per calcolare la sommatoria interna ci caviamo di impaccio con un esempio numerico: consideriamo la somma

$\displaystyle\sum_{j=0}^3(-1)^j{n\choose{3-j}}={n\choose3}-{n\choose2}+{n\choose1}-{n\choose0}$

e, utilizzando la solita identità

$\displaystyle{n\choose k}={{n-1}\choose k}+{{n-1}\choose{k-1}}$

scriviamo

$\displaystyle\left[{{n-1}\choose3}+{{n-1}\choose2}\right]- \left[{{n-1}\choose2}+{{n-1}\choose1}\right]+ \left[{{n-1}\choose1}+{{n-1}\choose0}\right]- {{n-1}\choose0}={{n-1}\choose3}$

Dato che utilizziamo solo una proprietà vera per tutti i coefficienti binomiali possiamo dedurrre che

$\displaystyle\sum_{j=0}^{k-1}(-1)^j{i_1\choose{k-1-j}}={{i_1-1}\choose{k-1}}$

e

$\displaystyle S_1=\sum_{i_1=1}^n i_1{{i_1-1}\choose{k-1}}=k\sum_{i_1=1}^n{i_1\choose k}=k{{n+1}\choose{k+1}}$

Concludendo,

$\displaystyle S_k=S_1-S_2=(k-1){{n+1}\choose{k+1}}$


QED :D
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"

Rispondi