OliForum Matematico

$80$ scienziati si tengono tutti in contatto su di loro su tre argomenti, ovvero ogni scienziato scambia informazioni con gli altri $79$ scienziati su $3$ argomenti a scelta (ogni scienziato può parlare di più argomenti contemporaneamente). Esistono $4$ scienziati $A,B,C$ e $D$ tali che:
$A$ parla di un certo argomento $a$ con $B$, $B$ parla di $a$ con $C$, $C$ parla di $a$ con $D$, $D$ parla di $a$ con $A$ ?

P.S.: sono molto ben accetti rilanci di ogni genere

Il problema dice che ogni coppia di scienziati sceglie uno dei 3 argomenti e parla di quello?
Se è così ho un bel rilancio:
E se gli argomenti fossero $n$ e gli scienziati $2n^2$?

Altrimenti non ho capito il testo e non vedo come altro interpretarlo (credo sia questa la realtà... oppure ho segato la dimostrazione... perchè mi sembra un po' troppo radicale l'abbassamento di bound dato che abbassa 80 a 18 o alza 3 argomenti a 6... )

Sì dario, ogni coppia sceglie un argomento e parla solo di quello

Tecnicamente credo si possa arrivare a dire che vale per $n$ argomenti e $n^2+n+1$ scienziati, ma è un po' complicato da dimostrare... (quindi nel nostro caso $3$ argomenti e $13$ scienziati, ma poi porta male...)

EvaristeG ha scritto:Tecnicamente credo si possa arrivare a dire che vale per $n$ argomenti e $n^2+n+1$ scienziati, ma è un po' complicato da dimostrare... (quindi nel nostro caso $3$ argomenti e $13$ scienziati, ma poi porta male...)

Uhuh che ganzo
Comunque la mia dimostrazione per $2n^2$ è perfettamente olimpica... e pure bella

...e piena di modestia, e senza lemmi con nomi buffi ...

Allora... provo la versione $2n^2$ scienziati e $n$ argomenti.

Considero il grafo completo $n$-colorato con vertici gli scienziati e archi di colore diverso a seconda dell'argomento di cui parlano i due vertici.
Voglio trovare quante "V" monocromotiche ci sono al minimo, considero quindi un qualsiasi scienziato e chiamo $a_1$, ..., $a_n$ il numero di archi che escono da quel vertice rispettivamente del colore 1, 2, ..., $n$.
La somma $a_1+...+a_n$ è uguale a $2n^2-1$ e il numero di "V" con "punta" nel vertice considerato è
$$
\sum_{i=1}^{n}{\binom{a_i}{2}}=\frac{1}{2} \left( \sum_{i=1}^{n}{a_i^2}-\sum_{i=1}^{n}{a_i} \right) =\frac{1}{2} \left( \sum_{i=1}^{n}{a_i^2}-(2n^2-1) \right)\ge
\frac{1}{2} \left( \frac{(2n^2-1)^2}{n}-(2n^2-1) \right)
$$
di cui l'ultima disuguaglianza per QM-AM.
Questo vale per ogni vertice quindi avrò che il numero totale di "V" monocromatiche (anche di colori diversi) sarà maggiore o uguale a
$$
2n^2\frac{(2n^2-1)(2n^2-n-1)}{2n}=n(2n^2-1)(2n^2-n-1)
$$
Quindi ci saranno almeno $(2n^2-1)(2n^2-n-1)$ "V" monocromatiche dello stesso colore, dimostro ora che almeno due di queste "V" hanno la stessa "base".
Il numero di coppie di vertici del grafo è $\binom{2n^2}{2}=n^2(2n^2-1)$ che è minore di $(2n^2-1)(2n^2-n-1)$, quindi almeno 2 "V" dovranno avere la stessa coppia di vertici di "base", da cui la tesi.

Se è giusto quello che ho fatto credo funzioni anche con $n^2+n+2$ scienziati e $n$ argomenti...

Yo! Che soluzione ganza
Praticamente arrivi a quello che sam aveva definito un po' complicato da dimostrare Invece è una figata... piccola aggiunta... per $n$ pari riesco ad abbassare il bound a $n^2+n+1$ che è proprio quello di sam... perchè se al posto di $2n^2$ nella tua dimostrazione metto $n^2+n+1$ risulta alla fine un'uguaglianza quindi o ci sta un quadrilatero monocromatico o devono essere tutte uguaglianze quelle precedenti nella dimostrazione quindi deve essere che da ogni vertice partono esattamente $n+1$ archi di ogni colore. Ma questo è impossibile perchè... se cancello tutti gli archi tranne quelli di un certo colore risulta che resta un grafo con $\frac{(n+1)(n^2+n+1)}{2}$ archi... che è un numero non intero!