Newsgroup: it.hobby.enigmi
Titolo: SECONDO ME NN CI RIUSCITE!!

Dopo anni e anni di lontananza torno nel ng...con un bel quesito...
1)Prendete i 6 vertici di un esagono
2)Collegate tutti i vertici tra loro(ogni vertice deve essere collegato agli
altri 5)
3)Chiamiamo arco il collegamento tra due vertici distinti
Riuscite a colorare gli archi con 2 colori diversi senza ottenere nemmeno un
triangolo dello stesso colore??
P.S. per triangolo intendo 3 vertici dell'esagono collegati tra loro
                                                                O
                                                              /    \
                                                             /      \
                                                            /        \
                                                           /          \
                                                         /             \
                                                       O---------O
Io domani partoper l'università,torno venerdi...se ci riuscite siete
veramente forti....
Ramsey/Bandian


s
 p
  o
 i
l
 e
  r
 .
s
 p
  o
 i
l
 e
  r
 .
s
 p
  o
 i
l
 e
  r
 .
s
 p
  o
 i
l
 e
  r
 .
Io credo che il problema non abbia soluzione. Ho scritto un programma
nel linguaggio ECLiPSe e mi dice che il problema non ammette soluzioni.
Per semplicita` ho costruito una matrice 6x6 di variabili binarie (che
possono assumere solo i valori 0 e 1). Ho imposto il vincolo di simmetria
della matrice ed ho richiesto che preso un triangolo qualsiasi, il numero
di lati con il colore 0 fosse 1 oppure 2, stessa cosa per il colore 1. A
questo punto parte la search, con il classico algoritmo che si usa in 
Constraint Programming.
Il programma esegue in 0.04 sec. su un Pentium II e risponde che non
ci sono soluzioni. Ma forse c'e` qualche bug: riporto il programma per
eventuali correzioni.
ciao ciao,
Marco
=========================================================================
:- lib(fd).
:- lib(fd_search).
:- lib(fd_global).
esagono(E) :-
% Costruisco un array 6x6 di variabili che
% possono assumere solo i valori 0 e 1
    dim(E,[6,6]),
    term_variables(E,Elist),
    Elist :: [0,1],
% Impongo che l'array rappresenti una matrice
% simmetrica
    simmetrici(E),
% Impongo che non esista un triangolo
% monocolore
    no_triangolo_mono(E),
% Faccio partire la search
    labeling(Elist).
simmetrici(E) :-
    (for(I,1,5), param(E) do
      ( I1 is I+1,
        (for(J,I1,6), param(E,I,I1) do
            E[I,J] #= E[J,I]
        ))).
no_triangolo_mono(E) :-
    (for(I,1,4), param(E) do
      ( I1 is I+1,
        (for(J,I1,5), param(E,I,I1) do
          ( J1 is J+1,
            (for(K,J1,6), param(E,I,J1,J) do
                no_mono(E,I,J,K)
            ))))).
% Vincolo che impone che il triangolo che ha
% vertici I,J,K non sia costituito da un solo
% colore
no_mono(E,I,J,K) :-
    A #= E[I,J],
    B #= E[J,K],
    C #= E[K,I],
% Il numero di occorrenze del colore 0 nel triangolo
% va da 1 a 2 (cioe` ci sono 1 o 2 lati di colore 0)
% Stessa cosa per il colore 1
    [N0,N1] :: 1..2,
    occurrences(0,[A,B,C],N0),
    occurrences(1,[A,B,C],N1).
-- 
http://www.ing.unife.it/docenti/MarcoGavanelli

 triangolo dello stesso colore??
.
.
.
.
.
.
.
.
.
.
.
.
E' facile vedere che non è possibile.
Consideriamo uno dei vertici dell'esagono, chiamiamolo A. Da questo
partiranno 5 archi colorati, di cui almeno tre (AB,AC,AD) dello stesso
colore (rosso). Consideriamo il triangolo BCD. Nessuno dei suoi archi può
essere rosso, altrimenti ci sarebbe un triangolo rosso. Quindi tutti e tre
gli archi di ABC sono neri. cvd.
Mi pare di ricordare che i trinagoli monocromatici in un grafo completo di
ordine 6 siano almeno 2, ma non ci giurerei.
Silv:o)

 ordine 6 siano almeno 2.
E' vero. Esiste pure un gioco, abbastanza conosciuto, inventato da Gustavus 
Simmons, il SIM, due giocatori si alternano disegnando un arco del proprio 
colore, il primo che chiude un triangolo monocromatico perde.
Questi grafi bicolore rappresentano bene le reciproche conoscenze di n 
persone ad un party.
Qual e' il numero minimo di triangoli monocromatici, in un grafo completo 
di n punti, bicolorato?
Esistono formule date da Goodman nel 1959.
Se n e' della forma 2u:
u(u-1)(u-2)/3
Se n e' della forma 4u+1:
2u(u-1)(4u+1)/3
Se n e' della forma 4u+3:
2u(u+1)(4u-1)/3
Per grafi completi da 6 a 12, si ottiene:
2,4,8,12,20,28,40...
:) dario

 wrote in message
qvaT7.10820$o9.4...@news1.tin.it...

il da te citato ramsey ha dimostrato che è possibile trovare un insieme
ordinato per insiemi con cardinalità abbastanza grandi. per 2 clori soli, 6
è abbastanza grande! per valori superiori i numeri crescono più velocemente
che l'esponenziale! guardatevi le scienze! ah dimenticavo. sono nuovo di
qui. abbiate pietà! pazzqo

Come sempre, meglio tardi che mai...:-)
Cmq, dato che ho trovato una soluzione diversa, ve la posto!
Sappiamo dalla formula di Eulero che P+F-L=1 per qualsiasi figura piana
(P=punti, F=facce, L=lati).
E' chiaro che nel nostro problema ogni punto viene toccato da almeno una
linea colorata ed almeno una non colorata, altrimenti si otterrebbe subito
una contraddizione.
Allora la serie di segmenti colorati che chiamiamo 'a' forma una figura a
cui è applicabile la formula:
Pa+Fa-La=1
Idem per i segmenti non colorati (b)
Pb+Fb-Lb=1
A questo punto sommando le due eguaglianze:
(Pa+Pb)+(Fa+Fb)-(La+Lb)=2
e ricordando che (vedi sopra):
Pa+Pb=6+6=12
La+Lb=C(6,2)=15
Chiamando X il numero di facce si ha:
12+X-15=2
X=5
Quindi ci devono essere 5 facce. Solo 3 quadrilateri sono possibili, quindi
le altre due sono...TRIANGOLI!
CIAO
        Flavio


Hum... più ci penso meno mi convince l'applicazione della formula che ho
usato. Il problema è definire le "facce" dove ci sono delle intersezioni...
Però mi sembra anche impossibile che il risultato giusto salti fuori così
bene. Secondo voi è valida (o da correggere) la mia soluzione?
--
CIAO
       Flavio

 wrote in message
9vvjh4$i66vk$1...@ID-69836.news.dfncis.de...


 un quadrato giallo. Quale è il minimo N?
Chi fosse interessato ai risultati aggiornati circa i numeri di Ramsey, 
segnalo il sito di Radziszowsky. Si puo' leggere in formato .pdf con una 
bibliografia di oltre 300 riferimenti.
http://www.cs.rit.edu/~spr/ElJC/eline.html
:) dario