Newsgroup: it.hobby.enigmi
Titolo: cercasi enigma

Se coloriamo ogni arco di un grafo completo di ordine n (tutti i vertici
sono collegati) con un colore scelto fra tre diversi, ci sara' almeno un
triangolo coi lati tutti dello stesso colore.
Qual e' il minimo n che garantisce tale condizione, qualunque si la
colorazione degli archi?
Una volta risposto a questa domanda, si puo' costruire un'enigma che
sfrutti questa conclusione. Potremmo poi votare il piu' interessante.
comincio col proporre, a titolo di esempio, il quesito dal quale ho tratto
lo spunto:
n persone (il dato era noto, ma poiche' ho trasformato il problema da una
semplice dimostrazione ad una ricerca di un minimo, non lo svelo...) si
scambiano reciprocamente delle lettere con tre possibili argomenti.
dimostrare che almeno tre di queste persone si scrivono lettere con
medesimo soggetto.
Si possono proporre problemi decisionali (dato n e' vero che... oppure:
sono necesssari n, sono sufficienti n), di ottimizzazione (qual e' il
numero massimo/minimo di...), richieste di dimostrazioni, controesempi e
quant'altro, l'importante e' che siano in tema. 
Ciao, Silvio

Ciao, Silvio
ciao
paolo

 colorazione degli archi?
Il primo ad analizzare la colorazione di grafi completi, e' stato
F.P.Ramsey morto nel 1930 a soli 26 anni.
Se proviamo a colorare un grafo completo di ordine 5 con 2 colori in
modo da evitare qualunque triangolo monocromatico, possiamo riuscirci
facilmente, ma per l'ordine 6 otterremo inevitabilmente almeno un
triangolo monocolore. Su questo principio esiste un gioco abbastanza
famoso SIM, di G. Simmon. Si inizia col disegnare su un foglio 6 punti
(vertici di un esagono regolare). Due giocatori armati di matite di
differenti colori, diciamo Rosso il primo e Blu il secondo, uniscono a
turno 2 punti del grafo. Perde il primo che disegna un triangolo del
proprio colore. Dato che il grafo non puo' essere colorato senza che
cio' avvenga, non si puo' chiudere in parita'.
A questo punto occorre una notazione. Per 2 colori R(x,y) denota il
minimo ordine del grafo, che obbliga a colorare almeno un subgrafo x od
uno y dello stesso colore. (R sta per Ramsey). Allora per il caso in
questione scriveremo:
R(3,3)=6, che come abbiamo visto ci dice che 6 e' il minimo ordine che
obbliga ad ottenere un subgrafo di ordine 3 (triangolo) monocromatico.
Non molti di questi valori sono stati dimostrati, eccone alcuni:
R(3,4)=9  R(3,5)=14  R(4,4)=18  R(3,6)=18  R(3,7)=23  R(3,9)=36
Da R(3,6)=18 possiamo ad es. dire che se ad un party partecipano 18
persone che si conoscono (rosso) oppure NON si conoscono (blu), ci
saranno sicuramente 3 persone che si conoscono reciprocamente oppure 6
che non si sono mai viste.
Con 3 colori la cosa si complica. Quello che chiedi e' il valore di
R(3,3,3), e' stato dimostrato nel 1955 che questo valore e' 17. Un buon
esercizio e' provare a colorare un grafo di ordine 16 senza ottenere
triangoli per ciascuno dei 3 colori.
Tornando a 2 soli colori possiamo chiederci: "Per un grafo di ordine n,
qual'e il numero minimo di triangoli  tutti rossi o tutti blu che saremo
forzati a colorare ?"
A.W.Goodman da' la risposta in "On Sets of Acquaintances and Strangers
at Any Party" uno scritto del 1959:
Se n e' della forma   2u = 1/3 u(u-1)(u-2).
Se n e' della forma 4u+1 = 1/3 2u(u-1)(4u+1).
Se n e' della forma 4u+3 = 1/3 2u(u+1)(4u-1).
Per 4 colori, R(3,3,3,3) e' ancora sconosciuto, ma e' dimostrato che sta
fra 51 e 64.
Per il problema inerente a questo argomento... ci devo ancora pensare.
ciao :)dario

 problema, nell'altro e' una astrazione matematica.
Bello anche l'enigma.
Senti questo:
Alla fine del girone di andata del campionato di serie A del 198x per
nessuna terna di squadre le partite sono terminate con la stessa tipologia
di risultato (parita', un gol di scarto, piu' di una rete di differenza).
"E' impossibile" - mi viene affermato. "E' vero, ho sbagliato di un anno!"
- dico io. Di che anni stiamo parlando?
Ciao, Silvio

almeno un triangolo monocromatico.
C'e' qualcosa che non mi convince. Indipendentemente da quello che
puo' aver scritto Dario, mi chiedo:
l'aver ottenuto n=17 e' basato sul fatto di poter in questo modo
svolgere considerazioni sul sottografo di ordine 6, per il quale gia'
si conosce qualcosa. Fin qui tutto OK.
Paolo stesso pero' ammette di non sapere se gia' n=16 lo smentisce; in
effetti lo stesso ragionamento sui sottografi non funziona, e non si
sa se, visto che ad ogni punto puo' essere associato un sottografo di
ordine 15, tramite l'"interazione" di questi sottografi e dei punti
che questi contengono (peggio delle ragnatele dell'Uomo Ragno!) non si
ottenga comunque un triangolo monocromatico.
Ieri notte prima di dormire la mia idea era stata questa (ma erano le
2:00...): dati n punti, si possono costruire n!/((l!(n-l)!) cammini di
ordine l. Con n punti, avremo dunque n!/(3!(n-3)!) triangoli.
Con 3 colori (RVB) posso costruire 10 triangoli diversi (cioe'
considerando ad es. RRB diverso da RBR). Allora ho detto:
trova n t.c. n!/(3!(n-3)!)>=10; n=5. E sono andato a letto.
Grossa stupidaggine; la giornata di ieri e' stata proprio pesante!
Il problema in effetti sta proprio nel fatto che un triangolo (es.
RBR) potrebbe addirittura "ripetersi" nello stesso grafo di ordine n,
e non sappiamo quante ripetizioni devono essere fatte prima di esser
costretti ad ottenere un triangolo monocromatico. Con 17 punti
tracciamo 680 triangoli; i triangoli distinti, a meno di permutazioni
nei colori, sono solo 27 con 3 colori.
E' un bel problema indipendentemente dalla sua riformulazione in
termini di lettere o aeroporti!!!
Stefano Costa
^^^^^^^^^^^^^
sco...@enjoy.it
cos...@odino.unipv.it