Newsgroup: it.hobby.enigmi
Titolo: Le 8 Regine

Questo č un prova che hanno proposto a scuola a mio figlio (11 anni).
Mi sembra carina.
Ve la propongo.
"Provate a disporre 8 Regine su una scacchiera in modo che nessuna possa
catturare o essere catturata da un'altra".
P.S. Io non sono riuscito a trovare la soluzione, anzi mi pareva che non
     fosse possibile disporre in tale modo piů di 7 Regine; mio figlio
     perň  ce l'ha fatta!

 catturare o essere catturata da un'altra".
Prova queste posizioni:
A6 B3 C1 D8 E5 F2 G4 D7
É un quesito non male, si dovrebbe risolvere in 5-10 minuti di tentativi...
Però se tuo figlio ha 11 anni fagli i complimenti!
MaxArt

      però  ce l'ha fatta!
E' un problema molto vecchio, ma di non facilissima soluzione.
Complimenti a tuo figlio.
Ecco, comunque, la soluzione
V
V
V
V
V
V
V
V
V
V
V
V
V
V
V
V
V
V
V
V
V
V
V
V
V
V
V
V
V
A7, B3, C8, D2, E5, F1, G6, H4.

 Ecco, comunque, la soluzione
UNA soluzione, vorrai dire ;-)
Domandina: a parte rotazioni varie, quante soluzioni ci sono?
MaxArt

 P.S. Io non sono riuscito a trovare la soluzione, anzi mi pareva che non


delle regine: quanti quadrati ci sono ina scacchiera 8x8?
Dovrebbero essere 204
Ciascun quadrato puo' essere definito indicando:
-casella di partenza (per esempio quella in alto a sinistra)
-lunghezza del lato (come numero di caselle)
se la casella di partenza appartiene all'ultima riga O
all'ultima colonna (15 casi) sono possibili solo quadrati di
lato 1;
se la casella di partenza appartiene alla penultima riga O
alla penultima colonna (13 nuovi casi) sono possibili solo
quadrati di lato 1 o 2;
...
per finire, se la casella di prtenza appartiene alla prima
riga E alla prima colonna (1 caso), sono possibili 8
quadrati, di lati da 1 ad 8.
quindi
15*1 + 13*2 + 11*3 + 9*4 + 7*5 +5*6 + 3*7 + 1*8=
=204
ciao
paolo

> Dovrebbero essere 204
Giusto, bravo Paolo :-)
Ciao
Giulio

 -lunghezza del lato (come numero di caselle)
Mi sembra molto piu' semplice vederla cosi':
I quadrati di lato 1 sono 8*8.
Un quadrato di lato 2 assume 7 posizioni lungo un lato, quindi sono 7*7.
Un quadrato di lato 3   "    6   "                        "         6*6.
Un quadrato di lato 4   "    5   "                        "         5*5.
ecc ...................
Fino al quadrato di lato 8 = 1*1.
In generale per una scacchiera di lato n la sol e' data dalla somma dei
quadrati degli interi da 1 fino ad n=
che e' = n(n+1)(2n+1)/6.
Se invece di una scacchiera consideriamo una matrice di 8*8 formata dai
punti che identificano gli interi in un piano cartesiano,
determinare quanti siano i quadrati con i vertici in corrispondenza di
tali punti, mi sembra piu' arduo, bisogna considerare anche quelli non
ortogonali.
:) dario

 Domandina: a parte rotazioni varie, quante soluzioni ci sono?
E' un problema notissimo, fu proposto per la prima volta
da un tale Bezzel nel 1848, se ne interesso' perfino il grande Gauss.
Ecco il numero di sol. computate per i vari ordini (lato della
scacchiera)
non considerando rotazioni e riflessioni:
ordine       num. di soluzioni
 4              1
 5              2
 6              1
 7              6
 8             12
 9             46
10             92
11            341
12           1787
13           9233
14          45752
15         285053
16        1846955
17       11977939                       
Piu' complesso lo stesso problema, ma con amazzoni al posto di regine.
L'amazzone e' un pezzo che puo' muovere  come una regina ed un cavallo
contemporaneamente.
Il conto delle soluzioni e':
10   1
11   6
12   22
13   239
14   653
15   4089
16   25411
17   166463
18   1115871
19   8062150
20   61984976
:) dario

 x*(n-x+1)^2 = 1/12*n*(n+1)^2*(n+2)
