Pagina 1 di 2

Simulazione 2016 2 (OliMaTo)

MessaggioInviato: 01/05/2016, 20:02
da Rho33
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 .

Re: Simulazione 2016 2 (OliMaTo)

MessaggioInviato: 01/05/2016, 20:16
da Veritasium
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]

Re: Simulazione 2016 2 (OliMaTo)

MessaggioInviato: 01/05/2016, 20:22
da mr96
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

Re: Simulazione 2016 2 (OliMaTo)

MessaggioInviato: 01/05/2016, 20:35
da Rho33
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.

Re: Simulazione 2016 2 (OliMaTo)

MessaggioInviato: 01/05/2016, 21:22
da parisgermain98
Quindi per il punto b) il controesempio non basta? Io ho fatta a casa la prova è mi è andata da schifo :lol:

Re: Simulazione 2016 2 (OliMaTo)

MessaggioInviato: 01/05/2016, 21:47
da Livex
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].

Re: Simulazione 2016 2 (OliMaTo)

MessaggioInviato: 01/05/2016, 22:00
da mr96
No, non basta e si, puoi fare domande nei primi 30 minuti (ma non è detto che ti rispondano)

Re: Simulazione 2016 2 (OliMaTo)

MessaggioInviato: 01/05/2016, 22:05
da Federico II
E se io scegliessi $n=42$ e $c=2016$? Tanto $2016\geq\sqrt{42}+1$ :lol: :lol: :lol:

Re: Simulazione 2016 2 (OliMaTo)

MessaggioInviato: 02/05/2016, 15:27
da alexthirty
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:

Re: Simulazione 2016 2 (OliMaTo)

MessaggioInviato: 03/05/2016, 16:11
da gillg
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 ?