Newsgroup: it.hobby.enigmi
Titolo: No-three-in-Line

Per gli esperti *del settore* questo quesito e' veramente datato(mi sembra
di capire che risalga a Dudeney) e penso che sia stato discusso in tutte le
salze ma, per chi, come me, non e' esperto potrebbe risultare interessante.
Si tratta di disporre 2n pedine su una scacchiera di lato n in modo tale da
NON avere tre pedine in linea retta.
N.B.: Per linea retta non si intendono solo quelle trasversali e diagonali
ma qualsiasi linea retta.
Per n=2 e' piu che banale
Per n=3 con pochi tentativi si arriva ad una soluzione
 _ _ _
|_|O|o|
|O|_|O|
|O|O|_|
Per n=4 gia comincia a complicarsi abbastanza
Chi vuole provare? Chi vuole continuare?
GaS

 di capire che risalga a Dudeney) 
E' vero.  Problema num.317 in Amusements in Mathematics, ma
Dudeney lo aveva proposto la prima volta in The Tribune (7
nov. 1906).
16 pedoni su una scacchiera 8x8.
Non mi risultano riferimanti anteriori. Sam Loyd lo
ripropone in Puzzle Magazine nel gennaio 1908 ed e' poi
riportato nella sua Cyclopedia del 1914 (edita dal figlio) a
pag.105 col titolo di Picket Post. 
ciao :) dario

 Chi vuole provare? Chi vuole continuare?
...Anche la n=4 e per n=5 e' banale perche' trovo almeno
una soluzione in pochi tentativi a mano....per il resto
credo serva qualcosa di +
;-)
.
.
m
i
n
i
.
.
.
.
.
s
p
o
i
l
e
r
.
.
.
N=4
 __ __ __ __
|  |/\|/\|  |
|--|--|--|--|
|/\|  |  |/\|
|--|--|--|--|
|/\|  |  |/\|
|--|--|--|--|
|__|/\|/\|__|
n=5
 __ __ __ __ __
|/\|  |/\|  |  |
|--|--|--|--|--|
|/\|  |  |/\|  |
|--|--|--|--|--|
|  |/\|  |/\|  |
|--|--|--|--|--|
|  |/\|  |  |/\|
|--|--|--|--|--|
|__|__|/\|__|/\|
CiaO,
Massimo

 Massimo
Scusa, hai perfettamente ragione. E' che non ho aggiunto il numero delle
soluzioni. La serie e'
1-1-4-5-11-22-57-51-????
o almeno questa riporta Martin Gardner nel suo articolo che ho sottomano,
pultroppo e' del '77 e quindi non so di sviluppi ulteriori.
Nello stesso articolo porta l'esempio di una sola configurazione per  ogni n
compreso tra 2 e 12.
Le tre soluzioni mancanti per n=4 le ho trovate(per curiosita: l'unica
riportata da M.G. e' quella che hai trovato tu) a mano
Per n=5 ne ho trovate altre 2 sempre a mano.
Per il resto, ancora, niente.
Intendevo che si complicava a trovarle tutte.
Ti consiglio di cercare una soluzione per n=8, e' fantasticamente lineare e,
almeno a posteriori, dopo averla vista, *abbastanza logica*.
GaS

"GaS" :

E' una mattinata tranquilla, fa caldo, non ho niente da fare e cosi:
Ho trovato le cinque soluzioni per n=5 !!
GaS

 pultroppo e' del '77 e quindi non so di sviluppi ulteriori.
http://www.uni-bielefeld.de/~achim/no3in/readme.html#2
ciao :) dario

 
http://www.uni-bielefeld.de/~achim/no3in/readme.html#2
....mitico !   ;-)
CiaO,
Massimo
-- 
Posted from 
net128-053.mclink.it
 [195.110.128.53] 
via Mailgate.ORG Server - 
http://www.Mailgate.ORG

GaS
wrote:

