qwerty

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Rispondi
wotzu
Messaggi: 52
Iscritto il: 16 dic 2015, 21:33

qwerty

Messaggio da wotzu »

hai un grafo con $16$ vertici , ogni coppia di vertici è collegata da un segmento che può essere di $3$ color diversi, dimostra che esiste esiste una colorazione per cui non si ha alcun triangolo monocromatico.
Avatar utente
karlosson_sul_tetto
Messaggi: 1452
Iscritto il: 10 set 2009, 13:21
Località: Napoli

Re: qwerty

Messaggio da karlosson_sul_tetto »

Mi sento trolloso.
Siano R,V,B i tre colori:
Testo nascosto:

Codice: Seleziona tutto

   1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16
1  X  R  V  V  R  V  R  B  B  R  R  B  V  V  B  B
2  R  X  R  V  V  R  V  R  B  B  B  R  B  V  V  B 
3  V  R  X  R  V  B  R  V  R  B  V  B  R  B  V  B
4  V  V  R  X  R  B  B  R  V  R  V  V  B  R  B  B
5  R  V  V  R  X  R  B  B  R  V  B  V  V  B  R  B
6  V  R  B  B  R  X  V  B  B  V  B  V  R  R  V  R
7  R  V  R  B  B  V  X  V  B  B  V  B  V  R  R  R
8  B  R  V  R  B  B  V  X  V  B  R  V  B  V  R  R
9  B  B  R  V  R  B  B  V  X  V  R  R  V  B  V  R
10 R  B  B  R  V  V  B  B  V  X  V  R  R  V  B  R
11 R  B  V  V  B  B  V  R  R  V  X  B  R  R  B  V
12 B  R  B  V  V  V  B  V  R  R  B  X  B  R  R  V
13 V  B  R  B  V  R  V  B  V  R  R  B  X  B  R  V
14 V  V  B  R  B  R  R  V  B  V  R  R  B  X  B  V
15 B  V  V  B  R  V  R  R  V  B  B  R  R  B  X  V
16 B  B  B  B  B  R  R  R  R  R  V  V  V  V  V  X
 
"Inequality happens"
---
"Chissa se la fanno anche da asporto"
fph
Site Admin
Messaggi: 3956
Iscritto il: 01 gen 1970, 01:00
Località: in giro
Contatta:

Re: qwerty

Messaggio da fph »

Ora devi solo dimostrare che non c'è nessun triangolo monocromatico... altrimenti 7 punti non te li dà nessuno. :D
--federico
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]
Avatar utente
karlosson_sul_tetto
Messaggi: 1452
Iscritto il: 10 set 2009, 13:21
Località: Napoli

Re: qwerty

Messaggio da karlosson_sul_tetto »

Purtroppo non sono LucaMac, altrimenti nessuno se ne sarebbe accorto :lol:
"Inequality happens"
---
"Chissa se la fanno anche da asporto"
LucaMac
Messaggi: 180
Iscritto il: 14 set 2014, 19:59
Località: Napoli

Re: qwerty

Messaggio da LucaMac »

karlosson_sul_tetto ha scritto:Purtroppo non sono LucaMac, altrimenti nessuno se ne sarebbe accorto :lol:
Ma dai, che sarà mai, scrivi 81 lettere a caso e scrivi "funziona" , è solo un controllo finito!
"And if we want to buy something to drink?"
"Just go to 7-11"
-----------------------------------
"Why an inequality?"
"Inequality happens"
MATHia
Messaggi: 90
Iscritto il: 11 apr 2014, 01:08

Re: qwerty

Messaggio da MATHia »

Siano rosso, giallo, blu i tre colori. Scegliamo un vertice $V_1$ del grafo. Per pigeonhole, esiste un colore (wlog rosso) tale che esistono sei vertici collegati al primo da segmenti rossi. Se tra questi sei esistono due vertici $A$, $B$ tali che $AB$ è rosso, allora $V_1AB$ è un triangolo monocromatico. Altrimenti, tutti i segmenti tra i sei vertici considerati sono gialli o blu. Sia $V_2$ un vertice dei sei. Per pigeonhole, esistono tre vertici $C$, $D$, $E$ (tra i sei considerati) collegati a $V_2$ con segmenti wlog gialli. Se tra questi tre c'è almeno un segmento giallo (wlog $CD$), allora $V_2CD$ è un triangolo monocromatico. Altrimenti tutti i segmenti tra $C$, $D$, $E$ sono blu, per cui $CDE$ è un triangolo monocromatico.
Avatar utente
karlosson_sul_tetto
Messaggi: 1452
Iscritto il: 10 set 2009, 13:21
Località: Napoli

Re: qwerty

Messaggio da karlosson_sul_tetto »

MATHia ha scritto:Scegliamo un vertice $V_1$ del grafo. Per pigeonhole, esiste un colore (wlog rosso) tale che esistono sei vertici collegati al primo da segmenti rossi.
$ \frac{16-1}{3}=5 $
"Inequality happens"
---
"Chissa se la fanno anche da asporto"
MATHia
Messaggi: 90
Iscritto il: 11 apr 2014, 01:08

Re: qwerty

Messaggio da MATHia »

Ops, nella mia mente ho contato anche $V_1$ tra i vertici collegati a $V_1$ :?
Rispondi