MASSIMO NICODEMO

MATEMATICA

sulla

SCACCHIERA

1

2

PREFAZIONE

La matematica ricreativa può costituire un piacevole passatempo per l'appassionato, ma anche un'occasione per avvicinarsi alla matematica con lo spirito del gioco.Questa raccolta di problemi, alcuni dei quali hanno destato l'interesse di matematici illustri, come Gauss ed Eulero,vuole essere, quindi, un divertissement per chi ama la matematica e un invito a scoprirne il fascino per chi, vittima di pregiudizi del tutto infondati, non ha mai sospettato che essa richiede intuito e fantasia, e può essere fonte di un intenso piacere intellettuale.Buon divertimento!

L'Autore

3

Ringrazio mio figlio Nicola per la preziosa collaborazione.

4

I

LA SCACCHIERA

5

6

CoordinateFissiamo un riferimento su una scacchiera n x n indicando le colonne e le traverse con i numeri da 0 a (n-1) in modo che ogni casa sia individuata da una coppia ordinata (i,j), nella quale i indica la colonna e j la traversa di appartenenza. In figura è rappresentata una scacchiera standard ( n = 8 ):

7 6 5 4 3 2 1 0 0 1 2 3 4 5 6 7

Osserviamo che:

1)Le case (i,j) e (h,k) appartengono ad una stessa diagonale se: a) i-j = h-k ( diagonale ascendente) b) i+j =h+k ( diagonale discendente)2) Il colore della casa (i,j) è:

nero se i+j è pari bianco se i+j è dispari.

3) Le case (i,j) e (h,k) sono in opposizione se |i-h| e |j-k| sono entrambi pari.

4)La scacchiera esemplifica una delle tre possibili “pavimentazioni regolari” del piano (pavimentazioni eseguite usando poligoni regolari di un sol tipo). In questo caso, infatti, se si vogliono adoperare “mattonelle”d'una sola forma, bisogna che l'angolo interno del poligono sia contenuto esattamente un certo numero di volte nell'angolo giro, affinché sia possibile coprire il piano accostando più mattonelle. Soddisfano a questa condizione solo tre poligoni regolari: il triangolo equilatero, il quadrato e l'esagono regolare.

7

Distanze

Definiamo distanza fra le case A = (i,j) e B = (h,k), il numero:

d(A,B) = max ( |i-h|, |j-k| ) ( distanza di Tchebichev)

Si può dimostrare che tale definizione rispetta le proprietà che caratterizzano una distanza, ovvero:

I) d(A, B) = 0 ↔ A = BII) d(A, B) = d(B, A) (simmetria)

III) d(A, B) ≤ d(A, C)+d(C, B) (disuguaglianza triangolare) IV) d(A, B) ≥ 0

Questa definizione di distanza si usa per il movimento del Re e della Donna.Per la Torre si usa la distanza del taxi ( o di Manhattan),così definita: d(A,B) = | i-h | + | j-k|.Tale distanza si usa anche per l'Alfiere sulla scacchiera ruotata di 45 gradi,ovvero assumendo come assi le diagonali uscenti dalla casa dell'Alfiere.

E' da notare che per spostarsi da una casa all'altra, il Re ha bisogno di un numero di mosse uguale alla distanza; Torre, Donna e Alfiere hanno bisogno solo di una o due mosse. Le due definizioni di distanza che abbiamo considerato sono casi particolari della distanza di Minkowski:

d(A,B) = ( | i-h |m + | j-k |m )1/m

particolarizzando i valori di m si ottiene:

m = 1 distanza di Manhattahm→ ∞ distanza di Tchebichev

8

La distanza euclidea, che ci è più familiare, si ottiene per m = 2.Per chiarire la differenza tra le due definizioni di distanza, consideriamo la seguente scacchiera nella quale sono indicate le case A(2,1) e B(5,6):

B

A

la distanza di Tchebichev fra le due case è : d(A,B) = max ( |5-2|, |6-1| ) = 5 passi di Re ( in verde nella figura )il che vuol dire che un Re ( o una Donna) deve “attraversare” 5 case (minimo) per spostarsi da A a B.La distanza di Manhattan fra le due case è :

d(A,B) = |5-2| + |6-1| = 8 passi di Re (in rosso nella figura)il che vuol dire che una Torre deve “attraversare” 8 case (minimo) per spostarsi da A a B. Nel conteggio delle case è esclusa quella di partenza ed è inclusa quella di arrivo.Nel gioco degli scacchi, la distanza fra due case svolge un ruolo fondamentale soprattutto nei finali che coinvolgono Re e pedoni, per tale motivo, quando si parla di distanze sulla scacchiera ci si riferisce tacitamente alla distanza di Tchebichev.

9

OrdineL'ordinamento lessicografico rappresenta la soluzione più naturale per introdurre una relazione d'ordine sulla scacchiera:in un dizionario, la parola P1 precede la parola P2 (scriveremo P1 < P2) se la lettera iniziale di P1 precede (nell'alfabeto) la lettera iniziale di P2. Se le lettere iniziali sono uguali, il confronto si sposta sulla seconda lettera, e così via. Allo stesso modo, date le case (i, j) e (h, k) diremo che (i, j) < (h, k) se:

1) i < h oppure2) i = h e j < k

Esempio 1: (3, 4) < (5, 2) perché 3 < 5 nell'alfabeto (0, 1,2,3,4,5,6,7) (3, 4) < (3, 6) perché 4 < 6

Esempio 2: se indichiamo le case nella consueta notazione scacchistica, l'esempio precedente diventa d5 < f3 perché d < f nell'alfabeto (a, b, c, d, e, f, g, h) d5 < d7 perché 5 < 7 nell'alfabeto (1, 2, 3, 4, 5, 6, 7, 8).

L'ordine lessicografico può risultare utile, ad esempio, per classificare le varianti d'apertura nel gioco degli scacchi: l'ordine di due varianti coincide con l'ordine delle case di arrivo dei pezzi nella prima mossa per cui esse differiscono. A parità di casa di arrivo, vale la casa di partenza.

Esempio: consideriamo le varianti A: 1) e4, e5; 2) Cf3, Cc6; 3)Ac4

B: 1) e4, e5; 2) Cf3, Cc6; 3)Ab5

diciamo che B < A perché b5 < c4. Questo tipo di classificazione ha il difetto di assegnare un ordine diverso a varianti che, per trasposizione di mosse, conducono alla stessa posizione.

10

Scacchiera + Pezzo = Grafo !Data una scacchiera e un pezzo, diciamo che due case sono adiacenti (unite da un arco) se il pezzo può spostarsi da una casa all'altra con una mossa. La scacchiera e il pezzo, quindi, definiscono un grafo i cui nodi sono le case della scacchiera e i cui archi sono le mosse del pezzo. Consideriamo, come esempio, la seguente scacchiera 3 x 3:

1 2 34 5 67 8 9

e costruiamo alcuni semplici grafi: -Grafo dell'Alfiere camposcuro:

-Grafo dell' Alfiere campochiaro:

11

-Grafo del Cavallo

-Grafo del Re

In analogia con la teoria dei grafi, diamo la seguente definizione:

Dicesi grado di una casa, relativamente a un dato pezzo P, il numero di case che il pezzo può raggiungere, con una mossa, quando è situato su quella casa.

Diciamo che una casa è dominata da un pezzo, se risulta occupata o controllata dal pezzo.

12

Dopo questo breve tour intorno alla scacchiera, consideriamo alcuni problemi che la vedono protagonista.

Problema n. 1 ( la leggenda di Sissa )

Il problema più conosciuto è quello legato alla leggenda di Sissa:secondo la leggenda, Sissa Nassir, l’inventore degli scacchi, chiese, come ricompensa, al re di Persia un chicco di grano per la prima casella della scacchiera, due chicchi per la seconda, quattro chicchi per la terza e così via raddoppiando fino alla 64-ma,come mostra la seguente figura:

1=20 21 22 23 24 25 26 27

28 29 210 ... ... ... ... ...... ... ... ... ... ... ... ...... ... ... ... ... ... ... ...... ... ... ... ... ... ... ...... ... ... ... ... ... ... ...... ... ... ... ... ... ... ...256 257 258 259 260 261 262 263

La domanda è: quanti chicchi di grano spettano a Sissa?

Soluzione

Sia N il numero da determinare:

N = 1+2+4+8+...+263

13

N è la somma dei primi 64 termini di una progressione geometrica di primo termine a1 = 1 e ragione q = 2, per cui, applicando una notissima formula, si ottiene : N = 264 – 1 ≈ 1.8446744∙1019

Se 20 chicchi di grano pesassero un grammo, Sissa avrebbe diritto a circa 1000 miliardi di tonnellate di grano!!

Appendice (capziosa) al problema n.1

Se la scacchiera fosse stata infinita (costituita da infinite colonne e infinite traverse), quanti chicchi di grano avrebbe dovuto ricevere Sissa?Sia N il numero cercato:

N = 1+2+4+8+16+32+...N = 1+2(1+2+4+8+16+...)N = 1+2NN = -1

ovvero: Sissa avrebbe dovuto dare un chicco di grano al re di Persia!E' evidente che in questo calcolo qualcosa “non quadra”. Dov'è l'errore?

Problema n.2

Quanti quadrati si possono individuare su una scacchiera?

Soluzione I quadrati di lato unitario sono 64,

per i quadrati di lato 2 possiamo ragionare così:consideriamo il quadrato costituito dalle caselle 0,0 ,0,1 , 1,1 , 1,0 e trasliamolo verso destra di una colonna alla volta, è evidente che otteniamo (contando il quadrato iniziale) 7 quadrati. Se per ognuno dei 7 quadrati ripetiamo la traslazione in senso verticale,ognuno genererà 7 quadrati, per cui i quadrati di lato 2 sono 49. Ragionando in modo analogo si conclude che i quadrati di lato 3 sono 36, quelli di lato 4 sono 25… e così via.E’ abbastanza agevole arrivare ad una formula chiusa :

14

i quadrati di lato k sono (9-k)2 1 ≤ k ≤ 8 Il numero totale dei quadrati sarà:

∑ 9−k 2 1k8

poiché 1 ≤ k ≤ 8 anche 1 ≤ 9-k ≤ 8per cui il numero totale dei quadrati è

∑ k 2 1k8

ovvero la somma dei quadrati dei numeri da 1 a 8, che vale 204.

Il problema si può generalizzare al caso di una scacchiera n x n :

numero dei quadrati di lato k : (n+1-k)2 1 ≤ k ≤ n

numero totale dei quadrati :

∑ k 2 = nn12n16 1kn

Se la scacchiera fosse rettangolare m x n (m ≤ n), si avrebbe, ragionando in modo analogo a quanto fatto per il caso precedente, che il numero dei quadrati di lato k è dato da: (n-k+1)(m-k+1) e il numero totale dei quadrati è dato, ponendo n = m+t, da:

1km ∑ k−m−1k−m−1−t = m m12m3t16

Problema n. 3

Quanti rettangoli si possono individuare su una scacchiera?

Soluzione

Per risolvere questo problema conviene vedere la scacchiera come una griglia formata dall’intersezione di 9 rette verticali e 9 orizzontali

15

( le rette che delimitano i bordi e quelle che fanno da separazione tra le colonne e le traverse della scacchiera).

Ora possiamo ragionare così:

per individuare un rettangolo basta fissare due rette verticali e due rette orizzontali. Le due rette verticali possono essere scelte in 9

2 modi e così anche le due rette orizzontali, per cui il numero dei rettangoli è 9

2 . 92 = 1296

tra questi rettangoli ci sono anche i quadrati, per cui i rettangoli non quadrati sono 1296 – 204 = 1092.Il problema si generalizza facilmente per una scacchiera n x n:

numero rettangoli:

n12 . n1

2 = [n2n12]4

Numero dei rettangoli non quadrati:

[n2n12]4

−nn12n1

6=

n 3n2n2−112

Se la scacchiera fosse una m x n, si avrebbe, con ragionamento analogo a quello seguito per il caso precedente:

numero rettangoli = m12 ⋅n1

2

Problema n.4 (La scacchiera mutilata)Sia data una scacchiera “mutilata”, dalla quale, cioè, sono state eliminate 2 case, e si disponga di 31 tessere del domino (ciascuna delle quali atta a ricoprire esattamente due case adiacenti della scacchiera), ci chiediamo: è possibile “pavimentare” la scacchiera disponendo le tessere orizzontalmente (sulle traverse) oppure verticalmente (sulle colonne) in modo che ogni tessera copra (senza sovrapposizioni) 2 case?

16

Soluzione (teorema di Gomory)Bisogna distinguere fra due ipotesi:

1) Le case eliminate sono dello stesso colore.2) Le case eliminate sono di colore diverso.

Nel primo caso il problema non ha soluzione. Infatti, ogni tessera copre una casa bianca ed una nera e, quindi, le 31 tessere devono coprire 31 case bianche e 31 nere... ma sulla scacchiera ci sono 30 case di un colore e 32 di un altro!Nel secondo caso il problema ammette soluzione. Infatti, supponiamo che vengano eliminate la casa nera (i,j) e la casa bianca (x,y). Ci sono due possibilità:

I) i e x hanno la stessa paritàII) i e x hanno parità diversa.

Dimostriamo che la soluzione esiste ipotizzando, senza perdere in generalità, che i e x abbiano la stessa parità.Se i e x hanno la stessa parità, allora j e y hanno parità diversa (non dimentichiamo che i+j è pari e x+y è dispari). Le due case eliminate individuano sulla scacchiera un rettangolo di cui esse sono due case d'angolo opposte. Le altre due case d'angolo sono (i,y) e (x,j), come mostrato nella seguente figura:

i,y x,y

i,j x,j

Le misure dei lati di tale rettangolo ( espresse in caselle ) sono:Base: b = | x-i | + 1 (dispari)Altezza: h = | y-j| + 1 ( pari)

17

Osserviamo che la scacchiera privata delle case (i,j)e (x,y) si può scomporre in rettangoli aventi ognuno un lato costituito da un numero pari di case, come mostrato nella seguente figura:

