OliForum Matematico

Si consideri una scacchiera 8x8. Trovare il numero di possibili posizioni che possono assumere 8 torri, badando che la diagonale bianca non sia occupata da torri. (La forza bruta non e\' consigliabile, il numero e\' prossimo alle 15000 posizioni)

siccome non hai specificato che non si debbano minacciare...
 comb(56,<IMG SRC="images/forum/icons/icon_cool.gif">, ma viene leggermente maggiore (1.420.494.075)...
 intendevi forse a meno di rotazioni e simmetrie?
 o intendevi senza minacciarsi a vicenda?

OK , allora le torri non devono micacciarsi vicendevolmente. <IMG SRC="images/forum/icons/icon_frown.gif">

Dunque, ci sarà una ed una sola torre per ogni riga e colonna (altrimenti ce ne saranno 2 sulla stesso riga o colonna minacciandosi).
 
 Le pos. saranno 8*7*6*5*4*3*2*1 [ Questo Messaggio è stato Modificato da: bh3u4m il 17-02-2004 16:41 ]

Ma per diagonale bianca che intendi?

Che la diagonale principale (angolo NW-SE) deve avere tutte le caselle libere.

Che la diagonale principale (angolo NW-SE) deve avere tutte le caselle libere.
 Quindi la tua soluzione e\' incompleta.

Sia n un intero positivo. Definiamo le seguenti regole di posizionamento:
 
 Regola P: supponiamo di voler disporre n torri numerate da 1 ad n (nominalmente, T1, T2, ..., Tn) su una scacchiera quadrata di n*n caselle, di modo tale che due torri non occupino mai la stessa riga o la medesima colonna.
 
 Si dimostra che il numero P(n) delle configurazioni complessivamente rispondenti alla regola P, così come peraltro già osservato da bh3u4m, è pari ad n!.
 
 Regola Q: ammettiamo adesso di voler disporre n torri su una scacchiera quadrata di n*n caselle, di modo tale che due torri non occupino mai la stessa riga o la medesima colonna e nessuna fra esse si trovi comunque su una casella della diagonale principale.
 
 Diciamo Q(n) il numero complessivo delle configurazioni soddisfacenti alla regola Q (il caso n = 8 corrisponde alla soluzione del quesito di Catraga) e D(n) il numero di configurazini per le quali una almeno fra le n torri T1, T2, ..., Tn trasgredisce invece la regola Q, occupando la diagonale principale della scacchiera, fermo restando tuttavia il vincolo imposto dalla regola P. Evidentemente, D(n) si ottiene sommando, su tutti i k = 1, 2, ..., n, il numero
 Dn(k) di disposizioni in cui k delle n torri stanno sulla diagonale principale della scacchiera n*n secondo la regola P e le restanti n-k stanno disposte secondo la regola Q su una scacchiera quadrata di dimensioni (n-k)*(n-k)! Considerando che: Q(1) = 0 e Q(2) = 1, se ne può dedurre pertanto (supposto n > 2) che:
 
 Q(n) = P(n) - D(n) = n! - sum[k=1...n-2] Dn(k) =
 = n! - 1 - sum[k=1...n-2] Bin(n,k)*Q(n-k)
 
 ove la relazione D(n) = 1 + sum[k=1...n-2] Bin(n,k)*Q(n-k) si ottiene considerando che Dn(n) = 1; Q(1) = 0 e che inoltre il numero di modi diversi di disporre (indipendentemente dall\'ordine) k fra le n torri T1, T2, ..., Tn, con k = 1, 2, ..., n, su altrettante caselle distinte della diagonale principale del piano da gioco è pari al numero delle combinazioni semplici di n oggetti presi a k a k, ossia al binomiale Bin(n,k) di ordini n e k. A questo punto, tuttavia, ch\'io mi metta a far conti potete soltanto sognarvelo... anche perché sarei curioso di sentire se, prima, LB ci ha qualcosa da aggiungere, quel caro ragazzo... come farei sanza di lui, che si dà tanta premura di corregger li miei orrori... <IMG SRC="images/forum/icons/icon_wink.gif"> [ Questo Messaggio è stato Modificato da: euler_25 il 21-02-2004 21:10 ]

...nel frattempo, dacché siamo in tema, mi permetto di approfittare del 3d di Catraga per proporre qualche altro problema riguardante la scacchiera:
 
 Problema i): dimostrare che n torri (con n intero positivo) possono disporsi su una scacchiera quadrata di dimensioni n*n in n! modi diversi, cosicché due torri non occupino mai la stessa riga o la medesima colonna.
 
 Problema ii): definire un opportuno morfismo che dimostri come sia possibile ridurre il problema di posizionare un certo numero k massimale di alfieri su una scacchiera quadrata di dimensione n*n, di modo che due alfieri comunque scelti non si minaccino mai l\'uno con l\'altro (indipendentemente dal loro colore), al problema di disporre piuttosto m torri sopra una scacchiera quadrata di dimensioni oppportune m*m, di modo che due torri non risultino mai occupare la stessa riga o la medesima colonna (k, n ed m sono, ovviamente, degli interi positivi).
 
 Problema iii): determinare il numero complessivo delle configurazioni con cui è possibile disporre k regine su una scacchiera quadrata di dimensioni n*n di modo tale che due regine comunque scelte, indipendentemente dai loro colori, non si minaccino mai l\'una con l\'altra (n e k s\'intendono essere, ovviamente, due interi positivi).
 
 Problema iv) : determinare il numero minimo di mosse necessarie affinché un cavallo disposto a un angolo d\'una scacchiera quadrata di dimensione 8*8 riesca a passare, un salto dopo l\'altro, su ciascuna delle 64 caselle costituenti il piano di gioco. E\' possibile fornire una regola che esprima la soluzione a questo medesimo problema in relazione al caso più generale di una scacchiera quadrata di dimensione n*n, con n intero > 4?
 
 NOTA: inutile nascondere che l\'ultimo problema è decisamente tosto!!!

