(Da kvant)
In un gruppo ci sono N persone, e a ciascuna di esse piacciono esattamente k persone di questo gruppo.Qual è il più piccolo k per il quae si può affermare "in questo gruppo sicuramente ci sono almeno due persone che si piaccioo l'un l'altro"?
P.S:ma va qui o in combinatoria?
"Inequality happens"
---
"Chissa se la fanno anche da asporto"
Il valore cercato é $ \displaystyle \frac {N-1}2 $.
Uniamo con una freccia due persone in modo tale che essa parta da una persona ed arrivi ad una persona che le piace, come detto in ipotesi da ogni persona partono k frecce.
Poiché vi sono N persone e da ogni persona partono k frecce, il numero totale delle frecce sarà Nk.
Per il principio del pigeonhole, ci sarà almeno una persona che riceve un numero di frecce maggiore o uguale a
$ \displaystyle \frac {Nk} N = k $
dunque, se da questa persona partono k frecce e ne arrivano k, la condizione per cui ci sia almeno una persona con cui essa é collegata da due frecce con un'altra é che il numero delle frecce ricevute (ossia k), é maggiore del numero delle persone a cui non ha mandato alcuna freccia. Siccome il numero delle persone a cui può mandare frecce é N - 1 e il numero delle frecce mandate é k, il numero delle persone a cui la persona in questione non ha mandato alcuna freccia é N - 1 - k.
Risolvendo la seguente disequazione si trova il valore cercato dalla tesi:
$ k > N - 1 - k $
$ 2k > N - 1 $
$ \displaystyle k > \frac {N-1}2 $
Pertanto il valore cercato é proprio il più piccolo valore maggiore o uguale a $ \displaystyle \frac {N-1}2 $.