Per maggior chiarezza, consideriamo la seguente tabella, che spiega la figura precedente (in verde, sono le case mancanti):

Colore rettangoli Misura base (b) Misura altezza (h) Parità 8 pari | y-j | +1 pari

| y-j | - 1 pari | x-i | pari

A questo punto risulta evidente che la scacchiera è ricopribile, perché un rettangolo avente un lato costituito da un numero pari di case è banalmente ricopribile.Se i e x hanno parità diversa il ragionamento non cambia: basta scambiare le traverse con le colonne.

18

Problema n. 5 ( il tappeto di Sierpinski)Una scacchiera di lato unitario viene divisa in nove scacchiere uguali e quella centrale viene eliminata. Le rimanenti otto scacchiere vengono similmente divise e viene eliminata la centrale. Se le ripetizioni di questo procedimento continuano indefinitamente si ha una figura (che qui,ovviamente, è solo accennata) nota come tappeto di Sierpinski, che è uno dei più famosi oggetti frattali. La domanda che ci poniamo è:qual è il limite dell'area colorata?

19

SoluzioneIl problema si risolve facilmente osservando che le aree dei quadrati eliminati ad ogni iterazione , a cominciare da quello centrale e considerando via via i più piccoli,danno luogo alla progressione geometrica

19

, 892 , 82

93 , 83

94 , ...

in cui è a1= 19 e q= 8

9 . Indicando con En , l'area dei quadrati eliminati

dopo n iterazioni, si ha En = 1−89

n

. Risulta, evidentemente, En →1 per n→∞.Se Sn è l'area restante (area colorata) dopo n iterazioni, si ha: Sn =

89

n

e, quindi, Sn →0 per n→∞.

20

Problema n. 6 (minimo attacco)

Disporre gli 8 pezzi di un colore (R, D, 2TT, 2AA, 2CC) in modo che risulti sotto attacco il minimo numero possibile di case ( un pezzo non attacca la casa su cui è situato, ma può attaccare la casa su cui è situato un altro pezzo).Soluzione Per questo problema ( ed altri simili ) non esiste una dimostrazione rigorosa. Una soluzione è la seguente:

A D T CA T R

C

le case attaccate sono 16.

21

Problema n. 7 (massimo attacco)

Disporre sulla scacchiera gli 8 pezzi di un colore in modo che risulti sotto attacco il massimo numero possibile di case ( valgono le osservazioni fatte per il problema 6).

Soluzione Una possibile soluzione è la seguente:

T

T

RA A

C CD

Le case attaccate sono 63.Il numero di case attaccate può essere portato a 64 (il massimo possibile) se è consentito usare due Alfieri camposcuro (o campochiaro):

T

A R C

C D A

T

22

Problema n. 8 (colorazioni della scacchiera)Siano dati due colori, bianco e nero, e una scacchiera n x n, in quanti modi si possono colorare le n2 case della scacchiera con i due colori?

Soluzione Diamo la soluzione per una scacchiera 2 x 2 (in modo analogo si procede nel caso generale). E' evidente che il numero di colorazioni in cui figurano h case nere è dato da 4

h 0≤ h≤4. Indichiamo i colori con x (nero) e y (bianco), e consideriamo il polinomio (x + y)4 = x4 + 4x3y + 6x2y2 + 4xy3 + y4.Questo polinomio enumera le colorazioni con h case nere e 4-h bianche. Così, ad esempio, il coefficiente del monomio 6x2y2 ci dice che vi sono 6 colorazioni con 2 case nere e 2 bianche:

allo stesso modo si interpretano i coefficienti degli altri monomi.La colorazione standard della scacchiera è realizzata in modo che le case nere e bianche si alternino sia lungo le colonne che le traverse, per cui, comunque scelte due colonne i e j , si avrà che le case ai,k e aj,k sono sempre dello stesso colore o sempre di colore diverso. Se diciamo che si ha una permanenza tutte le volte che colore(ai,k) = colore(aj,k) e una variazione quando colore(ai,k) ≠ colore(aj,k), la proprietà precedente può

23

essere enunciata dicendo che comunque scelte due colonne i, j, le coppie di case ai,k, aj,k danno luogo sempre a una permanenza o sempre a una variazione. Ovviamente, il discorso resta valido se sostituiamo “colonna” con “traversa” e ai,k, aj,k con ak,i, ak,j.Una colorazione alternativa è quella caratterizzata dalla seguente proprietà:comunque scelte due colonne (traverse) i,j , le coppie di case ai,k, aj,k

(ak,i, ak,j) danno luogo a un numero di permanenze uguale al numero di variazioni.Le seguenti figure esemplificano tale colorazione (detta anallagmatica) per una scacchiera 4 x 4 e una 8 x 8:

Questo tipo di colorazione diventa estremamente interessante se si sostituiscono i colori bianco e nero con i numeri +1 e -1 (bianco = 1, e nero = -1, o viceversa), perché con tale sostituzione la scacchiera si trasforma in una matrice che gode di particolari proprietà.Se si considerano scacchiere di ordine n = 1; 2 oppure 4k si ottengono delle matrici ( che indicheremo con H n) che sono state studiate dal matematico francese Jacques Hadamard (1865-1963). Elenchiamo alcune proprietà di tali matrici:

– | detHn | = nn/2 ( la matrice è invertibile)– Due colonne (righe) qualsiasi sono vettori ortogonali.– HnHn

T = nIn, dove HT è la trasposta di Hn e In è la matrice identità di ordine n.Verifichiamo queste proprietà sulla matrice 4 x 4 della figura precedente:

24

1 1 1 11 -1 1 -11 1 -1 -11 -1 -1 1

-| det H 4 | = 16-E' facile verificare che il prodotto scalare fra due colonne (righe) qualsiasi è nullo- H4HT

4 = 4I4

4 0 0 00 4 0 00 0 4 00 0 0 4

Una matrice di Hadamard può essere trasformata in un'altra equivalente mediante le seguenti operazioni:– scambiare due righe o due colonne.– moltiplicare una riga o una colonna per -1– considerare la matrice trasposta.

25

Quante caselle ci sono su una scacchiera? Spesso si parla degli scacchi come del “mondo delle 64 caselle” ma ...sono davvero 64 ?Consideriamo una scacchiera 8 x 8, divisa in quattro parti.

Se ricomponiamo le quattro parti nel modo indicato dalla seguente figura

otteniamo un rettangolo di 65 case, che dovrebbe essere equivalente alla scacchiera originaria, perché equicomposto!!Dobbiamo concludere che 64 = 65? L'”enigma” si scioglie come neve al sole se osserviamo che il triangolo avente per cateti 5 e 13 contiene il triangolo più piccolo, anch'esso rettangolo, avente per cateti 3 e 8 . Allora la tangente dell'angolo opposto ai lati 5 e 3 sarebbe 5/13 se misurata nel triangolo grande e 3/8 se misurata nel triangolo piccolo. Questo ci fa capire che l'ipotenusa del triangolo grande ( diagonale del rettangolo) e quella del triangolo piccolo non giacciono sulla stessa retta, ovvero quella che figura come diagonale del

26

rettangolo non è un segmento di retta se non nell'illusione del disegno. I quattro punti che essa apparentemente congiunge, ossia i vertici dei due trapezi, internamente, e i vertici opposti del rettangolo, non sono allineati. Essi formano, congiunti esattamente, un sottile quadrilatero, la cui superficie è equivalente a quella di un quadratino, ossia del quadratino che il rettangolo ha in più rispetto al quadrato iniziale e che il grosso tratto della diagonale ha fatto abilmente scomparire.

Il paradosso può essere riprodotto partendo da un quadrato n x n , dove n è un numero appartenente alla successione di Fibonacci:

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, .......

in cui ogni termine ( a partire dal terzo ) si ottiene come somma dei due che lo precedono. I “ numeri di Fibonacci “ sono particolarmente adatti a generare un paradosso come quello appena discusso, perché godono, fra le altre, della seguente proprietà, nota come identità di Cassini:

Se a, b, c, sono tre numeri consecutivi della successione, allora:

a⋅c=b2±1

dove vale il segno “+” se b occupa un posto pari nella successione, e il segno “-” se occupa un posto dispari. Se n è la misura del lato che si sceglie per il quadrato, la divisione di esso in due parti è data dai due numeri che lo precedono, come per esempio nel caso considerato di n = 8 la divisione del lato è stata fatta secondo 3 quadratini e 5 quadratini. Se si volesse disegnare una scacchiera 21 x 21 , la scomposizione del lato avverrebbe secondo 8 e 13 quadratini.Quanto più grande è n tanto più efficace è l' illusione della diagonale che nasconde, col suo spessore, la superficie equivalente al quadratino.

27

28

II

I PEZZI

29

30

Mosse - spostamenti

Lo spostamento che un pezzo subisce quando effettua una mossa verrà indicato con il vettore (x,y), dove x rappresenta la componente nella direzione delle traverse (“orizzontale”) e y la componente nella direzione delle colonne (“verticale”).In particolare:x>0 indica uno spostamento verso estx<0 indica uno spostamento verso ovesty>0 indica uno spostamento verso nordy<0 indica uno spostamento verso sudNel valutare gli spostamenti supporremo che il pezzo sia collocato nel centro della casa ( ovvero una casa sarà identificata con il suo punto centrale).Esempio:se un alfiere muove dalla casa (1,2) alla casa (3,0) il suo spostamento sarà indicato dal vettore (2,-2).Per quanto riguarda la mossa di cavallo, a volte conviene esprimere lo spostamento ad essa associato mediante le componenti nelle direzioni delle diagonali che passano per la casa di partenza. In tal modo si osserva che ad ogni mossa di cavallo corrisponde uno spostamento di

12 passo diagonale in una direzione e di 3

2 di passo diagonale nell'altra, come si evidenzia nella seguente figura:

Nord

Sud

31

Mobilità di un pezzoCome mobilità di un pezzo consideriamo il grado medio dei vertici del suo grafo.Consideriamo la variabile G = {grado di un vertice}che assumerà i valori g1, g2, ...gh con frequenza (relativa) p1, p2, ...ph.

Il valore medio di G rappresenta la mobilità del pezzo:

E(G) = ∑i=1

h

g i pi A volte il valore della mobilità viene usato per calcolare un indice che dovrebbe esprimere la “forza” del pezzo (Re escluso), rapportando la sua mobilità a quella del pedone (= 1.75), che viene assunta come unità di misura. Indicando tale indice con F, si ha:

F= mobilità del pezzomobilità del pedone

32

Descrivere una posizione

La notazione FEN (Forsyth-Edwards Notation), usata dai programmatori, fornisce tutte le informazioni necessarie a consentire la continuazione di una partita iniziando da una posizione data.Una stringa FEN é costituita da una sola linea di testo e si compone di 6 campi:

1) Posizione dei pezzi.I pezzi vengono indicati con le iniziali dei loro nomi inglesi, in maiuscolo i pezzi Bianchi (KQRBNP), in minuscolo i pezzi Neri (kqrbnp). Viene indicato il contenuto di ogni casa a partire dall'ultima traversa (traversa 7) fino alla prima (traversa 0), procedendo, per ogni traversa, dalla colonna 0 alla colonna 7. Le case vuote vengono indicate mediante le cifre dall'1 all'8(a seconda delle case vuote adiacenti). Per separare una traversa dall'altra si usa il simbolo “ / ”. 2) Giocatore che ha la mossa.

La lettera w (white) indica che la mossa spetta al Bianco, la lettera b (black) indica che la mossa spetta al Nero.

3) Diritto all'arrocco.Se entrambi i giocatori hanno perso il diritto all'arrocco, si usa il simbolo “_”, altrimenti si indica:K→ il Bianco può arroccare cortoQ→ il Bianco può arroccare lungok→ il Nero può arroccare cortoq→ il Nero può arroccare lungo 4) Casa in cui è possibile prendere en passant.Se non è possibile nessuna presa en passant, si usa il simbolo “-”, altrimenti si indica la casa alle spalle dell'ultimo pedone che ha effettuato la mossa di due case. 5) Numero di semimosse. Numero di semimosse dall'ultima mossa di pedone o dall'ultima cattura. Questo numero serve per la regola delle 50 mosse. 6) Numero delle mosse. Questo numero vale 1 per la prima mossa del Bianco e del Nero. Viene aumentato di 1 dopo ogni mossa del Nero.

33

Esempio: la posizione iniziale è così rappresentata in notazione FEN:

rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNRwKQkq-01

dopo 1) e4:

rnbqkbnr/pppppppp/8/8/4P3/8/PPPP1PPP/RNBQKBNRbKQkqe301

dopo 1)....c5:

rnbqkbnr/pp1ppppp/8/2p5/4P3/8/PPPP1PPP/RNBQKBNRwKQkqc602

e dopo 2) Cf3:

rnbqkbnr/pp1ppppp/8/2p5/4P3/5N2/PPPP1PPP/RNBQKB1RbKQkq-12

34

IL RE

Il Re si muove in tutte le direzioni spostandosi una casa per volta:

( i,j ) → ( i+x , j+y ) -1 ≤ x, y ≤ 1 , (x , y ) ≠ ( 0 , 0 )

Definiamo: passo orizzontale uno spostamento del tipo (±1, 0) passo verticale uno spostamento del tipo (0, ±1) passo diagonale uno spostamento del tipo (±1, ±1)

Mobilità del ReCon riferimento al Re, la scacchiera è costituita da: 4 case di grado 3 ( le case d'angolo ) 24 case di grado 5 ( le case sul bordo) 36 case di grado 8 ( le altre case) per cui possiamo costruire la variabile G:

G P 3 4/64 5 24/64 8 36/64

E(G) = 6.6

Il modo in cui è definito il movimento del Re ci induce a ripensare alla definizione di distanza data in precedenza. L’aver definito la distanza tra due case come max ( | i-h|,|j-k|) equivale ad aver scelto come unità di misura il “passo di Re” e ciò comporta delle conseguenze notevoli, nel senso che sulla scacchiera non sono più valide alcune delle fondamentali relazioni che sussistono nel piano euclideo. Per esempio, sulla scacchiera:

1) esistono triangoli rettangoli “equilateri”2) il percorso minimo tra due case non è, generalmente, unico!!

