Simulazione 2016 2 (OliMaTo)

Calcolo combinatorio (disposizioni, permutazioni e combinazioni) e calcolo delle probabilità.

Simulazione 2016 2 (OliMaTo)

Messaggioda Rho33 » 01/05/2016, 20:02

Dato un gruppo di $n$ persone è definita la relazione di conoscenza nel modo seguente: data una coppia di persone A e B, A conosce B se e soltanto se B conosce A.
Dimostrare che:

a) In un gruppo di $6$ persone esiste sempre un gruppo di tre persone che si conoscono tutte oppure un gruppo di tre persone che non si conoscono.
b) Dati $n,c \in \mathbb{N}$ con $n>2$ e $c\geq \sqrt n+1$non vero che esiste sempre un gruppo di $c$ persone che si conoscono tutte oppure un gruppo di $c$ persone che non si conoscono.

Soluzione:

Testo nascosto:
Riconduciamo il problema alla teoria dei grafi ( chiaramente le persone sono i vertici e le amicizie sono gli archi).

a) Scelgo uno dei $6$ vertici e lo chiamo $A$ . Consideriamo i restanti $5$ vertici, si possono verificare due configurazioni possibili:

$\bullet$ $A$ è collegato ad almeno tre vertici.

$\bullet $ $A$ non è collegato ad almeno tre vertici.

Le precedenti affermazioni sono una semplice conseguenza del pigeonhole: ho $5$ piccioni in $2$ scatole, allora vi sarà una scatola con almeno $3$ piccioni.

WLOG Siamo nella prima situazione, la seconda è analoga. Questi tre vertici li chiamiamo $B,C,D$ . Allora distinguiamo due sotto casi:

$\bullet$ Almeno due tra $B,C,D$ sono collegati tra loro, allora insieme al vertice $A$ formano un triangolo di amicizie.

$ \bullet $ $B,C,D$ sono indipendenti tra loro e quindi formano un triangolo di non-amicizie.

b) Scelgo $n=4$ ed $c=3$ . Considero un quadrato ( o anche un quadrilatero), esso non ha triangoli di amicizie e nemmeno non-triangoli . Quindi non è vero che esiste sempre quel gruppo di $c$ persone.

Ho però un dubbio sulla tesi b), non si deve intendere come generalizzazione della tesi a) giusto ? Perché $3 \leq \sqrt 6 +1 $ . In caso contrario, anche un pentagono va bene .
Rho33
 
Messaggi: 489
Iscritto il: 16/09/2014, 11:14

Re: Simulazione 2016 2 (OliMaTo)

Messaggioda Veritasium » 01/05/2016, 20:16

Rho33 ha scritto:.

b) Scelgo $n=4$ ed $c=3$ . Considero un quadrato ( o anche un quadrilatero), esso non ha triangoli di amicizie e nemmeno non-triangoli . Quindi non è vero che esiste sempre quel gruppo di $c$ persone.

Ho però un dubbio sulla tesi b), non si deve intendere come generalizzazione della tesi a) giusto ? Perché $3 \leq \sqrt 6 +1 $ . In caso contrario, anche un pentagono va bene .[/spoiler]


Penso che il punto b) vada dimostrato per qualsiasi [tex]n[/tex], non solo [tex]n = 4[/tex]
Veritasium
 
Messaggi: 206
Iscritto il: 30/03/2015, 20:36

Re: Simulazione 2016 2 (OliMaTo)

Messaggioda mr96 » 01/05/2016, 20:22

A Torino ti avremmo messo 4 punti... Perché siamo stati leggermente larghi coi punteggi... Però come dice Veritasium il b non va bene, e a Cesenatico non penso ti avrebbero messo più di 3 punti
mr96
 
Messaggi: 1486
Iscritto il: 11/02/2014, 20:37

Re: Simulazione 2016 2 (OliMaTo)

Messaggioda Rho33 » 01/05/2016, 20:35

Ah bene, quindi non avevo capito completamente il testo ! Ma durante la gara è possibile avere dei chiarimenti sul testo ? Perché il dubbio mi era venuto all'inizio leggendolo, poi però non ci ho fatto più caso.
Rho33
 
Messaggi: 489
Iscritto il: 16/09/2014, 11:14

Re: Simulazione 2016 2 (OliMaTo)

Messaggioda parisgermain98 » 01/05/2016, 21:22

Quindi per il punto b) il controesempio non basta? Io ho fatta a casa la prova è mi è andata da schifo :lol:
parisgermain98
 
Messaggi: 28
Iscritto il: 23/04/2016, 23:32

Re: Simulazione 2016 2 (OliMaTo)

Messaggioda Livex » 01/05/2016, 21:47

Alternativa (inutile) per il punto a):

Detto $n$ il numero di amicizie tra due persone, per non avere un gruppo di tre persone che si conoscono [tex]n \le 9[/tex], mentre per non avere nessun gruppo di tre persone che non si conoscono [tex]n \ge 10[/tex].
Livex
 
Messaggi: 994
Iscritto il: 15/03/2013, 15:33

Re: Simulazione 2016 2 (OliMaTo)

Messaggioda mr96 » 01/05/2016, 22:00

No, non basta e si, puoi fare domande nei primi 30 minuti (ma non è detto che ti rispondano)
mr96
 
Messaggi: 1486
Iscritto il: 11/02/2014, 20:37

Re: Simulazione 2016 2 (OliMaTo)

Messaggioda Federico II » 01/05/2016, 22:05

E se io scegliessi $n=42$ e $c=2016$? Tanto $2016\geq\sqrt{42}+1$ :lol: :lol: :lol:
Il responsabile della sala seminari
Avatar utente
Federico II
 
Messaggi: 449
Iscritto il: 14/05/2014, 14:53

Re: Simulazione 2016 2 (OliMaTo)

Messaggioda alexthirty » 02/05/2016, 15:27

mr96 ha scritto:No, non basta e si, puoi fare domande nei primi 30 minuti (ma non è detto che ti rispondano)

Detto così sembra che decidano a random se risponderti :lol:
Federico II ha scritto:E se io scegliessi [tex]n=42[/tex] :lol: :lol: :lol:
chissà perché proprio 42 :twisted:
alexthirty
 
Messaggi: 79
Iscritto il: 27/11/2013, 14:49

Re: Simulazione 2016 2 (OliMaTo)

Messaggioda gillg » 03/05/2016, 16:11

non ho capito bene cosa chiede il punto b , devo dimostrare che per ogni n non vero che esiste sempre un gruppo di c persone che si conoscono tutte oppure un gruppo di c persone che non si conoscono.
non basta prendere n=c ?
gillg
 
Messaggi: 179
Iscritto il: 27/11/2014, 14:38

Prossimo

Torna a Combinatoria e Probabilità

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite