In questo articolo vengono proposti alcuni problemi di natura combinatoria relativi alla scacchiera e al gioco degli scacchi, che tuttavia hanno un ambito di applicazione anche in altri settori della matematica.
Numeriamo la scacchiera \(8 \times 8\) con i numeri da 1 a 64. Disporre 8 torri sulla tastiera in modo che nessuna possa attaccare l’altra. Calcolare la somma dei numeri delle caselle occupate dalle torri.
SOLUZIONE
Affinché le torri non possano attaccarsi è necessario che in ogni riga e in ogni colonna ci sia una ed una sola torre. L’elemento presente nella riga i-esima e nella colonna j-esima ha il valore \(c_{ij}= j+ 8(i-1)\). Comunque siano disposte le torri, entrambi i coefficienti \(i,j\) devono apparire 8 volte. Quindi la somma cercata è:
Come generalizzazione dimostrare che nel caso di una scacchiera \(n \times n\) e di \(n\) torri disposte in modo da non attaccarsi fra loro, la somma risulta:
\[
S= \frac {n(n^{2}+1)}{2}
\]
Esercizio 2
Due regine sono poste a caso su una scacchiera vuota. Quale è la probabilità che le due regine non possano attaccarsi?
SOLUZIONE
Il numero minimo di quadrati che ogni regina può attaccare da qualunque posizione è 21, come si può facilmente verificare. Se la regina si trova nella prima o ottava riga, oppure nelle prima o ottava colonna, allora 21 è anche il numero massimo. Tuttavia se si trova nella seconda o settima riga, oppure nella seconda o settima colonna il numero massimo diventa 23. Proseguendo il massimo diventa 25 se si trova nella terza o sesta riga/colonna, e 27 nella quarta o quinta riga/colonna. Ora le caselle presenti nelle 4 regioni distinte sono rispettivamente 28,20,12,4. Supponiamo ora che le due regine abbiano posizioni iniziali casuali su due caselle. Calcoliamo inizialmente la probabilità \(p_{1}\) che possano attaccarsi. Applichiamo il principio delle probabilità composte:
La probabilità che non possano attaccarsi è quindi \(p_{2}=1 -p_{1} \approx 0,63\). Per uno studio del calcolo delle probabilità e in particolare del principio delle probabilità composte vedere ad esempio [1].
Esercizio 3
Calcolare il numero massimo di torri che è possibile mettere sulla scacchiera \(8 \times 8\), senza che possano attaccarsi fra loro.
Si trova facilmente che il massimo numero è \(8\).
Esercizio 4
Data una scacchiera \(n \times n\). Calcolare il numero di configurazioni di \(k\) torri (\(k \le n\)) tali che non ci siano due torri sulla stessa riga o sulla stessa colonna.
SOLUZIONE
Supponiamo inizialmente che le torri siano distinguibili tra loro. In questo caso per la prima torre abbiamo \(n^{2}\) possibilità di scelta. Per la seconda le possibilità sono \((n-1)^{2}\), ecc. Quindi in totale le possibili configurazioni sono
dove \(D_{n,k}\) indica il numero delle disposizioni di n oggetti presi a gruppi di k. Poiché le torri non sono distinte, per risolvere il problema dobbiamo dividere per \(k!\). Ricordiamo la seguente relazione fra le disposizioni e le combinazioni, espresse dal coefficiente binomiale:
Il termine polinomio della torre è stato introdotto da J. Riordan[2]. Il polinomio della torre viene utilizzato per risolvere problemi di natura combinatoriale in diversi settori della matematica, al di fuori dell’argomento degli scacchi. Si conviene di porre \(R_{0}(x)= 1\). È facile inoltre dimostrare che \(R_{1}(x)= 1+x\). Il significato è che su una scacchiera \(1 \times 1\) una torre può essere disposta in un solo modo, mentre zero torri possono essere disposte in un modo (nella scacchiera vuota). Per calcolare gli altri polinomi di grado maggiore è utile il seguente teorema, che si può dimostrare utilizzando proprietà note dei coefficienti binomiali.
Teorema Dimostrare la seguente formula di ricorsione:
Ad esempio il significato dell’espressione \(R_{2}(x)\) è che su una scacchiera \(2 \times 2\) due torri possono essere disposte in due modi, una torre può essere disposta in quattro modi, mentre zero torri possono essere disposte in un modo (nella scacchiera vuota). Si può verificare facilmente che i primi polinomi della torre hanno radici reali, distinte, tutte negative. Questa è una proprietà generale valevole per ogni grado \(n\) del polinomio, che si può dimostrare per induzione utilizzando la formula di ricorsione sopra riportata e il teorema di Rolle dell’analisi matematica.
Appendice: Cenni sui polinomi di Laguerre
I polinomi della torre sono strettamente collegati ai polinomi di Laguerre, che hanno importanti applicazioni in vari settori della matematica e delle fisica. Riportiamo alcune definizioni e proprietà. Per uno studio approfondito vedere [3].
I polinomi di Laguerre possono essere definiti dalla seguente sommatoria:
La matematica consiste in due principali categorie di attività: dimostrazione di teoremi e soluzione di problemi. In entrambe queste attività i matematici giustificano le loro conclusioni tramite il ragionamento deduttivo, basato sulle leggi della logica. Leggi tutto…
In questo articolo proponiamo alcuni esercizi di matematica elementare. Per eventuali chiarimenti si può utilizzare la email del blog oppure la sezione commenti. Esercizio 1 Sia dato un poligono regolare di \(n\) lati, ognuno di Leggi tutto…
In questo breve articolo presenteremo alcuni problemi relativi alla determinazione dei punti a coordinate intere contenuti all’interno o sulla frontiera di alcune figure piane. Questo tipo di problema presenta aspetti molto interessanti e trova importanti Leggi tutto…
0 commenti