Con riferimento al primo punto, consideriamo la seguente figura:

35

C

A B

Notiamo che d(A,B) = d(B,C) = d(A,C) = 7 passi di Re.Ovvero, il triangolo rettangolo (ABC) è “equilatero”!Per quanto riguarda il secondo punto, osserviamo le seguenti figure:

Figura 1

Figura 2

36

Sulla scacchiera di Fig.1 sono segnate due case dello stesso colore, una di partenza A = (5,0) e l'altra di arrivo B = (4,5).Si ha d(A,B) = max ( |5-4|, | 0-5| ) = 5 passi di Re.E' facile verificare che un re può spostarsi da A a B seguendo diversi percorsi tutti di lunghezza minima ( 5 passi ) e che tali percorsi sono tutti “ non esterni “ al rettangolo ACBD, dove C e D sono le case in cui si intersecano le diagonali uscenti da A e da B.Nella Fig.2 le case A e B (partenza e arrivo) non sono dello stesso colore e la costruzione del rettangolo è leggermente diversa perché le diagonali uscenti da A e da B non si incontrano nel centro di una casa ma in un vertice, restano comunque valide le considerazioni fatte per il caso rappresentato in Fig.1. Se la casa di partenza e quella di arrivo sono sulla stessa diagonale, il percorso minimo è, ovviamente, unico.

37

Problema n. 9 ( passeggiata del Re - I )

Quanti sono i percorsi che può seguire il Re per spostarsi dalla casa (0,0) alla casa (m,k), se sono consentiti solo spostamenti del tipo (1,0), che indichiamo con “o”, e (0,1), che indichiamo con “v” ?

Soluzione

Anzitutto notiamo che la posizione iniziale del re in (0,0) non toglie generalità alla soluzione, perché ci si può sempre ricondurre a questo caso mediante traslazione e/o rotazione degli assi ( questa considerazione varrà per tutti i problemi seguenti ).Ragioniamo così: per andare da (0,0) a (m.k) il re dovrà fare m spostamenti “o” e k spostamenti “v”, ovvero un totale di m+k spostamenti di cui m uguali fra loro e k uguali fra loro.Il numero dei percorsi, che indichiamo con T(m, k), sarà dato dal numero di permutazioni di m+k elementi, di cui m uguali fra loro e k uguali fra loro, ovvero: T(m, k) = mk

m , k = mk !m! k ! .

Assegnando dei valori a m e a k, otteniamo i risultati riportati nella seguente scacchiera:

7 16 1 75 1 6 214 1 5 15 353 1 4 10 20 352 1 3 6 10 15 211 1 2 3 4 5 6 70 1 1 1 1 1 1 1 1

0 1 2 3 4 5 6 7

I valori segnati in ciascuna casa indicano il numero di percorsi possibili per raggiungerla. Osservando i numeri lungo le diagonali discendenti, non è difficile riconoscere le prime otto righe del celeberrimo triangolo di

38

Tartaglia ( o di Pascal). Per maggiore chiarezza, consideriamo esplicitamente i percorsi per raggiungere la casa (2, 2):

1) oovv2) ovov3) ovvo4) vvoo5) vovo6) voov

Il valore di T(m, k) può essere calcolato anche con un semplice algoritmo ricorsivo: basta osservare che per raggiungere la casa (m, k), bisogna trovarsi, al penultimo passo, nella casa (m, k-1) oppure nella casa (m-1, k).La seguente figura chiarisce il concetto:

k →k-1 ↑

m-1 m

è evidente che T(m, k) = T(m, k-1)+ T(m-1, k)

questa relazione, unita alle condizioni iniziali:– T(0, 0) = 1– T(m, 0) = T(0, k) = 1ci permette di calcolare il numero di percorsi per raggiungere una generica casa.Esempio: T(4, 3) = T(4, 2) + T(3, 3)

T(4, 3) = 15 + 20 = 35.

Problema n. 10 ( passeggiata del Re – II )Quanti sono i percorsi che può seguire il Re per spostarsi dalla casa (0,0) alla casa (m,k), se sono consentiti solo spostamenti del tipo (1,0),che indichiamo con “o”, del tipo (0,1), che indichiamo con “v” e del tipo (1,1), che indichiamo con “d” ?

39

SoluzioneSupponiamo, senza togliere generalità al discorso, che sia k ≤ m e notiamo che la presenza di uno spostamento del tipo “d” determina la diminuzione di una unità del numero di spostamenti del tipo “o” e del tipo “v”, per cui, se sono presenti j ≤ k spostamenti del tipo “d”, gli spostamenti di tipo “o” diventano m - j, e quelli di tipo “v” diventano k - jIl numero totale di passi sarà N = (m – j)+(k – j)+j = m+k-jdi cuim-j passi tipo “o” k-j passi tipo “v” j passi tipo “d” .Il problema si risolve considerando le permutazioni di N elementi, di cui m-j uguali fra loro, k-j uguali fra loro e j uguali fra loro, con j variabile da 0 a k. Indicando con Pj il valore corrispondente ad un assegnato j, si ha:

Pj = Nm− j , k− j , j =

N !m− j ! k− j ! j !

Il numero totale dei percorsi, che indichiamo con L(m, k), sarà:

L(m, k) = ∑0

k

Pj ( numeri di Delannoy )

nella figura seguente è riportato il numero dei percorsi possibili calcolato per tutte le case di una scacchiera standard:

7 1 15 113 575 2241 7183 19825 48639

6 1 13 85 377 1289 3653 8989 19825

5 1 11 61 231 681 1683 3653 7183

4 1 9 41 129 321 681 1289 2241

3 1 7 25 63 129 231 377 575

2 1 5 13 25 41 61 85 113

1 1 3 5 7 9 11 13 15

0 1 1 1 1 1 1 1 1

0 1 2 3 4 5 6 7

40

Anche qui riportiamo esplicitamente, per maggiore chiarezza, i percorsi che conducono alla casa (2,2):

1) vvoo 2) vovo 3) ovov 4) oovv 5) ovvo 6) voov7) odv 8) ovd 9) dov 10) vod 11) dvo 12) vdo13)dd.

Come per il caso precedente, anche i valori di L(m, k) possono essere calcolati con un algoritmo ricorsivo osservando che per raggiungere la casa (m, k) bisogna essere, al passo precedente, nella casa (m, k-1) o nella casa (m-1, k) o nella casa (m-1, k-1), come si evidenzia nella seguente figura:

k →k-1 ↑

m-1 m

È evidente che L(m, k) = L(m, k-1)+ L(m-1, k) + L(m-1, k-1)

Questa relazione, unita alle condizioni iniziali:– L(0, 0) = 1– L(m, 0) = L(0, k) = 1

ci permette di calcolare il numero di percorsi per raggiungere una generica casa.Esempio: L(4, 3) = L4, 2) + L(3, 3) + L(3, 2)

L(4, 3) = 41 +63 +25 = 129.

41

Problema n.11 (passeggiata del Re -III)

Quanti sono i percorsi che può seguire il Re per spostarsi dalla sua casa d'origine (4,0) alla casa (4,m), se i movimenti consentiti sono (0,1), (1,1) e (-1,1)?

Soluzione

Il re deve compiere m movimenti, e quelli del tipo (1,1) dovranno essere tanti quanti quelli del tipo (-1,1), perché il Re deve ritornare sulla sua colonna. Il re, quindi, dovrà fare k mosse (1,1), k mosse (-1,1) e m-2k mosse (0,1). Il numero dei percorsi sarà, quindi, dato dal numero di permutazioni di m elementi di cui k uguali fra loro, altri k uguali fra loro e m-2k uguali fra loro, con k variabile da 0 a floor m

2 . Detto P il

numero cercato, sarà:

P=∑ m !k ! 2m−2k ! 0k floor m

2

Assegnando a m i valori da 0 a 7, otteniamo i risultati evidenziati nella seguente figura:

7 3936 1415 514 193 72 31 10 1

0 1 2 3 4 5 6 7

42

Problema n.12

Qual è il numero massimo di Re che è possibile disporre su una scacchiera n x n, in modo che nessuno ne attacchi un altro ?

Soluzione Il problema si risolve osservando che un quadrato 2 x 2 può contenere un solo re. Bisogna considerare due casi:

1) n pariLa scacchiera si può suddividere in n

2 2

quadrati 2 x 2, in ciascuno dei quali va collocato un re. Il numero dei re , quindi, è: 1

4n2

2) n dispariLa scacchiera può essere suddivisa in

n−12

2

quadrati 2 x 2

n−1 rettangoli 2 x 1

1 quadrato 1 x 1

per un totale di n−12

2

n−11 quadrati/rettangoli, in ciascuno dei quali va collocato un re. Il numero dei re, quindi, è:

14n12

43

Consideriamo, come esempio, la scacchiera 9 x 9:

R R R R R

R R R R R

R R R R R

R R R R R

R R R R R

Problema n. 13

Qual è il numero minimo di Re che bisogna disporre su una scacchiera n x n, in modo che ogni casa sia dominata?

SoluzioneBasta considerare che un re può dominare, al più, un quadrato 3 x 3, occupandone la casa centrale.

Bisogna distinguere 3 casi:1) n = 3k

La scacchiera può essere suddivisa in

n3

2

quadrati 3 x 3, in ciascuno dei quali va collocato un re.

Il numero di re, quindi, è: n3

2

2) n = 3k+1

La scacchiera può essere suddivisa in:

n−13

2

quadrati 3 x 3

44

23n−1 rettangoli 3 x 1

1 quadrato 1 x 1

per un totale di n−13

2

23n−11 quadrati/rettangoli, in ciascuno dei

quali va collocato un re. Il numero dei re, quindi,è: n23

2

.Verifichiamolo su una scacchiera 7 x 7:

R R R

R R R

R R R

3) n = 3k+2La scacchiera può essere suddivisa in:

n−23

2

quadrati 3 x 3

23n−2 rettangoli 3 x 2

1 quadrato 2 x 2

per un totale di n−23

2

23n−21 quadrati/rettangoli, in ciascuno dei

quali va collocato un re. Il numero dei re, quindi, è: n13

2

.

45

E' il caso della scacchiera standard:

R R R

R R R

R R R

Le tre formule possono essere unificate mediante la funzione ceiling:

il numero dei re è: [ceiling n3 ]

2

.

46

LA DONNA

La Donna dispone dei seguenti movimenti(i,j) → (i+x, j) x≠0(i,j) → (i, j+y) y≠0(i,j) → (i+x, j+y) |x| = |y| , (x,y) ≠ (0,0) ovviamente x,y sono interi relativi tali da consentire alla Donna di restare all'interno della scacchiera.

Mobilità della Donna

Con riferimento alla Donna, la scacchiera è costituita da:

28 case di grado 2120 case di grado 2312 case di grado 254 case di grado 27possiamo costruire la variabile G:

G P 21 28/64 23 20/64 25 12/64 27 4/64

E(G) = 22.75 F = 13

47

Problema n.14

Qual è il numero massimo di Donne che è possibile porre su una scacchiera n x n in modo che nessuna ne attacchi un'altra?

SoluzioneSe n=2 è possibile collocare una sola donna.Se n=3 è possibile collocare 2 donne.Se n>3 è possibile collocare n donne. Stabilire in quanti modi le n donne possono disporsi sulla scacchiera, è un problema ancora irrisolto, nonostante il contributo di C.F.Gauss.Per n = 8, esistono 92 soluzioni, considerando distinte quelle che si ottengono per rotazioni o simmetrie. I modi essenzialmente distinti sono 12 . Qui di seguito sono elencate delle configurazioni che potrebbero essere assunte come fondamentali:

D

DD

DD

DD

D1

48

D

D D

DD

DD

D2

DD

DD

DD

DD

3

DD

DD

DD

DD

4

49

DD

DD

DD

DD

5

DD

DD

DD

DD

6

DD

DD

DD

DD

7

50

DD

DD

DD

DD

8

DD

DD

DD

DD

9

DD

DD

DD

DD

10

51

D

DD

DD

DD

D 11

DD

DD

DD

DD

12

52

Costruire una soluzione Calcolare, per ogni n, il numero delle soluzioni, e indicare un metodo per costruirle, è un problema difficile ma, per contro, è abbastanza semplice costruire una soluzione, per qualsiasi valore di n. Diamo, come esempio, una regola per ottenere una soluzione per i più comuni valori di n.

Dividiamo l'esempio in tre parti:1) n = 4, 6, 10 Si colloca una donna in (0, 1) e si procede sistemando le altre “a salto di Cavallo” del tipo (1, 2), fino a raggiungere l'ultima traversa. Poi si ricomincia, con la stessa tecnica, dalla prima casa della colonna successiva all'ultima colonna raggiunta.Applichiamo la regola al caso n = 6

DD

DD

DD

2) n = 5, 7

La soluzione per n = 5, si ottiene da quella costruita per n = 4 aggiungendo una donna in (4, 4).In modo analogo, la soluzione per n = 7 si ottiene da quella relativa a n = 6 aggiungendo una donna in (6, 6), come mostrato nella figura seguente

DD

DD

DD

D

53

3) n= 9In questo caso la regola precedente non è valida, per cui diamo una soluzione esplicita

DD

DD

DD

DD

D

Costruire una soluzione per n = 1, 2, 3, non è, ovviamente, un problema.

54

Problema n.15Qual è il numero minimo di Donne da collocare su una scacchiera n x n affinché ogni casa sia dominata?

SoluzioneQuesto problema è stato risolto per alcuni valori di n, ma non esiste una soluzione generale, tuttavia sussistono dei teoremi in virtù dei quali possiamo affermare che il numero cercato è compreso tra:

12

n e ceiling 23

n n pari

floor 12

n e ceiling 23

n n dispari

Poiché una sola donna domina una scacchiera 3 x 3, è molto semplice costruire una soluzione per i primi valori di n.Le figure seguenti rappresentano una soluzione per 6 ≤ n ≤ 10.

n = 6

D

D

D

n = 7

DD

DD

55

