Grafo

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Rispondi
polarized
Messaggi: 96
Iscritto il: 06 feb 2015, 14:06

Grafo

Messaggio da polarized » 12 lug 2016, 13:56

Ad un party prendono parte $12k$ persone. Ciascuna di esse stringe la mano ad esattamente $3k+6$. Si sa che esiste un numero $N$ tale che, per ogni coppia di persone $A,B$ il numero di invitati che stringe la mano sia ad $A$ che a $B$ è esattamente $N$.

Determinare per quali valori interi di $k$ si può realizzare questa situazione.

In spoiler chiedo quale possa essere l'errore della mia soluzione
Testo nascosto:
Disegno un grafo con $\mid V\mid =12k$, dove $\forall A \in V \, \, \,\mbox{deg}(A)=3k+6$

Ora faccio un double counting sul numero di archi

\begin{equation}
\mid E\mid = \frac 1 2 \sum_{V_i \in V}\mbox{deg}(V_i)\\
\mid E\mid =\frac 1 2 (3k+6)(12k)
\end{equation}

D'altro canto so che $\forall A,B \exists ! N$ vertici collegati sia ad $A$ che a $B$. Quindi posso dire (ho il dubbio che possa essere un bottom bound ma anche se fosse il problema resta) che
\begin{equation}
\mid E\mid = \binom {12k} {2} 2N
\end{equation}

Uguagliando i due termini ottengo
\begin{equation}
3k+6=(24k-2)N
\end{equation}
Che però non ha soluzioni che diano sia k che N interi :(
In geometria tutto con Pitagora, in Algebra tutto con Tartaglia

Avatar utente
karlosson_sul_tetto
Messaggi: 1436
Iscritto il: 10 set 2009, 13:21
Località: Napoli

Re: Grafo

Messaggio da karlosson_sul_tetto » 20 lug 2016, 08:28

polarized ha scritto:
D'altro canto so che $\forall A,B \exists ! N$ vertici collegati sia ad $A$ che a $B$. Quindi posso dire (ho il dubbio che possa essere un bottom bound ma anche se fosse il problema resta) che
\begin{equation}
\mid E\mid = \binom {12k} {2} 2N
\end{equation}
Il problema è qua: dati due punti A,B, ci sono N punti $C_1\ldots C_N$ collegati sia ad A che a B; tu conti i segmenti $AC_1,BC_1,AC_2\ldots BC_N$; il problema è che scegliendo "C_1" come A e "C_2" come B, allora conterai $AC_1,AC_2" anche adesso, contando più segmenti di quanti ce ne siamo effettivamente (ed è quindi un upper bound).

Cerca ora di aggiustare il conteggio!
"Inequality happens"
---
"Chissa se la fanno anche da asporto"

Rispondi