Italian TST 2005: problema n°1

[Simo_the_wolf]

Ci sono $ n>3 $ partecipanti ad una gara. Il giorno prima della gara i partecipanti si riuniscono in triplette e ognuna delle triplette cospira contro un altro partecipante. Dimostrare che esiste una persona con almeno
$ \displaystyle \sqrt [3] {(n-1)(n-2)} $
cospiratori.

[Boll]

Le triplette si intendono distinte senza intersezioni?

[HumanTorch]

Il numero $ n $ di partecipanti è multiplo di $ 3 $ o uno o due restano
"scoperti"? (e la radice cubica è da approssimare per difetto, vero?)

[Simo_the_wolf]

Si considera che il giorno prima della gara ogni possibile tripletta si riunisca e cospiri contro uno degli studenti

[Boll]

Uhm, proviamoci dai...

Le triplette cospiratrici sono $ \displaystyle \binom{n}{3} $
quindi ci sono esattamente $ \displaystyle \frac{n(n-1)(n-2)}{6} $ "mosse cospiranti"
mettendoci nel caso peggiore, cioè minimizzando il numero di triplette cospiratrici per persona avremo che sono
$ \displaystyle \frac{(n-1)(n-2)}{6} $
triplette per persona.
Ora, chiamato $ k $ il numero dei cospiratori presenti nelle triplette avremo che essi sono almeno $ \binom{k}{3} $ perchè, poniamo di prendere appunto queste $ \binom{k}{3} $ configurazioni, per migliorare la nostra situazione dovremo prendere una tripletta, toglierla e inserirne una nuova in modo che siano presenti meno implicazioni totali, ma ciò è impossibile, perchè se aggiungiamo persone nuove ci mettiamo in una situazione perdente, se invece tentiamo di sostituire la tripletta presente con un latra in cui sono contenute persone già utilizzate, ripeteremo una tripletta, poichè le abbiamo già contate tutte (se questo passaggio non è chairo, non esitate a chiedere ;))
Quindi si avrà
$ \displaystyle \binom{k}{3}= \binom{n}{3}*\frac{1}{n} $
$ k(k-1)(k-2)= (n-1)(n-2) $
ma $ k(k-1)(k-2)<k^3 $
quindi $ (n-1)(n-2)<k^3 $
$ \sqrt[3]{(n-1)(n-2)}<k $
q.e.d.

[info]

Solo un appunto (inutile? errato?)... se k è intero, come sembra, l'uguaglianza non mi sembra abbia senso sempre... è vero però che:

(k,3) >= (n,3)/n

infatti quei k ci devono dare un numero di triplette sufficienti... in prededenza già Boll aveva dimostrato l'esistenza di un tipo con un numero di triplette di conspiranti maggiore o uguale
e poi si prosegue uguale con confronto ...

[Boll]

EDIT: Bah, a me sembra sia giusto uguale, mi ero incasinato un attimino rileggendo...

[MindFlyer]

Ora, chiamato $ k $ il numero dei cospiratori presenti nelle triplette avremo che essi sono almeno $ \binom{k}{3} $ perchè, poniamo di prendere appunto queste $ \binom{k}{3} $ configurazioni, per migliorare la nostra situazione dovremo prendere una tripletta, toglierla e inserirne una nuova in modo che siano presenti meno implicazioni totali, ma ciò è impossibile, perchè se aggiungiamo persone nuove ci mettiamo in una situazione perdente, se invece tentiamo di sostituire la tripletta presente con un latra in cui sono contenute persone già utilizzate, ripeteremo una tripletta, poichè le abbiamo già contate tutte (se questo passaggio non è chairo, non esitate a chiedere ;))

Non ho capito un tubo di tutto questo.

[Boll]

Ho fatto veramente un casino pazzesco...

Allora, chiamiamo $ j $ il numero dei cospiratori, si è già detto che abbiamo $ \displaystyle \frac{(n-1)(n-2)}{6} $ triplette, ora ci mettiamo nel caso peggiore, cioè nel caso in cui, con tale numero di triplette, il numero di cospiratori sia minimo.

Affermo che tale minimo è $ k $, dove $ k $ è la soluzione dell'equazione $ \displaystyle \binom{k}{3}=\binom{n}{3}*\frac{1}{n} $. Dimostriamolo, poniamo di avere appunto tutte queste care triplette, in cui appaiono $ k $ cospiratori. Tentiamo di diminuire il numero dei cospiratori lasciando però invariato il numero totale delle triplette. Come dovremo fare? E' ovvio, almeno per iniziare dovremo togliere una tripletta e piazzarcene una nuova che fa in modo che il numero di cospiratori si abbassi. Per fare ciò la nuova tripletta dovrà evidentemente contenere cospiratori già utilizzati nelle altre triplette (sennò aggiungiamo gente), ma le altre triplette (per la definizione di binomiale) rappresentano già tutti i modi possibili di mettere i cospiratori che abbiamo in triplette, quindi l'unica che manca è quella che abbiamo tolto, quindi non possiamo diminuire il numero di gente. Quindi $ j\ge k $, poi si conclude come prima.



Dimmi se ora va meglio...

[what]

(...) ma le altre triplette (per la definizione di binomiale) rappresentano già tutti i modi possibili di mettere i cospiratori che abbiamo in triplette, quindi l'unica che manca è quella che abbiamo tolto, quindi non possiamo diminuire il numero di gente. Quindi $ j\ge k $, poi si conclude come prima.

Uhm... non ho capito molto.
Io farei così: dimostro con i piccioni che esiste un ragazzo al centro di $ \frac{(n-1)(n-2)}6 $ cospirazioni; ora, definito $ x $ come il numero di ragazzi che prendono parte ad almeno una di tali cospirazioni, si avrà $ \displaystyle \binom x 3\geq \frac{(n-1)(n-2)}6 $, da cui si conclude come hai fatto tu (i calcoli li ho capiti! ).

[darksky0]

mhm...

io l'ho svolto così...

siccome in un gruppo di n persone le uniche persone che possono formare triplette e conspirare contro una stessa persona sono (n - 1)

perchè le trplette conspirano con una persona esterna

il numero di triplette sarà quindi di (n - 1)!/3!(n - 4)!

con il gruppo più piccolo di persone (4 persone) vi è max una sola tripletta...

secondo quello che bisognerebbe dimostrare le triplette dovrebbero essere almeno

radical 3 di 6 che è maggiore di uno... e qst nn si trova... quindi la tesi non è valida

ditemi se erro