n= 8,9

DD

DD

D

Questa configurazione vale anche per n = 9, come è facile verificare aggiungendo una traversa a Sud e una colonna a Est.

n = 10

D

D

D

D

D

56

LA TORRE

La Torre dispone dei seguenti movimenti:(i,j) → (i+x, j) x≠ 0(i,j) → (i.j+y) y≠ 0con x e y interi relativi tali da mantenere la torre nell'ambito della scacchiera.

Mobilità della TorreCon riferimento alla Torre, la scacchiera è costituita da:64 case di grado 14.Possiamo costruire la variabile G:

G P 14 1

E(G)=14 F=8

Problema n.16Data una scacchiera m x n, in quanti modi è possibile collocare k Torri in maniera che nessuna ne attacchi un'altra?

Soluzione

Anzitutto deve essere kminm ,n perché su ogni riga e ogni colonna vi può essere al più una torre.I- caso : le torri sono distinguibili (etichettate, per esempio).Per collocare la prima torre disponiamo di mn case. Dopo aver sistemato la prima torre dobbiamo “eliminare” la traversa e la colonna che passano per la casa occupata dalla torre, di modo che per la seconda torre disponiamo di m−1n−1 case. In maniera del tutto analoga, per la terza

57

torre disponiamo di m−2n−2 case. Infine, per la k-esima torre disponiamo di m−k1n−k1 case.

In conclusione:la prima torre si può collocare in mn modile prime 2 torri in mnm−1n−1 modile prime 3 torri in mnm−1n−1m−2n−2 modi ...k torri in mnm−1n−1m−2n−2...m−k1n−k1 modi.

Poniamo T(m,n,k) = mnm−1n−1m−2n−2...m−k1n−k1

riordinando i fattori, si ha: T(m,n,k) = mm−1m−2... m−k1n n−1n−2... n−k1

T(m,n,k) = Dm,k Dn,k

Se la scacchiera è una n x n (ovvero m=n) sarà max k = n.In questo caso il numero dei modi in cui n torri possono essere collocate sulla scacchiera sarà: T(n,n,n) = Dn,n Dn,n = n! n !=n! 2

II-caso: le torri sono indistinguibili.La soluzione deriva in modo immediato da quella del problema precedente. Infatti: considerata una data disposizione di k torri distinguibili sulla scacchiera, se permutiamo le etichette in tutti i possibili modi otteniamo k! nuove disposizioni le quali, se le torri sono indistinguibili, si riducono ad una sola disposizione. In parole povere, se le torri sono indistinguibili, il numero dei modi determinato nel problema precedente si riduce di un fattore k!. Se indichiamo con R(m.n.k) il numero dei modi in cui k torri indistinguibili possono essere collocate su una scacchiera m x nsi ha R(m,n,k) = T m , n , k

k !

58

Se la scacchiera è una n x n, e vogliamo collocarvi il numero massimo di torri ( che è n) si ha: R(n,n,n) = n ! n !

n! = n!

Sulla scacchiera standard, quindi, si possono collocare al più 8 torri, e ciò si può fare in 8! modi, infatti ogni configurazione rappresenta una permutazione degli elementi (0, 1, 2, 3, 4, 5, 6, 7). Vediamone alcune:

permutazione: 76543210 T

TT

TT

TT

T

permutazione: 54031672T

TT

TT

TT

T

59

Problema n.17Qual è il numero minimo di Torri che occorre collocare su una scacchiera n x n in modo che ogni casa risulti dominata?

SoluzioneIl numero minimo è n. Infatti, se sulla scacchiera ci fossero meno di n torri, almeno una traversa e almeno una colonna sarebbero prive di torri. Una casa intersezione fra una traversa e una colonna prive di torri non sarebbe dominata, ovvero la scacchiera non sarebbe dominata. Per dominare la scacchiera, quindi, è necessario ( e sufficiente ) che ci sia una torre su ogni colonna ( o su ogni traversa ). Fatta questa considerazione, è abbastanza agevole dimostrare che le configurazioni possibili sono:

2nn - n!

Su una scacchiera 8 x 8, quindi, le configurazioni possibili sono:

2∙88 - 8! = 33.514.312

Vediamone alcune:

TTTT

TTTT

60

T T T TT T T T

TTT

TT

TT

T

T T T T T T T T

61

62

L' ALFIERE

L'Alfiere dispone del seguente movimento:(i,j) → (i+x, j+y); |x| = |y|; (x, y) ≠ (0, 0)

Mobilità dell'AlfiereCon riferimento all'Alfiere, la scacchiera è costituita da:28 case di grado 720 case di grado 912 case di grado 11 4 case di grado 13

costruiamo la variabile G:

G P 7 28/64 9 20/64 11 12/64 13 4/64

E(G) = 8.75 F = 5

63

Problema n.18

Qual è il numero massimo di Alfieri che è possibile collocare su una scacchiera n x n in modo che nessuno ne attacchi un altro?

Soluzione

Il numero massimo è 2n-2.Infatti, ci sono 2n-1 diagonali aventi una stessa direzione, ma le due diagonali costituite da una sola casa non possono essere entrambe occupate, perché situate sulla stessa diagonale. Questo fatto riduce le diagonali a 2n-2.Gli alfieri vanno collocati tutti sul bordo della scacchiera ( teorema di Yaglom e Yaglom ).Su una scacchiera standard, quindi, si possono collocare 14 alfieri, e ciò può essere fatto in 256 modi. Infatti, considerando la seguente figura:

Z f1 e1 d1 c1 b1 a1 Wf4 a2

e4 b2

d4 c2

c4 d2

b4 e2

a4 f2

X a3 b3 c3 d3 e3 f3 Y

1) collochiamo una coppia di alfieri in due case d'angolo appartenenti ad uno stesso lato (necessariamente).Ciò può essere fatto in 4 modi: X-Y, X-Z, Z-W, Y-W.2) Collochiamo la seconda coppia di alfieri in due vertici opposti del rettangolo a1a2a3a4 . Possiamo farlo in due modi: a1a3 – a2a4.

3) Collochiamo la terza coppia di alfieri in due vertici opposti del rettangolo b1b2b3b4. Possiamo farlo in due modi: b1b3 -b2b4.

64

4) Procedendo così fino a collocare la settima coppia in due vertici opposti del rettangolo f1f2f3f4, avremo che il numero totale delle configurazioni sarà:

4∙2∙2∙2∙2∙2∙2 = 28 = 256

Vediamo due possibili disposizioni:

A A A A A A

A A A A A A A A

A A A A A

A AA A

A A A A A

Su una scacchiera n x n le possibili configurazioni sono 2n:infatti, fissate le due case d'angolo ( possiamo farlo in 4 modi ), restano n-2 case, ciascuna delle quali genera 2 possibili scelte:

4∙2n-2 = 2n

65

Problema n.19

Qual è il numero minimo di Alfieri che occorre disporre su una scacchiera n x n, in modo che ogni casa risulti dominata?SoluzioneIl numero minimo è n. Sulla scacchiera standard, quindi, è 8. Infatti, il bordo della scacchiera è costituito da 14 case bianche e 14 nere, e un alfiere ne può dominare al più 4 dello stesso colore. Occorrono, quindi, almeno 4 alfieri campochiaro per dominare le 14 case bianche e 4 alfieri camposcuro per dominare le 14 case nere. Occorrono, quindi, almeno 8 alfieri per dominare il bordo della scacchiera e, a maggior ragione, occorrono almeno 8 alfieri per dominare l'intera scacchiera. I seguenti esempi mostrano che sono anche sufficienti:

AAAAAAAA

A A A A A A A A

66

A AA A A AA A

E' stato dimostrato (Yaglom e Yaglom) che su una scacchiera n x n (con n=4k) le configurazioni possibili sono:

2k ! 4k12

2

su una scacchiera 8 x 8, quindi, ci sono 11664 configurazioni possibili.Costruire una soluzione, per ogni n, è semplicissimo, perché basta allineare gli alfieri lungo la colonna centrale, se n è dispari, o lungo una delle due colonne centrali, se n è pari.

67

68

IL CAVALLO

Il Cavallo dispone del seguente movimento:

(i,j) → (i ±2, j ±1)(i,j) → (i ±1, j ±2)

Osservazione importanteSupponiamo che il cavallo effettui la mossa (i,j)→ (x,y) e che sia i+j=p e x+y=s. La differenza s-p può assumere i valori -3, -1, 1, 3, e, quindi, s-p è dispari, ovvero s e p hanno parità diversa. In modo più esplicito, le case (i,j) e (x,y)sono di colore diverso.Queste brevi considerazioni ci permettono di affermare che il “grafo del cavallo” è un grafo bipartito.Ciò implica che il cavallo necessita di un numero pari di mosse per spostarsi da una casa ad un'altra dello stesso colore(in particolare, per rientrare nella casa di partenza!).

Mobilità del cavallocon riferimento al Cavallo, la scacchiera è costituita da: 4 case di grado 2 8 case di grado 320 case di grado 416 case di grado 616 case di grado 8

costruiamo la variabile G: G P 2 4/64 3 8/64 4 20/64 6 16/64 8 16/64

E(G) = 5.25 F = 3

69

Problema n.20

Qual è il numero massimo di Cavalli che è possibile collocare su una scacchiera n x n in modo che nessuno ne attacchi un altro?

Soluzione

il numero massimo è: 12

n2 ; n pari 2

12n21 ; ndispari

Infatti, se n è pari, la scacchiera è costituita da un numero pari di case ( n2 ),e le case nere sono tante quante le bianche ( 1

2⋅n2 ).

Il massimo che si può fare è collocare un cavallo in ciascuna delle case di uno stesso colore, come mostra l'esempio seguente:

C C C CC C C C

C C C CC C C C

C C C CC C C C

C C C CC C C C

Se n è dispari,la scacchiera è costituita da un numero dispari di case ( n2 ),e le case di un colore superano di una unità le case dell'altro colore. Se indichiamo con p il numero delle case del colore prevalente, quelle dell'altro colore saranno p-1, ed è:

p p−1=n2 → p=12⋅n21 .

70

Il massimo che si può fare è porre un cavallo in ciascuna delle case del colore prevalente. In figura è rappresentata la soluzione per n = 5:

C C CC C

C C CC C

C C C

Se n = 2, il numero massimo di cavalli è chiaramente 4.

71

Problema n.21

Qual è il numero minimo di Cavalli che occorre collocare su una scacchiera n x n in modo che ogni casa risulti dominata?

Soluzione Per questo problema non esiste una soluzione generale. Esaminiamo le soluzioni per alcuni valori di n :

n = 2, 3, 4 Occorrono 4 cavalli. Per n = 2 non c'è nulla da aggiungere. Per n = 3, osserviamo che un cavallo sul bordo della scacchiera domina 3 case, ma 3 cavalli sul bordo non riescono a dominarne 9, perché nessuno controlla quella centrale, ed è necessario porre un cavallo al centro della scacchiera:

C CC C

questa soluzione vale anche per n = 4, aggiungendo, in modo opportuno, una traversa e una colonna alla scacchiera.

n = 5Occorrono 5 cavalli. Ragioniamo per assurdo, e proviamo che 4 cavalli non sono sufficienti. La figura seguente mostra il numero di case ( in seguito indicato con d ) che un cavallo domina da ciascuna delle 25 posizioni sulla scacchiera:

3 4 5 4 34 5 7 5 45 7 9 7 54 5 7 5 43 4 5 4 3

se 4 cavalli dominano 25 case, ognuno, in media, ne domina 6.25, e bisogna, perciò, usare (collocandovi un cavallo) almeno una casa per la quale d > 6.Se non si usa la casa centrale ( d = 9 ), è necessario usare almeno 3 case aventi d = 7 . Le scelte possibili sono equivalenti, perché le case dominate sarebbero, comunque, solo 15. La casa centrale, quindi, deve essere usata.

72

Oltre la casa centrale, è necessario utilizzare, per ovvi motivi, almeno una casa con d = 7 (una qualsiasi, perché le quattro case si equivalgono). Una possibile scelta, e la situazione che si determina, è presentata nella seguente figura

x x x x

x x xC C

x x xx x x x

osserviamo che restano 9 case “libere”. Indichiamo con L l'insieme costituito da queste case. Gli altri due cavalli devono dominare L.Nella seguente figura è mostrato il numero delle case di L che sono dominate da un cavallo, per ognuna delle 25 posizioni sulla scacchiera.

1 1 1 2 31 3 5 1 02 0 0 5 31 3 5 1 01 1 1 2 3

Per dominare L, occorre usare due case per le quali sia d = 5 ma, come è facile verificare, da due qualsiasi di queste case è possibile dominarne solo 8 appartenenti a L. Possiamo concludere, quindi, che 4 cavalli non sono sufficienti e ne occorrono almeno 5. La seguente configurazione è la prova che sono anche sufficienti:

CC C C

C

73

n = 6 Occorrono 8 cavalli. Infatti, se consideriamo la seguente scacchiera e poniamo l'attenzione sulle case della prima e dell'ultima traversa

risulta evidente che occorrono 2 cavalli per dominare le case bianche della prima traversa, e ne occorrono altrettanti per dominare le nere. Poiché un cavallo che domina una casa della prima traversa non domina alcuna casa dell' ultima, occorrono altri 4 cavalli per dominare le case dell'ultima traversa. In conclusione, sono necessari 8 cavalli per dominare le case delle due traverse e, a maggior ragione, occorrono almeno 8 cavalli per dominare l'intera scacchiera. La seguente disposizione evidenzia che sono anche sufficienti:

C C C CC C C C

74

n=7Per dominare una scacchiera 7 x 7 occorrono 10 cavalli.Infatti, osservando la seguente figura ci si convince che non è possibile usarne un numero minore

perché un cavallo può dominare una sola delle case ombreggiate, per cui sono necessari 10 cavalli per dominarle tutte e, a maggior ragione, ne occorrono almeno 10 per dominare l'intera scacchiera. Dalla seguente figura risulta evidente che sono anche sufficienti:

C C C C C

C C C C C

75