Solo un'ultima aggiunta.
Il sito da te riportato riporta il numero di
soluzioni fino ad n=13, su la "On-Line Encyclopedia of integer sequences"
riporta la seri fino ad n=15
ID Number: A000769
1,1,4,5,11,22,57,51,156,158,566,499,1366,3978,5900
http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eismum.cgi
GaS
--------------------------------
Inviato via 
http://usenet.iol.it
 

 ma qualsiasi linea retta.
Una variante: sapreste trovare la formula che esprime il numero di triplette
in linea retta per ogni n?
Ciao,
Paolo.

> e, almeno a posteriori, dopo averla vista, *abbastanza logica*.
Mi pareva di averlo affrontato, tempo fa. Fino ad n=7 trovavo facilmente
soluzioni, con un metodo abbastanza interessante ispirato da un vecchio
lavoro di Paolo (che mi ha anche fatto notare che il metodo è lontano
dall'anilzzare tutte le soluzioni). Riporto quanto dicemmo qualche mese fa
su i.s.m.
--------------------
Sono partito ovviamente dalla considerazione che ogni soluzione deve avere
due pezzi per ogni riga e colonna. Se consideriamo la prima soluzione, i
punti possono essere collegati in modo da formare un circuito unendo sempre
i due che stanno sulla stessa riga o colonna, così:
* * O-O * * *    (1,3)
* * O-+-----O    (1,5)
O-----+-----O    (7,5)
| * * | O-O *    (7,6)
O-O * | | | *    (3,6)
* O---|-+-O *    (3,7)
* * * O-O * *     ...
                 (2,2)
                 (2,3)
Se ci fai caso il circuito è completamente individuato dalle due sequenze
delle coordinate, (1,7,3,..,2) per le x e (3,5,6,..,2) per le y che non sono
altro che due permutazioni delle 7 righe e colonne. Quindi i percorsi
diversi saranno 7!*7!; anzi, se teniamo fisso la x del primo punto (da
qualche parte dovremo pur cominciare a scorrere il circuito!) si riducono a
6!*7!, tre milioni e mezzo, che non sono poi così tante. Se tieni poi conto
che il controllo sull'allineamento lo faccio *strada facendo* controllando
che i coeff. ang. dy/dx tra il punto che sto aggiungendo e quelli già
piazzati
siano diversi, vedi che molte soluzioni vengono abortite già al terzo quarto
punto.
e Paolo replicò:
Mi sembra di capire che hai considerato solo gli schemi dove i pezzi
formano UN circuito. Se è così potrebbero (forse) esistere altre
soluzioni, con i pezzi disposti a formare due o tre circuiti distinti.
Ciao, Silv:o)

 Ciao, Silv:o)
Il metodo da te descritto e' veramente interessante ma non so quante
sluzioni ricavi.
Per n=4 solo una soluzione su 4 forma un circuito, e precisamente:
 _ _ _ _
|_|o|_|o|
|o|o|_|_|
|_|_|o|o|
|o|_|o|_|
Le altre tre danno luogo a due circuiti diversi:
a](1,2)-(1,3)-(4,3)-(4,2) & (2,1)-(3,1)-(3,4)-(2,4)
b](1,2)-(1,3)-(3,3)-(3,2) & (2,1)-(2,4)-(4,4)-(4,1)
c](1,1)-(1,3)-(4,3)-(4,1) & (2,2)-(2,4)-(3,4)-(3,2)
Per n=5 tutte e 5 le soluzioni formano un circuito unico
Come ho gia accennato per n superiori ho solo una soluzione fino a n=12.
Per n=6 forma un percorso  unico.
Per n=7 forma tre circuiti.
Per n=8 l'unica soluzione che ho e' formata da 4 percorsi distinti
 _ _ _ _ _ _ _ _
|_|_|o|o|_|_|_|_|
|_|_|o|o|_|_|_|_|
|_|_|_|_|_|_|o|o|
|_|_|_|_|_|_|o|o|
|o|o|_|_|_|_|_|_|
|o|o|_|_|_|_|_|_|
|_|_|_|_|o|o|_|_|
|_|_|_|_|o|o|_|_|
Per n=9 forma un circuito unico.
per n=10 forma addirittura 5 circuiti separati, n=11 ha un circuito unico,
n=12 ha due circuiti separati.
GaS