Newsgroup: it.hobby.enigmi
Titolo: File di pedine

  _ _ _ _ _
|a|_|_|_|_|
|_|_|b|_|_|
|_|_|c|_|d|
|_|_|_|e|_|
|_|_|f|_|_|
Su questo campo 5x5 sono collocate 6 pedine.
Possono essere individuate 4 linee di 3.
abd, ace, bcf, def.
Qual e' la piu' piccola scacchierina mxn sulla quale e' possibile risolvere 
lo stesso problema ?
Cerca soluzioni per:
10 pedine in 5 linee di 4
15 pedine in 6 linee di 5
dario

 ha scritto nel messaggio
news:3CD5461B...@uriland.it...

Provo con questa:
S
P
O
I
L
E
R
  _ _ _ _ _ _ _
 |l|_|_|_|_|_|_|
 |_|i|_|_|_|_|_|
 |_|h|_|_|_|_|_|
 |_|_|_|g|_|_|_|
 |_|_|f|_|_|_|_|
 |_|e|_|_|_|_|_|
 |a|b|_|c|_|_|d|
Ciao a tutti,
GaS

 lo stesso problema ?
.
.
.
.
.
.
.
.
.
.
Al momento (credo) di aver trovato la risposta alla prima domanda.
;-))
L'algoritmo usato e' buono...ma forse per le altre domande deve
essere migliorato...Ecco la soluzione per una scacchiera 4x5:
 _ _ _ _ 
|a|b|_|c|
|_|d|_|_|
|_|_|e|_|
|_|_|_|_|
|_|f|_|_|
Le quattro linee sono....:
a,b,c
a,d,e
b,d,f
c,e,f
CiaO,
Massimo

 dario
Provo ora con questa, naturalmente non so se è ottimale.
S
P
O
I
L
E
R
!
Scacchiera 12x12
  _ _ _ _ _ _ _ _ _ _ _ _
 |_|a|_|_|_|_|_|_|_|_|_|_|
 |_|b|c|_|_|d|_|_|_|_|e|f|
 |_|_|_|_|_|_|_|_|_|g|_|_|
 |_|_|_|_|h|_|_|_|_|_|_|_|
 |_|_|_|_|_|i|_|_|_|_|_|_|
 |_|_|_|l|_|_|m|_|_|_|_|_|
 |_|n|_|_|_|_|_|_|_|_|_|_|
 |_|_|_|_|_|_|_|_|_|_|_|_|
 |_|_|_|_|_|_|_|_|_|_|_|_|
 |_|o|_|_|_|_|_|_|_|_|_|_|
 |_|p|_|_|_|_|_|_|_|_|_|_|
 |q|_|_|_|_|_|_|_|_|_|_|_|
Le 6 linee sono:
abnop
bcdef
achim
nligf
qolhd
qpmge
Ciao a tutti,
GaS

 Al momento (credo) di aver trovato la risposta alla prima domanda.
.
.
.
Ci sono ben quattro soluzioni per scacchiere 4x5 ma la cosa curiosa
e' che c'e' ne una sola per la scacchiera 4x6...
C'e' qualcuno che l'ha trovata...?
CiaO,
Massimo
PS...Sto' lavorando al prg per ottimizzare la ricerca e spero presto
     di trovare le altre soluzioni...

 15 pedine in 6 linee di 5
.
.
Sto' provando anche altri approcci al problema...ma non e' facile
almeno per le mie modeste capacita'...
Eppure e' singolare la 'coincidenza' che tu abbia chiesto proprio
questi tre casi....:
pedine linee da_pezzi
  6      4     3
 10      5     4
 15      6     5
...in quanto per ogni soluzione si nota chiaramente che ogni pedina
sara' presente in due linee....Mi sbaglio...?
;-)
CiaO,
Massimo

 lo stesso problema ?
Forse non vale ma:
.
.
.
.
.
.
.
.
in una scacchiera 4*1
abcd
ci sono le file abc, abd, acd, bcd
e utilizzo *non più di* 6 pedine
se invece si chiedono *esattamente* 6 pedine passo alla scacchiera 4*2
abcd
ef..
:-)
ciao
paolo

 Massimo
Ciao a tutti,
GaS

 Massimo
Ciao a tutti,
GaS

 sara' presente in due linee....Mi sbaglio...?
In realta', quella che tu noti, e' una condizione che avrei dovuto 
includere nell'esporre il problema. Altrimenti gli "attacchi" di Paolo sono 
inoppugnabili.

 piu piccola.... o sbaglio?
.
.
.Chiaro....ma 'devi' considerarle minori, quindi sicuramente
tutte le 4x5 sono anche nella 4x6 ma quello che dicevo io e'
che di 4x6 'reale' ne esiste solo una configurazione a parte
le r&r.
Cmq ancora non ho capito se la mia soluzione 4x5 sia la minima...
;-)
CiaO,
Massimo 
-- 
Posted via Mailgate.ORG Server - 
http://www.Mailgate.ORG

 ;-)
Credo di si, mi pare che si possa almeno dimostrare che non è possibile una
soluzione 3*n.
Considera un quadrilatero completo, ossia la figura nel piano formata da
quattro rette che si intersecano in sei punti, per esempio:
.      \  |
.       \ |     /
.        \|    /
.         |   /
.         |\ /
.         | /
.         |/ \
.         |   \
.        /|    \
.  _____/_|_____\_________
.      /  |      \
.     /   |       \
.    /    |        \
.
Il nostro problema consiste in pratica nel formare un quadrilatero completo,
dove i sei punti di intersezione abbiano coordinate intere, con la ulteriore
limitazione che non ci siano tre rette intersecantesi in un punto.
Escludiamo inoltre la possibilità di quattro o più punti allineati (vedi il
mio post precedente).
Allora, in una scacchiera 3*n, con non più di tre punti (pedine) su una
riga, deve esserci un'altra riga con almeno due pedine; avremo pertanto due
rette parallele, e la sesta pedina andrebbe ... nel loro punto di incontro;
insomma una scacchiera larga 3 dovrebbe avere lunghezza infinita.
Resterebbe da dimostrare l'impossibilità del 4*4
ciao
paolo

 ;-)
Io non ho capito se le mie per gli altri due problemi sono minime, non penso
ma adesso non ho nessuno stimolo per provare a migliorarmi...