n = 8Per dominare una scacchiera 8 x 8 sono necessari 12 cavalli.Se esaminiamo la seguente figura risulta evidente che non è possibile usarne un numero minore, perché un cavallo può dominare una sola delle case ombreggiate, per cui ne occorrono 12 per dominarle tutte e, a maggior ragione, ne occorrono almeno 12 per dominare l'intera scacchiera.

La seguente disposizione dimostra che sono anche sufficienti:

CC C C C

CC

C C C CC

76

n = 9Occorrono 14 cavalli. Nella seguente figura, le case colorate sono state scelte in modo che un cavallo non possa dominare, contemporaneamente, case di colore diverso

sono necessari 4 cavalli per dominare le case rosse, 4 per dominare le gialle, 3 per le verdi e 3 per le celesti. In totale, 14 cavalli, i quali, come si evince dalla seguente figura, sono sufficienti per dominare la scacchiera.

C

C C C CC C

C CC C C C

C

77

n = 10Occorrono 16 cavalli. Nella seguente figura, le case colorate sono state scelte in modo che un cavallo non possa dominare, contemporaneamente, case di colore diverso

Sono necessari 4 cavalli per dominare le case verdi, 4 per dominare le rosse, 4 per le gialle e 4 per le celesti. In totale 16 cavalli, che, come risulta evidente dalla seguente figura, sono sufficienti per dominare la scacchiera.

C CC C C C

C C

C CC C C C

C C

78

Problema n. 22

Data una scacchiera n x n (n>3), qual è il numero minimo di mosse affinché un Cavallo si sposti dalla casa (0,0) alla casa (n-1, n-1)?

Soluzione

Sia m il numero cercato.Lo spostamento massimo che un cavallo può effettuare (con una sola mossa) lungo la diagonale è di 3

2 di passo diagonale, e per spostarsi da (0,0) a (n-1, n-1) sono necessari almeno n-1 passi diagonali. Con m passi il cavallo può spostarsi, al massimo, di 3

2m passi diagonali e, quindi,

dovrà essere

32

mn−1 ovvero m23n−1

In conclusione, m è il più piccolo numero che soddisfa simultaneamente le seguenti condizioni:

{m 23n−1

m èinteromè pari

}Esempio: Su una scacchiera standard (n=8), quante mosse sono necessarie per spostarsi da (0,0) a (7,7)?deve essere m 2

38−1m4.67 ovvero m = 6 perché 6 è il più piccolo

intero pari che sia maggiore di 4.67.

Cerchiamo una relazione immediata tra n e m:

n = 3k m 233k−1 → m2k−2

3 → m=2k

79

n = 3k+1 m 233k → m2k → m=2k

n = 3k+2 m 2

33k1 → m2k2

3 → m=2k2

Dopo aver determinato quante mosse sono necessarie per effettuare lo spostamento richiesto, vediamo come effettuare tale spostamento.

I) n = 3k k > 11. il cavallo esegue la mossa (1,2) k+1 volte2. esegue la mossa (2,-1) una volta3. esegue la mossa (2,1) k-2 volte

0,0k11,22,−1k−22,1=3k−1,3k−1=n−1,n−1

II) n = 3k+11. il cavallo esegue la mossa (1,2) esattamente k volte2. esegue la mossa (2,1) esattamente k volte

0,0k 1,2k 2,1=3k ,3 k =n−1, n−1

III) n = 3k+21. il cavallo esegue la mossa (1,2) esattamente k volte2. esegue la mossa (2,-1) una volta3. esegue la mossa (-1,2) una volta4. esegue la mossa (2,1) esattamente k volte.

0,0k 1,22,−1−1,2k 2,1=3k1,3k1=n−1,n−1

80

L'eccezione che conferma la regola:

Su una scacchiera 3 x 3 occorrono 4 mosse per spostarsi da (0,0) a (2,2), come mostrato nella seguente figura:

1 4 3 0 2

Problema n. 23 (ciclo euleriano)Data una scacchiera n x n , è possibile, per un cavallo, partire da una casa e farvi ritorno dopo aver percorso tutti gli archi una sola volta?Il problema equivale a stabilire se esiste un ciclo euleriano sul grafo del Cavallo.SoluzioneSe n = 3 il problema ammette soluzione, perché tutte le case della scacchiera hanno grado pari. Per costruire un ciclo euleriano basta numerare le case come in figura:

1 2 3 4 5 6 7 8 9

e rappresentare il grafo associato:

6_____ 1______ 8| |7 5 3 | |2_____ 9______ 4

un ciclo potrebbe essere 1-8-3-4-9-2-7-6-1.Se n > 3 il problema è impossibile, perché sulla scacchiera saranno sempre presenti case di grado dispari, come si evince dalla seguente figura che si riferisce a una 4 x 4 ( nelle case è indicato il grado ):

81

3 3 3 3 3 3

3 3

La presenza di più di 2 case di grado dispari esclude anche l'esistenza di un cammino euleriano.

Problema n. 24 ( ciclo hamiltoniano )

Data una scacchiera n x n, è possibile, per un Cavallo, partire da una casa e farvi ritorno dopo aver “visitato” tutte le case esattamente una volta?Il problema equivale a stabilire l'esistenza un ciclo hamiltoniano sul grafo del Cavallo.

Soluzione

Se n è dispari, il problema è impossibile. Infatti, la scacchiera è costituita da una numero dispari di case (n2), e il cavallo, dovendo visitarle tutte, dovrà compiere un numero dispari di mosse per poter rientrare nella casa di partenza, ma ciò è assurdo perché un grafo bipartito contiene solo cicli pari.

Se n è pari, bisogna considerare due possibilità:

1) n = 4in questo caso il problema non ammette soluzione, ed è facile rendersene conto osservando la seguente figura:

XB

AY

82

le case A e B sono le uniche disponibili per accedere alle case X e Y ( e per uscirne!). Se bisogna visitare tutte le case, sarà necessario visitare 2 volte almeno una delle case A e B.

2) n > 4 il problema ammette soluzione, ma non è semplice costruire un ciclo hamiltoniano. Una tecnica abbastanza efficace che conduce ad un cammino aperto, è dovuta a De Moivre. Tale tecnica consiste nell'iniziare il cammino da una casa del bordo, e di mantenersi vicino al bordo quanto più è possibile, visitando le case centrali solo quando è strettamente necessario. Un metodo più “scientifico” utilizza il principio di Warnsdorff:

“ad ogni mossa il cavallo deve visitare la casa di grado minimo”. In sostanza, il principio suggerisce di visitare per ultimo le case di grado più alto perché si ha una maggiore “possibilità di manovra” nella fase finale. Le figure seguenti mostrano un cammino hamiltoniano costruito da De Moivre:

34 49 22 11 36 39 24 121 10 35 50 23 12 37 4048 33 62 57 38 25 2 139 20 51 54 63 60 41 2632 47 58 61 56 53 14 319 8 55 52 59 64 27 4246 31 6 17 44 29 4 157 18 45 30 5 16 43 28

e un ciclo hamiltoniano dovuto ad Eulero:

43 30 11 56 45 28 5 5812 55 44 29 10 57 46 2731 42 13 62 17 6 59 454 19 16 9 14 61 26 4741 32 63 18 7 48 3 6020 53 8 15 64 23 36 2533 40 51 22 35 38 49 252 21 34 39 50 1 24 37

83

Un cammino hamiltoniano esiste per n ≥ 5. Un ciclo hamiltoniano esiste per n ≥ 6 e n pari.

Ciclo pitagoricoSe si unisce con un tratto rettilineo il centro della casa di partenza e il centro della casa di arrivo di una mossa di Cavallo, si ottiene un segmento che chiameremo “passo di Cavallo”.Osserviamo la figura seguente:

passi di Cavallo

Due passi di cavallo consecutivi possono descrivere, oltre all'angolo nullo e all'angolo piatto, solo i seguenti angoli:

per i quali è facile calcolare le ampiezze:α = tan-1(3/4) ≈ 36o 52´ 11” β = tan-1 (4/3) ≈ 53o 7´ 48”γ = 90o δ = 90o + α ε = 90o + β

Gli angoli acuti α e β sono tipici dei triangoli rettangoli del tipo 3: 4: 5, per cui, questi sono gli unici triangoli che si possono formare con passi di Cavallo.

84

Su una scacchiera 9 x 11 è possibile realizzare un percorso chiuso che descrive un triangolo rettangolo il cui cateto minore misura 3 passi di Cavallo, il maggiore 4, e l'ipotenusa 5, come mostra la figura sottostante:

Se la scacchiera è sufficientemente ampia, è possibile costruire cicli “pitagorici” lunghi a piacere, per i quali vale una sorta di proprietà frattale, perché tutti descrivono triangoli rettangoli simili a quello “primitivo” rappresentato in figura.

Ciclo minimoCon 4 mosse è possibile costruire solo i seguenti cicli minimi

è interessante notare che l'area dei poligoni descritti (due rombi e un quadrato) è, nell'ordine, 3, 4 e 5 quadratini!La più famosa fra le terne pitagoriche lega i cicli che descrivono un triangolo (poligono col minimo numero di lati) e quelli che descrivono un quadrilatero (poligono costruibile col minimo numero di mosse).

85

Problema n. 25 ( Guarini )

Su una scacchiera 3 x 3 collochiamo i 2 Cavalli neri e i 2 Cavalli bianchi nella posizione iniziale:

CB CB

CN CN

CB = cavallo biancoCN = cavallo nero

il problema consiste nel muovere alternativamente i cavalli in modo da raggiungere la posizione finale:

CN CN

CB CB

con il minimo numero di mosse. Questo problema fu proposto nel 1512 dal matematico Guarini di Forlì.

Soluzione

Numeriamo le case della scacchiera con i numeri 1,2 ,3 , ...,9 e consideriamo il grafo associato

1 2 34 5 67 8 9

86

CB 6___1___8

| |CN 7 5 3 CB

| | |2___9___4

CN

si vede facilmente che il problema si risolve muovendo i cavalli sempre nello stesso senso (orario/antiorario). Sono richieste 16 mosse.Una soluzione è la seguente:

1-8, 7-6, 9-2, 3-4, 8-3, 6-1, 2-7, 4-9, 3-4, 1-8, 7-6, 9-2, 4-9, 8-3, 6-1, 2-7.

87

Pegaso !

Ricordiamo che si chiama sezione aurea di un segmento quella parte di esso che è media proporzionale fra l'intero segmento e la parte restante.Se AB è il segmento dato e AC la sua sezione aurea, si deve avere

A------------------C--------B

AB : AC = AC : CB

Se indichiamo con s la misura dell'intero segmento e con x la misura della sezione aurea, deve essere

s : x = x : ( s-x )

da cui x2 = s( s-x)

e anche x2 + sx -s2 = 0

L' equazione ha certamente radici reali, una positiva e una negativa; accettando la sola positiva, abbiamo

x=s˙5−12

ovvero xs=5−1

2=0.6180339...

Questa relazione prova che un segmento e la sua sezione aurea sono grandezze incommensurabili, in quanto il loro rapporto è un numero irrazionale. Il rapporto s

x=1 5

2 =1.6180339... è detto rapporto aureo o numero d'oro, e viene indicato con la lettera Φ, in onore di Fidia, che ne ha fatto un grande uso ( ad esempio, nel Partenone).Il numero Φ gode di notevoli proprietà , tra cui:

1) Φ+1 = Φ2

2) Φ-1 = 1/ Φ

88

La sezione aurea ha una funzione di grande rilievo nell'espressione della bellezza, per cui fu definita “aurea” nel Rinascimento. L'alto valore estetico della sezione aurea fu riconosciuto fin dai tempi antichi. Essa, infatti, si riscontra nelle opere d'arte e in particolare nelle strutture dell'architettura egiziana e greca.

Il matematico Luca Pacioli (1445 – 1517 ) scrisse su di essa un libro intitolato “ De divina proportione “, illustrato con figure di Leonardo da Vinci.In epoca moderna, troviamo la sezione aurea in molti capolavori di Michelangelo, Leonardo, Brunelleschi, Bramante, Tiziano, ecc.Essa domina nel Palazzo Ducale di Venezia, al quale conferisce, insieme alla simmetria, un aspetto di insuperabile armonia. Troviamo la sezione aurea anche nel cavallo, ad esprimere l'armonioso equilibrio delle varie parti del suo corpo.In epoca recente, attraverso numerose osservazioni, è stato rilevato che la divisione in sezione aurea dell'altezza dell'uomo adulto, da parte dell'ombelico, è esatta, come dato statistico medio. Dopo questa brevissima incursione nel mondo dell'arte e della natura, torniamo agli scacchi.Una mossa di Cavallo va dalla casa ( i, j ) alla casa ( i ± 1, j ± 2) oppure ( i ± 2, j ± 1) per cui ad ogni mossa resta “associato” un triangolo rettangolo nel quale, se si assume come unità di misura il lato di un quadratino, le misure dei lati sono 1, 2, √5 . Il legame col numero d'oro risulta evidente : Ipotenusa+Cateto minore = √5 +1 = Φ Cateto maggiore 2

89

Le mirabili proprietà di cui gode la MOSSA DEL CAVALLO sono sintetizzate nei seguenti eleganti grafici:

90

Il primo evidenzia il legame fra i due triangoli connessi con il movimento del Cavallo, il secondo, ottenuto dal precedente doppiando ad ogni passo l'ipotenusa del triangolo 3: 4: 5 (b – grigio chiaro) e combinando i triangoli ottenuti con i triangoli 1: 2: √5 in modo da generare triangoli isosceli ( a, b, c, d, e ). La curva rappresentata approssima la spirale logaritmica, di cui parleremo nel paragrafo seguente.

91

EADEM MUTATA RESURGO

Un rettangolo nel quale il rapporto tra il lato maggiore e quello minore sia il numero d'oro, si dice rettangolo aureo.Se dividiamo un rettangolo aureo in due parti, in modo che una di esse sia un quadrato, l'altra parte sarà ancora un rettangolo aureo. Se dividiamo anche questo rettangolo in due parti, come abbiamo fatto con il rettangolo dato, avremo ancora un rettangolo come i due precedenti. Continuando così avremo rettangoli aurei sempre più piccoli. Per chiarire quanto detto, consideriamo un rettangolo 21 x 13 ( elementi consecutivi della successione di Fibonacci!!) che rappresenta, grosso modo, un rettangolo aureo ( 21

13=1.615... )

