Italian TST 2005: problema n°1

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Rispondi
Simo_the_wolf
Moderatore
Messaggi: 1052
Iscritto il: 01 gen 1970, 01:00
Località: Pescara

Italian TST 2005: problema n°1

Messaggio da Simo_the_wolf » 22 mag 2005, 10:41

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.

Avatar utente
Boll
Messaggi: 1076
Iscritto il: 01 gen 1970, 01:00
Località: Piacenza

Messaggio da Boll » 22 mag 2005, 10:53

Le triplette si intendono distinte senza intersezioni?

Avatar utente
HumanTorch
Messaggi: 281
Iscritto il: 01 gen 1970, 01:00
Località: Tricase

Messaggio da HumanTorch » 22 mag 2005, 11:16

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
Moderatore
Messaggi: 1052
Iscritto il: 01 gen 1970, 01:00
Località: Pescara

Messaggio da Simo_the_wolf » 22 mag 2005, 11:35

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

Avatar utente
Boll
Messaggi: 1076
Iscritto il: 01 gen 1970, 01:00
Località: Piacenza

Messaggio da Boll » 23 mag 2005, 15:26

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 :D;))
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.
Ultima modifica di Boll il 24 mag 2005, 14:34, modificato 2 volte in totale.

Avatar utente
info
Messaggi: 903
Iscritto il: 01 gen 1970, 01:00

Messaggio da info » 23 mag 2005, 20:16

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 ...

Avatar utente
Boll
Messaggi: 1076
Iscritto il: 01 gen 1970, 01:00
Località: Piacenza

Messaggio da Boll » 23 mag 2005, 20:19

EDIT: Bah, a me sembra sia giusto uguale, mi ero incasinato un attimino rileggendo...
Ultima modifica di Boll il 24 mag 2005, 14:35, modificato 1 volta in totale.

MindFlyer

Messaggio da MindFlyer » 24 mag 2005, 05:10

Boll ha scritto: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 :D;))
Non ho capito un tubo di tutto questo.

Avatar utente
Boll
Messaggi: 1076
Iscritto il: 01 gen 1970, 01:00
Località: Piacenza

Messaggio da Boll » 24 mag 2005, 14:45

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...

Avatar utente
what
Messaggi: 158
Iscritto il: 01 gen 1970, 01:00
Località: roma

Messaggio da what » 28 mag 2005, 23:12

Boll ha scritto: (...) 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
Messaggi: 6
Iscritto il: 16 apr 2005, 16:37

Messaggio da darksky0 » 27 giu 2005, 19:42

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 :roll:

ditemi se erro

Rispondi