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$
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
Re: Grafo
Inviato: 20 lug 2016, 08:28
da karlosson_sul_tetto
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).