92

tracciamo, in modo opportuno, degli archi di circonferenza nei successivi quadrati in cui abbiamo suddiviso il rettangolo, come indicato nella figura sottostante. La curva, che così si ottiene, approssima una spirale logaritmica!!

La spira mirabilis, la cui equazione in coordinate polari è ρ = aθ (a>1), si riscontra spesso in natura. Ecco alcuni esempi:– disposizione delle foglie sui rami degli alberi ( fillotassi)– i molluschi, in genere, costruiscono la loro conchiglia secondo le leggi

della spirale logaritmica– i ragni tessono la loro tela tracciando una spirale logaritmica.

L'illustre matematico Jacques Bernoulli, studiò le proprietà di questa curva per cui essa, sottoposta a diverse trasformazioni geometriche, si riproduce. Egli volle che fosse incisa sulla sua tomba con l'iscrizione: “Eadem mutata resurgo “, cioè “ mutata, pur rinasco la stessa”.

93

94

Il PEDONE

Il Pedone dispone dei seguenti movimenti:

(i, j)→(i, j+1) oppure (i, j)→(i, j+2) se muove dalla casa origine

(i, j)→(i, j+1) negli altri casi.Mobilità del pedoneIl Pedone non può essere collocato sulla prima traversa né sull'ultima, per cui le case disponibili sono 48. Costruiamo la variabile G:

G P 1 12/48 2 36/48

E(G) = 1.75 F = 1

Due pedoni.... ed un quadrato!Tutti gli scacchisti conoscono la regola del quadrato del pedone; meno nota, invece, è la regola del quadrato comune a due pedoni: il quadrato comune a due pedoni isolati, è quello la cui diagonale parte dalla casa del meno avanzato ( se non sono sulla stessa traversa ) e arriva fino alla colonna del più avanzato, come mostrato nella seguente figura:

Fig. 1

**

*P *

*P

95

Se tale quadrato raggiunge o supera il bordo della scacchiera uno dei pedoni è inarrestabile. Applichiamo la nostra regola alle posizioni illustrate dalle seguenti figure ( con i pedoni situati sulla stessa traversa):

p = pedone nero

P = pedone bianco

r = re nero

R = re bianco

Fig. 2

p pR

96

Fig. 3

r

P P

Il quadrato dei pedoni neri in Fig. 2 non tocca il bordo della scacchiera e l'esito della lotta è incerto.In Fig. 3 il quadrato dei pedoni bianchi raggiunge il bordo della scacchiera ed uno dei pedoni è inarrestabile.

97

98

III

L'ALBERO DEGLI SCACCHI

99

Il teorema di Zermelo

Gli scacchi sono un gioco finito e a informazione perfetta.Finito, perché ogni giocatore ha un numero finito di mosse a disposizione, e il gioco si conclude dopo un numero finito di mosse.A informazione perfetta vuol dire che il giocatore cui spetta la mossa, è a conoscenza dell'intera storia del gioco, ovvero non solo conosce tutte le sue mosse passate, ma anche quelle degli altri giocatori.Il matematico tedesco Ernst Zermelo ha dimostrato che il gioco degli scacchi è strettamente determinato,nel senso che vale una sola delle seguenti tre alternative:– esiste una strategia vincente per il Bianco;– esiste una strategia vincente per il Nero;– esiste una strategia che conduce forzatamente alla patta.Egli riuscì a dimostrare questo risultato utilizzando un algoritmo di induzione a ritroso, la cui logica è illustrata dall'esempio seguente:Il gioco si svolge tra due giocatori A e B, ed è caratterizzato dalle seguenti regole:

1) muove per primo A ( e dopo muove B);2) A dispone di 2 mosse, a1 , a2;3) B dispone di 3 mosse, b1, b2 e b3;4) l'esito del gioco può essere

V vince A S vince B (A è s-confitto) P patta.Il gioco può essere rappresentato dal seguente diagramma ad albero di immediata comprensione:

100

101

Se A inizia con la mossa a1 si arriva al nodo 2 e la mossa tocca a B, il quale sceglierà b2, perché è la mossa che lo fa vincere. Il giocatore A “anticipa mentalmente” la scelta di B e assegna al nodo 2 l'esito S.Se A inizia con a2 si arriva al nodo 3, B risponderà con b1 e patta. Anche qui il giocatore A “anticipa mentalmente” la scelta di B e assegna al nodo 3 l'esito P. E' evidente che l'esito di questo gioco è predeterminato: A, che non vuole perdere, giocherà a2 e B, che non vuole perdere, risponderà b1 e la partita terminerà sempre patta.Anche per gli scacchi si può, in teoria, costruire un albero simile al precedente e analizzare il gioco con la tecnica appena illustrata dell'induzione a ritroso:l'esito della partita sarebbe deciso dopo la prima mossa o , addirittura, prima di iniziare a giocare! E' ovvio che il teorema non afferma che una singola partita termina con la vittoria del Bianco, oppure con quella del Nero oppure con una patta (sarebbe la scoperta dell'acqua calda!), ma che ogni partita giocata finisce sempre allo stesso modo, uno dei tre possibili. In ultima analisi, il teorema asserisce che non è possibile che due giocatori razionali, pur conoscendo l'albero del gioco, non siano in grado di stabilire, a priori, l'esito di ogni partita giocata fra loro. Per fortuna, l'Albero degli Scacchi avrebbe un numero di nodi così elevato da risultare “intrattabile” anche per un computer super potente. Per farsi un'idea delle sue dimensioni facciamo l'ipotesi, restrittiva, che una partita si concluda dopo la 20-esima mossa del Nero e che ogni giocatore abbia avuto a disposizione, per ogni mossa, 20 possibili scelte.L'albero associato a questa ipotetica partita avrebbe un numero di nodi uguale a 20+202+203+...+2040 ≈ 1.16∙1052. Poiché in un anno ci sono 3.15∙107 secondi, se un computer analizzasse 1010 nodi al secondo, in un anno riuscirebbe ad analizzare 1010∙3.15∙107 = 3.15∙1017 nodi e, quindi, per visitare l'intero albero impiegherebbe

1.16⋅1052

3.15⋅1017≈3.7⋅1034 anni!!

102

I programmi per gli scacchi hanno compiuto progressi enormi negli ultimi decenni, soprattutto per quanto riguarda gli algoritmi di ricerca, tanto è vero che:– nel 1978, il maestro internazionale David Levy fu sconfitto da

CHESS 4.7– nel 1988, il grande maestro Bent Larsen fu sconfitto da

DEEP TOUGHT– nel 1997, il campione del mondo Garry Kasparov fu sconfitto da

DEEP BLUE, non in una partita singola, ma in un vero e proprio torneo!

Nonostante questi progressi, però, il gigantesco albero degli scacchi non potrà mai essere “visitato” completamente, per cui gli scacchisti possono dormire sonni tranquilli!

103

IV

QUADRATI DI EULERO

104

Quadrati latiniIl matematico svizzero Leonardo Eulero iniziò lo studio sistematico dei quadrati latini verso la fine del '700, con uno scopo meramente ricreativo . Oggi essi trovano importanti applicazioni in vari campi ( in statistica, per esempio), pur conservando l'originario carattere ludico, come dimostra il grande successo riscosso dal SUDOKU, che è diventato uno dei giochi più diffusi.Un quadrato latino di ordine n è una una griglia n x n , le cui case sono occupate da n simboli distinti, in modo che ogni simbolo compaia una sola volta in ogni riga e in ogni colonna.Un esempio è sufficiente per capire:Vogliamo disporre 4 Re, 4 Donne, 4 Torri e 4 Alfieri, su una scacchiera 4 x 4, in modo che ciascuna figura compaia una sola volta su ogni traversa e su ogni colonna. Ecco una soluzione:

R A T DD R A TT D R AA T D R

Costruire un quadrato latino di ordine n è molto semplice se si usano come simboli i numeri da 0 a (n-1), perché con tale accorgimento è possibile avvalersi dell'aritmetica modulare: nella casa ( i, j ) si riporta il valore z = (ki+ j) modn , dove k è un intero positivo primo con n.Come applicazione della regola, costruiamo un quadrato di ordine 4, ponendo k = 1:

3 0 1 22 3 0 11 2 3 00 1 2 3

Da un quadrato se ne possono ottenere altri permutando le righe (colonne), oppure mediante permutazione circolare degli elementi.L'uso dei numeri è utile per costruire il quadrato, ma è ovvio che possiamo impiegare dei simboli a piacere: basta stabilire una corrispondenza tra gli n simboli desiderati e gli n numeri 0, 1, 2, ... (n-1), ed effettuare la

105

sostituzione. Nel nostro esempio, potremmo usare come simboli quattro colori, ponendo 0=giallo, 1=verde, 2=rosso, 3=celeste, ed il quadrato assumerebbe il seguente aspetto:

SchedulingProblema: preparare il calendario per un torneo al quale partecipano 2n giocatori.Questo problema si risolve velocemente con l'uso dei quadrati latini.Abbiamo visto che un quadrato latino si costruisce facilmente ( un modo è quello di scrivere la tabella dell'addizione modulo n; un altro modo, ancora più immediato, consiste nello scrivere nella prima riga i numeri da 1 a n in ordine crescente e, nelle righe successive, cambiarli per sostituzione circolare: 1→2→3...n→1).Consideriamo le seguenti ipotesi:a) i giocatori sono divisi in due squadre di n elementi, e ogni giocatore di

una squadra deve incontrare ogni giocatore dell'altra squadra.b) ognuno dei 2n giocatori deve incontrare tutti gli altri. Caso a:si costruisce un quadrato latino di ordine n; le righe vengono intestate ai giocatori di una squadra e le colonne ai giocatori dell'altra. I numeri all'interno del quadrato rappresentano i turni.Esempio:numero giocatori: 6 (=2n, n=3)I squadra: A, B, CII squadra: X, Y, Zcostruiamo un quadrato latino 3 x 3:

X Y ZA 1 2 3B 2 3 1C 3 1 2

i turni saranno:I TURNO: AX, BZ, CY

106

II TURNO: AY, BX, CZIII TURNO: AZ, BY, CX.

L'esempio è facilmente generalizzabile.Caso bEsempio:numero giocatori: 6 (=2n)giocatori: A, B, C, D, E, F.Costruiamo un quadrato latino di ordine 5 (=2n-1) intestando le righe e le colonne a 5 dei 6 giocatori (immaginiamo di escludere, provvisoriamente, il giocatore F), avremo la seguente tabella:

A B C D EA 1 2 3 4 5B 2 3 4 5 1C 3 4 5 1 2D 4 5 1 2 3E 5 1 2 3 4

ora bisogna eliminare gli elementi che sono sulla diagonale principale ( perché un giocatore non gioca contro se stesso) e, creare una nuova riga e una nuova colonna da intestare al sesto giocatore. Le due cose si ottengono semplicemente aggiungendo una nuova riga e una nuova colonna nelle quali saranno trascritti tutti gli elementi della diagonale in modo che ogni elemento sarà trascritto nell'ultima colonna (ferma restando la riga) e contemporaneamente nell'ultima riga (ferma restando la colonna). Si otterrà la seguente tabella:

A B C D E FA - 2 3 4 5 1B 2 - 4 5 1 3C 3 4 - 1 2 5D 4 5 1 - 3 2E 5 1 2 3 - 4F 1 3 5 2 4 -

Poiché la tabella è simmetrica rispetto alla diagonale principale, basta considerare solo la metà superiore ( o inferiore).

107

I turni saranno:

I TURNO II TURNO III TURNO IV TURNO V TURNO

A-F A-B A-C A-D A-E B-E C-E B-F B-C B-D C-D D-F D-E E-F C-FPer assicurare ad ogni giocatore una certa alternanza nella posizione di I o II giocatore ( per esempio, nel calcio, giocare in casa o fuori; negli scacchi, giocare col bianco o col nero.) si può decidere che il I giocatore è il giocatore RIGA nei turni dispari, ed il giocatore COLONNA nei turni pari. Una migliore alternanza si ottiene se il quadrato latino è costruito usando la tabella dell'addizione modulo (2n-1). Ripetiamo l'esempio con l'aiuto della tabella dell'addizione modulo 5:

+ 0 1 2 3 40 0 1 2 3 41 1 2 3 4 02 2 3 4 0 13 3 4 0 1 24 4 0 1 2 3

A questo punto, come nel caso precedente, aggiungiamo una riga e una colonna ed eliminiamo gli elementi della diagonale principale:

0 1 2 3 4 50 - 1 2 3 4 01 1 - 3 4 0 22 2 3 - 0 1 43 3 4 0 - 2 14 4 0 1 2 - 35 0 2 4 1 3 -

Intestiamo le righe e le colonne ai giocatori e, all'interno del quadrato sostituiamo, per comodità, lo 0 con il 5 e avremo la tabella finale:

108

A B C D E FA - 1 2 3 4 5B 1 - 3 4 5 2C 2 3 - 5 1 4D 3 4 6 - 2 1E 4 5 1 2 - 3F 5 2 4 1 3 -

Formiamo i turni assumendo come primo giocatore il giocatore RIG nei turni dispari e quello COLONNA nei turni pari:

I TURNO: AB, CE, DFII TURNO: CA, ED, FBIII TURNO: AD, BC, EFIV TURNO: DB, EA, FCV TURNO: AF, BE, CD.

A proposito di tornei....A un torneo di scacchi partecipano 1200 giocatori, e il torneo è a eliminazione diretta (in caso di patta la vittoria viene assegnata per sorteggio). Quante partite bisogna giocare per proclamare il vincitore del torneo?

Quadrati greco-latini

Siano dati:1) un quadrato latino costruito con gli n simboli di un insieme S ;2) un quadrato latino costruito con gli n simboli di un insieme T .