--
x=1,n
Nel nostro caso fa 540
Ciao, Silv:o)

 Nel nostro caso fa 540
Esatto, volevo procedere per gradi. Ecco alcune generalizzazioni in
ordine crescente di difficolta' :
Quanti sono i rettangoli ortogonali in una scacchiera n*n?
Quanti sono i rettangoli in totale  in una scacchioera n*n?
Stesso problema, ma su una scacchiera m*n.
Buon lavoro (anche a me)
:) dario

Stesso problema, ma su una scacchiera m*n.
Per ora mi limito ai rettangoli ortogonali nella scacchiera
n*m
(per intenderci, sto considerando n*m punti, quindi la
normale scachiera 8*8 caselle sarebbe 9*9 punti)
Per individuare un generico rettangolo, considero una coppia
di punti (P,Q) non allineati in orizzontale ne' in
verticale, che formeranno una diagonale del rettangolo.
Il punto P puo' essere scelto in n*m modi differenti, il
punto Q, per rispettare la condizione di non allineamento,
in (n-1)*(m-1) modi, quindi in totale :
n*(n-1)*m*(m-1) coppie;
Ora devo dividere il prodotto per quattro, infatti...il
rettangolo ha quattro diagonali(???:-);
cioe' per un generico rettangolo ABCD, il calcolo precedente
ha conteggiato le coppie
AC, CA, BD, DB.
quindi
n*(n-1)*m*(m-1)/4
(ovviamente, tra i rettangoli sono stati calcolati anche
tutti i possibili quadrati; se volessimo escluderli basta
calcolarli a parte e sottrarre)
ciao
paolo

 n*(n-1)*m*(m-1)/4
Caspita ! Paolo che soluzione brillante !
Complimenti davvero.
:) dario

Complimenti davvero.
Grazie per i complimenti, ma in fondo non era poi tanto
difficile.
L'uso di definire un rettangolo mediante le coordinate di
due punti, estremi di una diagonale, e' piuttosto comune in
alcuni programmmi di grafica.
Tornando all'espressione proposta,
n*(n-1)*m*(m-1)/4
forse e' piu' agevole scrivere
N*(N+1)*M*(M+1)/4
con N=n-1 ed M=m-1
dove N,M sono le dimensioni della scacchiera espresse in
numero di caselle (non in numero di punti).
Ci si poteva arrivare in un modo, forse piu' immediato,
analogo a quello proposto da te per i quadrati:
Un rettangolo ortogonale e' definito dall'intersezione di
una fascia orizzontale con una verticale.
le possibili fasce verticali sono:
1 di larghezza M
2 di larghezza M-1
...
M di larghezza 1
quindi in totale 1+2+...M=M*(M+1)/2
Analogamente le fasce orizzontali sono N*(N+1)/2
da cui il totale
N*(N+1)*M*(M+1)/4 rettangoli
Il problema dei rettangoli obliqui mi sembra invece
veramente tosto.
Un'idea di partenza (non so se suscettibile di sviluppi)
potrebbe essere questa:
Come ha detto Silvio per i quadrati,anche i rettangoli
obliqui possono essere *imbrigliati* in quelli ortogonali.
Considerato un generico rettangolo ortogonale di lati interi
p*q, in esso possono essere inscritti
(p-1)*(q-1) parallelogrammi, aventi un vertice( di
coordinate intere) in ciascuno dei lati del rettangolo .
Qualcuno riesce a trovare una formula *utilizzabile* per
verificare quanti dei parallelogrammi siano rettangoli?
ciao
paolo

verificare quanti dei parallelogrammi siano rettangoli?
Se devi solo verificare, la condizione e':
   +------p------+
   |_____________|___
   | / '-._      | |
___|/      '-._  | |
 | |'-._       '-| q
 y |    '-._    /| |
_|_|________'-./_|_|_
   |           |
   +-----x-----+
