Anticricche

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Rispondi
Avatar utente
Anér
Messaggi: 720
Iscritto il: 03 giu 2008, 21:16
Località: Sabaudia

Anticricche

Messaggio da Anér » 06 dic 2010, 17:28

Come al solito è facile, come al solito date la soluzione solo se non sapete risolverlo.
Abbiamo un grafo su n vertici, e ogni vertice ha grado minore o uguale a k. Dimostrare che si possono prendere almeno $ \lceil\frac{n}{k+1}\rceil $ vertici che formino un'anticricca (che siano dunque a due a due non collegati).
Sono il cuoco della nazionale!

Avatar utente
Anér
Messaggi: 720
Iscritto il: 03 giu 2008, 21:16
Località: Sabaudia

Re: Anticricche

Messaggio da Anér » 08 dic 2010, 16:59

Anér ha scritto:Come al solito date la soluzione solo se non sapete risolverlo.
Suvvia, era uno scherzo!
Sono il cuoco della nazionale!

Euler
Messaggi: 345
Iscritto il: 20 mar 2010, 22:07
Località: Trento

Re: Anticricche

Messaggio da Euler » 26 dic 2010, 19:36

Ma sbaglio o è semplicissimo? Penso vada bene costruire l' anticricca facendo vertice per vertice. Prendo un vertice a caso, e questo sarà il primo appartenente all'anticricca; poi, per scegliere il secondo, ho una scelta di almeno $n-k-1$ altri vertici, visto che uno è il vertice stesso e al massimo altri k sono quelli a lui collegati, che nel peggiore dei casi non sono collegati a quello da scegliere. Poi procedo con il terzo, e dovrò sceglierlo almeno tra $n-2k-2=n-2(k-1)$, per gli stessi motivi. Ora posso dimostrare che l'm-esimo termine dell'anticricca lo posso scegliere tra almeno $n-(m-1)(k+1)$ vertici; infatti, se prima ne ho già scelti $m-1$, dovrò escluderne $(m-1)k$ e i vertici stessi.
Quindi adesso, per vedere quanti vertici può contenere al minimo l'anticricca, basterebbe che $n-(\lceil\frac{n}{k+1}\rceil-1)(k+1)$ sia maggiore di 0 (e non quello successivo). Questo è vero perché $\lceil\frac{n}{k+1}\rceil-1< \frac{n}{k+1}$ e sotituendo $\frac{n}{k+1}$ ottengo l'uguaglianza a 0 (mentre con l'intero subito dopo si ottiene un numero nullo o negativo) $\square$

Avatar utente
Anér
Messaggi: 720
Iscritto il: 03 giu 2008, 21:16
Località: Sabaudia

Re: Anticricche

Messaggio da Anér » 28 dic 2010, 12:19

Euler ha scritto:Ma sbaglio o è semplicissimo?
No, non sbagli, era davvero semplice.
Sono il cuoco della nazionale!

Rispondi