Sovrapponiamo i due quadrati in modo da ottenerne uno solo, contenente in ciascuna casa una coppia (s, t ) con s∈S e t∈T .Il nuovo quadrato si dice greco-latino, se nelle sue n2 case compaiono tutte le n2 coppie del prodotto cartesiano S×T . In questo caso, i due quadrati si dicono ortogonali.Un esempio chiarirà l'idea:Si vogliono disporre i 4 Assi, i 4 Re, i 4 Cavalli e le 4 Donne di un comune mazzo di carte napoletane, in un quadrato 4 x 4, in modo che ciascuna figura e ciascun seme compaiano una sola volta in ogni riga e in ogni colonna.

109

Abbiamo: S = { A, R, C, D }; T = { b, c, d, s }; n = 41) quadrato delle figure:

A R C DD C R AR A D CC D A R

2) quadrato dei semi:d c b sb s d cs b c dc d s b

se sovrapponiamo i due quadrati, ne otteniamo uno greco-latino, perché in esso compaiono tutte le coppie di S×T .

A-d R-c C-b D-sD-b C-s R-d A-cR-s A-b D-c C-dC-c D-d A-s R-b

Per chiarire ulteriormente, mostriamo una coppia di quadrati latini che non sono ortogonali.Poniamo S= ( A, B, C); T = ( x, y, z)-quadrato di S

C A BB C AA B C

-quadrato di Tx z yy x zz y x

110

sovrapponendoli abbiamo il quadratoC-x A-z B-yB-y C-x A-zA-z B-y C-x

che non è greco-latino, perché mancano le coppie A-x, A-y, B-x, B-z, etc.Una coppia di quadrati ortogonali di ordine dispari si costruisce facilmente applicando il seguente algoritmo:

1) Si costruisce il quadrato generato da k = 1,2) Si costruisce il quadrato generato da k =2.

I due quadrati risultano ortogonali, come si vede dal seguente esempio: k = 1

2 0 11 2 00 1 2

k = 22 1 01 0 20 2 1

sovrapponendoli, si constata che generano un quadrato greco-latino

2-2 0-1 1-01-1 2-0 0-20-0 1-2 2-1

Quando n è pari il problema è più complesso, per cui ci limitiamo a fornire un esempio per n = 4:

A-1 B-2 C-3 D-4B-3 A-4 D-1 C-2C-4 D-3 A-2 B-1D-2 C-1 B-4 A-3

C'è da aggiungere che non esistono quadrati greco-latini per n = 2 e per n= 6.L'impossibilità per n = 2 è di immediata verifica, perché esistono solo due quadrati latini di ordine 2, e non sono ortogonali.Più interessante è la storia legata al valore n = 6. Eulero pose la questione in questi termini:

111

Il problema dei 36 ufficiali.Ciascuno di 6 reggimenti invia una delegazione di 6 ufficiali, che devono partecipare ad una parata militare. Ogni delegazione è costituita da un sottotenente, un tenente,un capitano, un maggiore, un colonnello e un generale. E' possibile disporre i 36 ufficiali su 6 righe e 6 colonne, in modo che in ogni riga e in ogni colonna sia rappresentato ciascun reggimento e ciascun grado?Eulero indicò i 6 reggimenti con le lettere latine a, b, c, d, e, f e i 6 gradi con le lettere greche α, β, γ, δ, ε, ζ . E' evidente che ciascun ufficiale è individuato da una coppia di lettere, una latina e l'altra greca. Il problema consiste nel costruire un quadrato greco latino e, quindi, ci sono tre condizioni da soddisfare:

1) su ogni riga devono figurare le sei lettere latine e le sei greche2) lo stesso deve avvenire su ogni colonna3) nel quadrato devono essere presenti tutte le 36 coppie possibili.

Eulero mostrò che le prime due condizioni non sono sufficienti, altrimenti sarebbe facile trovare una soluzione e, a conferma della sua affermazione, costruì il seguente schema

aα bζ cδ dε eγ fβbβ cα fε eδ aζ dγcγ dε aβ bζ fδ eαdδ fγ eζ cβ bα aεeε aδ bγ fα dβ cζfζ eβ dα aγ cε bδ

che soddisfa le prime due condizioni ma non è una soluzione, perché le coppie bζ e dε figurano due volte e mancano le coppie dζ e bε.

Egli non riuscì a risolvere il problema ed ipotizzò che fosse impossibile, avanzando la congettura secondo la quale non esistono quadrati greco-latini di ordine 6. Anzi, si spinse oltre ed affermò che è impossibile costruire quadrati greco-latini di ordine n≡2 mod4. La congettura di

112

Eulero ha resistito per quasi due secoli, ma è stata confutata (parzialmente) nel 1959 dai matematici Bose, Shrikhande e Parker, i quali hanno dimostrato che esistono quadrati greco-latini per ogni valore di n, escluso n =6.

Il guastafeste di EuleroRiportiamo, a titolo di curiosità, il quadrato greco-latino costruito dal matematico E. T. Parker, che rappresenta un controesempio sufficiente a confutare la congettura di Eulero (10 ≡ 2 mod 4 !!).

00 47 18 76 29 93 85 34 61 5286 11 57 28 70 39 94 45 02 6395 80 22 67 38 71 49 56 13 0459 96 81 33 07 48 72 60 24 1573 69 90 82 44 17 58 01 35 2668 74 09 91 83 55 27 12 46 3037 08 75 19 92 84 66 23 50 4114 25 36 40 51 62 03 77 88 9921 32 43 54 65 06 10 89 97 7842 53 64 05 16 20 31 98 79 87

113

114

V

QUADRATI MAGICI

115

Definizioni e proprietàUn quadrato magico “normale” n x n è una tabella costituita di n2 caselle, in ciascuna delle quali viene collocato un numero naturale da 1 a n2, senza ripetizioni, in modo che la somma per righe, colonne e diagonali risulti costante. Tale somma è detta costante magica (K).Determinare la costante magica di un quadrato ( normale ) di ordine n è abbastanza semplice:detta S la somma di tutti i numeri inseriti nel quadrato, risulta K=S

n

ma S=123...n2=n21

2n2

quindi K=n21

2n

Un quadrato magico di ordine n resta tale se si opera su di esso con una delle seguenti trasformazioni:– rotazione intorno al centro di ± 90°, ± 180°, ± 270°;– simmetria rispetto all'asse orizzontale o verticale;– simmetria rispetto ad una diagonale;– sostituzione di ogni numero con il suo complemento a n2+1– si aggiunge una costante ad ogni numero– si moltiplicano (dividono) tutti i numeri per una costante ( diversa da 0).

Costruiamo un quadrato magicoDopo questa breve introduzione, passiamo alla costruzione dei quadrati magici. Bisogna considerare tre ipotesi:I caso: n dispari.Realizziamo un quadrato di ordine 5, che ci servirà da modello per il caso generale:Passo 1: tracciamo il quadrato 5 x 5 e poi, al suo esterno, aggiungiamo, ad ogni lato, delle righe e delle colonne di lunghezza decrescente ( due case per volta), come mostrato in figura

116

Passo 2: inseriamo i numeri da 1 a 25 nello schema seguendo le diagonali ascendenti:

54 10

3 9 152 8 14 20

1 7 13 19 256 12 18 24

11 17 2316 22

21

Passo 3: i numeri che sono fuori dal quadrato vengono riportati all'interno con uno spostamento (verticale/orizzontale) di 5 caselle. Fine.

3 16 9 22 1520 8 21 14 27 25 13 1 1924 12 5 18 611 4 17 10 23

K = 5212

5=65

In modo analogo si procede per ogni n dispari.II caso: n doppiamente pari ( n= 4k).

117

Anche questo caso si risolve con un algoritmo molto semplice, che illustriamo costruendo il quadrato per n = 8 (=4·2 )Passo 1: si divide il quadrato in 4 (=22) sotto-quadrati di ordine 4 e si colorano le diagonali maggiori di ciascun sotto-quadrato

Passo 2: si inseriscono nel quadrato i numeri da 1 a 64, iniziando dalla prima casella a sinistra della prima riga in alto, e continuando nel modo più spontaneo...

1 2 3 4 5 6 7 89 10 11 12 13 14 15 1617 18 19 20 21 22 23 2425 26 27 28 29 30 31 3233 34 35 36 37 38 39 4041 42 43 44 45 46 47 4849 50 51 52 53 54 55 5657 58 59 60 61 62 63 64

Passo 3: ogni numero che occupa una casa colorata si scambia di posto con il suo complemento a 65 (=82+1).Fine.

64 2 3 61 60 6 7 579 55 54 12 13 51 50 1617 47 46 20 21 43 42 2440 26 27 37 36 30 31 3332 34 35 29 28 38 39 2541 23 22 44 45 19 18 4849 15 14 52 53 11 10 568 58 59 5 4 62 63 1

K= 8212

8=260

118

Anche qui non è difficile passare al caso generale.

III caso: n semplicemente pari ( n = 4k + 2 ).Costruiamo, come esempio guida, il quadrato di ordine 6.

Passo 1: dividiamo il quadrato in due parti uguali e simmetriche rispetto all'asse verticale

Passo 2: inseriamo i numeri da 1 a 6 lungo le diagonali maggiori:

1 62 5

3 43 4

2 51 6

notiamo che nella generica colonna j figura due volte il numero j.

Passo 3 (si esegue solo nella zona rossa): per ogni j ( j=1,2,3),poniamo cj=7-j , e completiamo la colonna in modo che in essa i valori j e cj

figurino un ugual numero di volte. Qui è mostrata una delle possibili soluzioni:

1 5 4 66 2 3 56 5 3 41 5 3 46 2 4 51 2 4 6

119

Passo 4: riempiamo la “zona verde”, inserendo in ogni cella vuota il complemento a 7 del numero che occupa la cella simmetrica rispetto all'asse.

1 5 4 3 2 66 2 3 4 5 16 5 3 4 2 11 5 3 4 2 66 2 4 3 5 11 2 4 3 5 6

Chiamiamo M la matrice così ottenuta.

Passo 5: costruiamo la sua trasposta, MT:

1 6 6 1 6 15 2 5 5 2 24 3 3 3 4 43 4 4 4 3 32 5 2 2 5 56 1 1 6 1 6

e indichiamo con ti,j il generico elemento di M T.

Passo 6: costruiamo la matrice Q, il cui elemento generico qi,j è così definito: qi,j= 6(ti,j-1)

0 30 30 0 30 024 6 24 24 6 618 12 12 12 18 1812 18 18 18 12 126 24 6 6 24 2430 0 0 30 0 30

Passo 7: il quadrato cercato è dato dalla matrice M+Q

120

1 35 34 3 32 630 8 27 28 11 724 17 15 16 20 1913 23 21 22 14 1812 26 10 9 29 2531 2 4 33 5 36

K = 6212

6=111

Non solo matematica...Il primo quadrato magico di cui si abbia notizia proviene dalla Cina, e risale a circa 2000 anni prima di Cristo: la leggenda narra di una tartaruga sul cui guscio erano impressi dei segni che rappresentavano i primi nove numeri disposti in tre righe e tre colonne, in modo che la somma per righe, colonne e diagonali era sempre 15 .Tale quadrato, conosciuto come Lo Shu, diventò un simbolo sacro per la Cina, rappresentazione dei più arcani misteri dell'Universo.

4 9 23 5 78 1 6

Probabilmente, i quadrati magici giunsero in Occidente attraverso gli Arabi, e dal Rinascimento in poi, c'è stato un grande interesse per queste figure, che erano circondate da un alone di mistero e di magia.A testimonianza del valore simbolico attribuito a tali quadrati, ne riproduciamo due molto noti, perché rappresentati in famose opere d'arte:

– il quadrato raffigurato nell'incisione Malinconia,eseguita nel 1514dal pittore tedesco Albrecht Dürer (1471 – 1528).

16 3 2 135 10 11 89 6 7 124 15 14 1

121

La tecnica di costruzione è quella spiegata in precedenza, ma il pittore ha scambiato le colonne interne per fare in modo che le case centrali della riga inferiore indicassero l'anno in cui è stata eseguita l'incisione..

– il quadrato scolpito sulla facciata della Sagrada Familia (Barcellona), opera dell'architetto Antoni Gaudi (1852 - 1926).

1 14 14 411 7 6 98 10 10 513 2 3 15

Il quadrato, attribuito all'architetto Subirach, non è normale, perché non vi figurano tutti i numeri da 1 a 16. Inoltre, la costante magica non è 34 (tipica del quarto ordine ) ma 33, alludendo, probabilmente, all'età di Gesù al momento della morte. In entrambi i quadrati è possibile individuare numerosi gruppi di 4 case, situate in posizioni simmetriche rispetto al centro, o a un asse, o a una diagonale, che danno come totale la costante magica. Lasciamo al lettore il piacere di individuarli. I due quadrati si somigliano come due gocce d'acqua, il che non è casuale. Il quadrato di Subirach, infatti, si ottiene da quello di Dürer con una rotazione di 180 gradi e qualche piccola modifica per avere come costante magica il numero 33.

122

Il magico EuleroAbbiamo imparato a costruire i quadrati magici applicando dei semplici algoritmi, ma è estremamente interessante ed istruttivo costruirli seguendo il metodo di Leonardo il Grande. Eulero parte dall'osservazione che i numeri da 1 a n2 possono essere rappresentati nella forma nh + k.Infatti, se si assegnano ad h i valori da 0 a n-1, e a k i valori da 1 a n, si ottengono tutti i numeri da 1 a n 2 semplicemente associando ogni valore di h con ogni valore di k, come mostrato nella seguente tabella:

kh

1 2 3 ................ n

0 1 2 3 .................. n1 n+1 n+2 n+3 ................... 2n2 2n+1 2n+2 2n+3 ................... 3n........... ............. ............ .............. ..............n-1 n2-n+1 n2-n+2 n2-n+3 ............. n2