x/y=(q-y)/(p-x) ovvero x*(q-y)=y*(p-x)
==========
Io propongo un approccio diverso:
Dato un qualsiasi rettangolo obliquo, definiamo *base* il lato che unisce
il vertice di ordinata minima (y0) col vertice di ascissa minima (x0).
Gli estremi della base avranno coordinate (x0,y0+y) e (x0+x,y0). D'ora in
poi chiamero'
b(x0,y0,x,y) una tale base.
Se M e' il MCD di x e y, allora posso aggiungere strisce da M quadrati
costruite sulla base, ottenendo tutti rettangoli possibili a vertici interi.
Per aggiungere una striscia ho bisogno di x/M caselle in altezza e y/M in
larghezza, quindi ne posso aggiungere finche' non mi trovo fuori dal
rettangolo in altezza o larghezza. Quante strisce posso aggiungere?
+---------m----------+
|                    |
|                    |
|            .'\     |
|         .'\   \    |
|      .'\   \.' \   |
|     \   \.' \   \  n
|     |\.' \   \.'   |
|    y| \   \.'      |
y0____|__\.'         |
|     | x            |
+-----|--------------+
      x0
Secondo me, sono il minimo tra int((n-x0-x)/(y/M)) e int((m-y0-y)/(x/M)).
Calcolando R per tutte le possibili basi dovremmo trovarci il numero totale
di rettangoli obliqui.
Ho realizzato un programma che mi calcola R(x,y). Ecco i risultati. A prima
vista mi sembrano molto interessanti. Guardate per esempio le differenze tra
i termini di due righe o colonne successive. Sempre che i numeri siano
esatti, a mano ho controllato fino al 5*5 ;)
 \ m  2    3    4    5    6    7    8    9   10
n \ ____________________________________________
 2 |  1    2    3    4    5    6    7    8    9
 3 |  2    8   14   20   26   32   38   44   50
 4 |  3   14   30   48   66   84  102  120  138
 5 |  4   20   48   88  128  172  216  260  304
 6 |  5   26   66  128  199  278  357  440  525
 7 |  6   32   84  172  278  408  542  684  830
 8 |  7   38  102  216  357  542  748  966 1192
 9 |  8   44  120  260  440  684  966 1280 1606
10 |  9   50  138  304  525  830 1192 1606 2053
11 | 10   56  156  348  610  980 1426 1948 2528
12 | 11   62  174  392  695 1130 1660 2294 3011
13 | 12   68  192  436  780 1284 1906 2660 3522
14 | 13   74  210  480  865 1438 2152 3026 4037
15 | 14   80  228  524  950 1592 2398 3396 4560
16 | 15   86  246  568 1035 1746 2648 3774 5095
17 | 16   92  264  612 1120 1900 2900 4156 5640
18 | 17   98  282  656 1205 2054 3152 4538 6185
19 | 18  104  300  700 1290 2208 3404 4924 6738
20 | 19  110  318  744 1375 2362 3656 5310 7291
Ciao, Silv:o)

 Io propongo un approccio diverso:
Devo essere stato preso da un attacco di complicatio tremens.
La procedura che ho utilizzato, basata sulla scansione delle possibili basi
e sulla valutazione dei rettangoli che ci posso costruire sopra e'
decisamente piu' complessa di quella proposta da Paolo, basata
sull'esplorazione di tutti i parallelogrammi inscritti nei rettangoli
ortogonali. Mi conforta il fatto che i risultati coincidono ;)
Con riferimento alla figura, che rappresenta un generico rettangolo
ortogonale p*q contenuto nell'n*m, la nuova procedura per contare i
rettangoli obliqui contenuti in un rettangolo n*m funziona cosi':
   +------p------+
   |_____________|___
   | / '-._      | |
___|/      '-._  | |
 | |'-._       '-| q
 y |    '-._    /| |
_|_|________'-./_|_|_
   |           |
   +-----x-----+
Per ogni possibile rettangolo (p=1,..,m , q=1,..,n)
* Controlla tra tutti i parallelogrammi (x=1,..,p-1 , y=1,..,q-1)
  quanti sono i rettangoli (quelli che hanno x*(q-y)=y*(p-x))
* moltiplica per i rettangoli p*q possibili (sono (m-p+1)*(n-q+1))
* somma i parziali
Con quatro cicli, un controllo ed un paio di somme me la cavo, senza MCD e
amenita' varie.
Ciao, Silv:o)