problema iv: la superficie media ricoperta dal cavallo in due mosse sono 6 quadretti, quindi in media una mossa copre 3 quadretti di scacchiera. Pertanto il numero di mosse minimo è [64/3]+(8 mod(3)) = 21 + 2 =23 mosse.
 Generalizzando a una scacchiera nxn:
 
 Numero minimo mosse = [n*n/3]+(n mod(3))
 
 Il fatto che euler garantisca che questo è un problema molto difficile mi lascia alquanto perplesso di fronte alla mia soluzione che mi sembra troppo facile e quindi probabilmente è errata, la pubblico lo stesso perchè sbagliando si impara. <IMG SRC="images/forum/icons/icon_biggrin.gif"> [ Questo Messaggio è stato Modificato da: psion_metacreativo il 22-02-2004 01:16 ]

Per il problema 1: Ogni torre dovrà occupare una colonna diversa (se non fosse così vi sarebbe un colonna con due torri che si minaccerebbero a vicenda), partendo dalla prima colonna la torre potrà occupare n posizioni.
 In ognuno di questi casi impedirà a tutte le successive torri di occupare la riga in cui è piazzata.
 Nello stesso modo la seconda torre avrà n-1 posizioni possibili per ogni posizione della prima e occupando la casella bloccherà la riga. La terza torre avrà n-2 posizioni possibili...
 Procedendo con il ragionamento si ottiene appunto n!.

Alternativa CONTRADDITORIA per il primo: Partendo da una situazione di scacchiera con lato m noto con m torri, in cui è stato verificato che il numero di posizioni possibile è pari a m!, si aumenta sia il lato sia il numero di torri a m+1.
 Ovviamente vi saranno 2m+1 caselle nuove. Supponiamo che la nuova riga e la nuova colonna create si intersechino in una casella che appartiene alla diagonale.
 Non sarà possibile disporre nella nuova colonna così creata una torre. Per farlo sarà necessario spostare una delle torri delle precedenti colonne nella nuova riga creata, liberando una riga. Ma i possibili spostamenti sono m.
 Ma allora le combinazioni sono m*m!. Come è possibile?

@PsionMetacreativo: probabilmente è colpa mia, ché non mi sono spiegato bene sì come avrei dovuto! Chiedo perdono... <IMG SRC="images/forum/icons/icon_razz.gif">
 
 In ogni caso, provvedo qui ad eliminare ogni ambiguità sulla traccia precisando che, nel computo delle mosse necessarie affinché il cavallo, un salto dopo l\'altro, \"tocchi\" ciascuna casella della scacchiera, si deve considerare che la singola mossa con cui la nostra cazzuta bestiola si porta da una prima casella generica A ad una seconda casella (non troppo) generica B del piano da giuoco determina un passaggio diretto da A a B, nel senso che, librandosi in un \"salto\" acrobatico doppio avvitato, il nostro scalcinato ronzino si sposta da A a B \"toccando\" unicamente le caselle A e B. D\'accordo? Bene, mi scuso nuovamente per l\'ambiguità! Ciao, Psion. <IMG SRC="images/forum/icons/icon_smile.gif">
 
 P.S.: il fatto ch\'io abbia dichiarato \"difficile\" il problema iv) non significa di certo che debba esserlo in assoluto! Per esempio, personalmente trovo i problemi di Geometria (cosiddetta) Elementare molto piacevoli e interessanti, ma purtroppo per me, non appena il livello sale di un epsilon rispetto agli standard, non mi ci raccapezzo più! Semplicemente non ho acquisito la forma mentis al tempo in cui di farlo ancor m\'era dato, ed ora mi sa che è un po\' tardino... ma questa è un\'altra storia! In ogni caso, fortuna ha voluto che sul forum io abbia trovato degli ottimi maestri, dai quali sto cercando pian pianino (lo dico sinceramente e con molta umiltà) di imparare, se non altro, il minimo sindacabile delle conoscenze di cui sono deficiente. Penso ad Evariste, Jack, Antimateria ed altri che qui non sto ad elencare, per non sembrar troppo affettato! Questo per sottolinearti, Psion, un fatto decisamente banale, ossia che la difficoltà estrinseca di un problema è un parametro assolutamente relativo (bell\'ossimoro, vero?); in quanto alla difficoltà intrinseca, beh... per quel che mi compete, non sono in grado di stabilirla, sicché... <IMG SRC="images/forum/icons/icon_wink.gif"> [ Questo Messaggio è stato Modificato da: euler_25 il 22-02-2004 19:32 ]

OliForum Matematico

Scacchi e combinatoria