Poiché i numeri da 1 a n2 possono essere scritti nella forma nh+k, e quindi rappresentati come somma di due addendi, indicheremo il primo, nh, con le lettere latine a,b,c,d,etc., e il secondo con le lettere greche α, β, γ, δ, etc..E' chiaro che saranno necessarie n lettere latine e n lettere greche, perché le latine possono assumere i valori 0n, 1n, 2n,....,(n-1)n e le greche i valori 1, 2, 3, ...., n. E' bene notare che non è fissato nessun ordine né tra le lettere latine né tra le greche, per cui ciascuna lettera latina può assumere sia il valore 0n, sia 1n, sia 2n etc., purché si assegnino valori diversi alle n lettere; e questo vale anche per le lettere greche. Un numero da 1 a n 2 si può scrivere, quindi, come somma tra una lettera latina e una greca: a+γ, a+β, b+α, etc. Per comodità, indichiamo la somma fra due lettere mediante il loro semplice accostamento, ovvero scriviamo aγ invece di a+γ, aβ invece di a+β, bα invece di b+α, e così via. Applichiamo il metodo ai casi n = 3 e n = 4.n = 3 Un quadrato del terzo ordine contiene i numeri da 1 a 9 , i quali si possono scrivere nella forma

3h+ k h=(0, 1, 2); k= (1, 2, 3 )

123

ovvero, si possono scrivere come somma di due addendi : (3h) e (k), che considereremo sempre in questo ordine.Usiamo le lettere latine a, b, c per indicare il primo addendo e quelle greche α, β, γ per indicare il secondo. Il primo addendo può assumere i valori 0, 3, 6 e il secondo i valori 1, 2, 3. Ribadiamo che non è fissato nessun ordine, nel senso che ciascuna lettera latina può assumere i valori 0, 3, 6 ma le tre lettere devono assumere valori diversi; lo stesso vale per quelle greche.Costruiamo un quadrato latino usando le lettere a, b, c

a b cb c ac a b

e osserviamo che in una diagonale figurano tutte e tre le lettere, mentre nell'altra figura tre volte la stessa lettera ( è inevitabile, per n = 3).Poiché a+b+c = 9, se vogliamo che il quadrato sia magico deve essere c=3.Costruiamo, ora, un quadrato latino (ortogonale con il precedente) con le lettere α, β, γ

γ β αα γ ββ α γ

Poiché α+β+γ = 6, per avere un quadrato magico deve essere γ = 2.Combiniamo i due quadrati per formarne uno greco-latino

aγ bβ cαbα cγ aβcβ aα bγ

In cui sappiamo che c = 3 e γ = 2 e che alle lettere a e b possono essere assegnati i valori 0 e 6, mentre alle lettere α e β possono essere assegnati i valori 1 e 3. Se scegliamo a = 0, b = 6, α = 1 e β = 3 otteniamo il seguente quadrato magico:

124

2 9 47 5 36 1 8

n = 4 I numeri da 1 a 16 si possono scrivere nella forma 4h+ k h = ( 0, 1, 2, 3) k = ( 1, 2, 3, 4 ).Usiamo le lettere latine a, b, c, d per indicare il primo addendo e quelle greche α, β, γ, δ per indicare il secondo. Il primo addendo può assumere i valori 0, 4, 8, 12 e il secondo i valori 1, 2, 3, 4.Con le lettere a, b, c, d costruiamo un quadrato latino che abbia l' ulteriore proprietà di presentare tutte le lettere anche sulle due diagonali ( quadrato latino diagonale). Per fare ciò basta scrivere le lettere in ordine alfabetico sulla prima riga e scegliere una lettera, tra la c e la d, da porre nella seconda casa della diagonale principale. In questo esempio scegliamo la c e otteniamo il seguente schema:

a b c dc

dal quale risulta evidente che il quadrato è completamente determinato.a b c dd c b ab a d cc d a b

Ora dobbiamo collocare nelle celle le lettere greche, in modo da ottenere un quadrato greco-latino. Un metodo efficiente è il seguente:

– si colloca in ogni casa la lettera greca equivalente a quella latina che occupa la casa ( aα, bβ, etc.)

– si scambiano di posto le lettere greche che occupano case simmetriche rispetto alla diagonale principale.

Operando in tal modo, otteniamo il seguente quadrato:

125

aα bδ cβ dγdβ cγ bα aδbγ aβ dδ cαcδ dα aγ bβ

notiamo che anche le lettere greche formano un quadrato latino diagonale.Dato che le lettere latine e quelle greche figurano tutte una sola volta in ogni riga, in ogni colonna e in entrambe le diagonali, non abbiamo nessun vincolo da rispettare circa il valore da assegnare alle lettere, le quali, quindi, possono assumere uno qualsiasi dei valori ammissibili per generare un quadrato magico. Ponendo, ad esempio,a = 0,b = 4, c = 8, d = 12, α = 1, β = 3, γ = 2, δ = 4, si ottiene il quadrato

1 8 11 1415 10 5 46 3 16 912 13 2 7

l' esempio evidenzia lo stretto rapporto tra i quadrati di Eulero e i quadrati magici. Per chiarire ulteriormente la logica su cui poggia il metodo di Eulero, consideriamo un quadrato greco-latino del quarto ordine costruito con i “simboli” 0, 1, 2, 3, (che sono le cifre consentite in un sistema di numerazione in base 4)

1-1 0-3 2-0 3-23-0 2-2 0-1 1-30-2 1-0 3-3 2-12-3 3-1 1-2 0-0

interpretiamo la coppia di numeri che figura in ogni casa, come un numero scritto in base 4, e trasformiamolo in base 10:114 = 5, 034 = 3, 204 = 8, 324 = 14, 304 = 12, etc.Se riscriviamo il quadrato, sostituendo in ogni casa il corrispondente numero in base 10 , otteniamo il seguente quadrato magico non normale

126

5 3 8 1412 10 1 7 2 4 15 911 13 6 0

il quale, però, si “normalizza” facilmente aggiungendo 1 ad ogni suo elemento....

127

128

APPENDICI

129

130

APPENDICE ALe funzioni floor e ceiling.

floor(x) è il massimo intero ≤ x

ceiling(x) è il minimo intero ≥ x

se x è intero, floor(x) = ceiling(x) = x

Esempio: floor(3.5) = 3; ceiling(3.5) = 4; floor(6) = ceiling(6) = 6

Fattoriale di un naturale n: n!

n! = 1∙2∙3∙...∙n per convenzione: 0! = 1 Esempio: 5! = 1∙2∙3∙4∙5 = 120

Disposizioni semplici: Dn,k k ≤ n

Dn,k conta il numero di raggruppamenti di k elementi scelti da un insieme di n elementi, con l'intesa che un raggruppamento differisca dagli altri per almeno un elemento, o per l'ordine.

Dn,k = n !

n−k !

Esempio: Quanti sono i numeri di 4 cifre, tutte diverse, che non contengano né lo 0 né il 6 ?Si tratta di calcolare il numero delle disposizioni ( e non le combinazioni perché il numero cambia di valore mutando l'ordine delle cifre) di 8 cifre prese 4 a 4: D8,4 = 8∙7∙6∙5 = 1680

131

Permutazioni semplici: Pn.

Pn conta il numero dei raggruppamenti formati da n elementi distinti presi in un ordine qualsiasi ( anagrammi di parole costituite da lettere tutte diverse, per esempio).

Pn = n!

Esempio: Quanti sono gli anagrammi della parola ROMA? Abbiamo n = 4, quindi gli anagrammi sono P4 = 4! = 1∙2∙3∙4= 24

Osservazione importante: Permutare n elementi equivale a disporre n Torri su una scacchiera n x n, in modo che in ogni colonna e in ogni traversa ci sia esattamente una Torre. Consideriamo, come esempio, le permutazioni degli elementi ( a, b, c ): abc

c Tb Ta T

1 2 3

acbc Tb Ta T

1 2 3

cabc Tb Ta T

1 2 3

132

bacc Tb Ta T

1 2 3

bcac Tb Ta T

1 2 3

cbac Tb Ta T

1 2 3

Permutazioni con elementi ripetuti: Pna,b,c,...

Pna,b,c,... conta il numero di raggruppamenti formati da n elementi di cui

a uguali fra loro, b uguali fra loro, c uguali fra loro ecc..., presi in un ordine qualsiasi (anagrammi di parole contenenti alcune lettere ripetute, per esempio).

Pna,b,c,... =

n!a !⋅b!⋅c ! ...

Esempio: Quanti sono gli anagrammi distinti della parola MAMMA? Abbiamo n = 5, a = 2, b = 3, quindi gli anagrammi distinti sono P5

2,3= 5 !2 !⋅3!

=10

133

Combinazioni semplici: nk

n

k conta il numero di raggruppamenti di k elementi scelti da un insieme di n elementi, con l'intesa che ogni raggruppamento differisca dagli altri per almeno un elemento (senza considerare l'ordine degli elementi).

Esempio: Quanti ambi si possono formare con i 90 numeri del lotto?

902 = 90 !

2 !⋅88 !=4005

l'operatore modulo: modSe a è un intero e n è un intero positivo, si definisce a mod n come il resto della divisione di a per n.

Esempi: 7mod2=1, 11mod7=4, 37mod5=2, 4mod11=4

Due interi a e b sono detti congruenti modulo n se a mod n = b mod n.In parole semplici, se a e b , divisi per n, danno lo stesso resto.Per indicare che a e b sono congruenti si scrive a≡b .

Esempi: 7≡51 mod 2,23≡5 mod 3,40≡12 mod 4

134

APPENDICE B

Un grafo non orientato G è costituito da una coppia ordinata ( V, A) dove V è un insieme finito (non vuoto) di elementi chiamati vertici o nodi e A è un insieme finito di archi. Un arco è una coppia non ordinata di due nodi.Nella figura seguente, i punti A, B, C, D, E sono i nodi, e i segmenti che li congiungono sono detti archi ( o spigoli o lati )

Le definizioni che seguono sono del tutto intuitive. -Estremi di un arco (i,j) sono i due nodi i e j collegati dall'arco. L'arco si dice incidente nei nodi i e j.

-Vertici adiacenti si dice di 2 vertici i e j se sono collegati da un arco.

135

- Cammino è una sequenza di archi tali che, a eccezione del primo e dell'ultimo di essi, il nodo finale di ogni arco coincide con quello iniziale del successivo.

Un grafo non orientato è connesso se, per ogni coppia di nodi, esiste un cammino che li connette.

Ciclo o circuito è un cammino chiuso, cioè un cammino in cui il vertice iniziale e quello finale coincidono.

136

Un ciclo si dice euleriano se utilizza tutti gli archi esattamente una volta.

Un ciclo si dice hamiltoniano se passa attraverso ogni vertice del grafo esattamente una volta.

Un ciclo si dice pari, se è costituito da un numero pari di archi.

-Albero è un grafo connesso e privo di cicli.

-Grado di un nodo è il numero di archi incidenti nel nodo.

137

-Grafo bipartito è un grafo in cui l'insieme dei nodi è partizionato in 2 sottoinsiemi V1 e V2 tali che esistano archi solo tra nodi di V1 e nodi di V2.

138

Teorema n.1In un grafo connesso esiste un ciclo euleriano se tutti i nodi hanno grado pari. Vale l'inverso.

Teorema n.2Se in un grafo connesso esistono esattamente 2 vertici di grado dispari, il grafo contiene una cammino euleriano che inizia in uno dei vertici e termina nell'altro. Vale l'inverso.

Teorema n.3In un grafo bipartito esistono solo cicli pari. Vale l'inverso.

139

140

BIBLIOGRAFIA

● P. Gritzman, R. Brandenberg - Alla ricerca della via più breve● L. Barzanti e S. Fabbri -Gli scacchi come strumento per la

didattica della matematica● Cerasoli, Eugeni, Protasi - Matematica discreta● John J. Watkins -Across the board● S. I. Gelfand - Sequences, Combinations, Limits● Martin Gardner - Enigmi e Giochi Matematici● R. Lucchetti - Di duelli, scacchi e dilemmi● E. Paoli - Il finale negli scacchi● B. Rosen - Chess Endgame Training● A. Colorni - Ricerca operativa ● T, Beardon - A Knight's Journey● L. Eulero - De quadratis magicis ● U. Russo - La matematica e la conoscenza

dell'universo● I. Ghersi - Matematica dilettevole e curiosa

141

142

INDICE

Prefazione 3LA SCACCHIERA

Coordinate 7Distanze 8Ordine 10Scacchiera+pezzo=grafo 11Problema n.1 (leggenda di Sissa) 13Problema n.2 14Problema n.3 15Problema n.4 (la scacchiera mutilata) 16Problema n.5 (il tappeto di Sierpinski) 19Problema n.6 (minimo attacco) 21Problema n.7 (massimo attacco) 22Problema n.8 (colorazioni della scacchiera) 23Quante caselle ci sono sulla scacchiera? 26

I PEZZIMosse-spostamenti 31Mobilità di un pezzo 32Descrivere una posizione 33Il Re 35Problema n. 9 (passeggiata del Re-I) 38Problema n. 10 (passeggiata del Re-II) 39Problema n, 11 (passeggiata del Re-III) 42Problema n. 12 43Problema n. 13 44La Donna 47Problema n. 14 48Costruire una soluzione 53Problema n. 15 55La Torre 57Problema n. 16 57Problema n. 17 60L'Alfiere 63Problema n. 18 64Problema n. 19 66Il Cavallo 69

143

Problema n. 20 70Problema n. 21 72Problema n. 22 79Problema n. 23 ( ciclo euleriano) 81Problema n. 24 ( ciclo hamiltoniano) 82Ciclo pitagorico 84Problema n. 25 (Guarini) 86Pegaso 88Eadem mutata resurgo 92Il Pedone 95Due pedoni...ed un quadrato 95

L'ALBERO DEGLI SCACCHI Il teorema di Zermelo 100

.

QUADRATI DI EULEROQuadrati latini 105Scheduling 106A proposito di tornei.. 109Quadrati greco-latini 109Il problema dei 36 ufficiali 112Il guastafeste di Eulero 113

QUADRATI MAGICI Definizioni e proprietà 116Costruiamo un quadrato magico 114Non solo matematica 121Il magico Eulero 123

APPENDICIAPPENDICE A 131APPENDICE B 135

144

145