[L03] Un bel grafo

[polarized]

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

[Rho33]

Il problema è nel tuo secondo double-counting: in questo modo non stai contando il numero di archi totali, ne stai contando MOLTI di più! Esempio: prendiamo i nostri due vertici $A,B$ e scegliamo, tra gli $N$ disponibili, i vertici $E,F$ ($E$ è collegato ad $A,B$ così come $F$ è collegato ad $A,B$). Quindi ci sono in tutto $4$ archi , $2$ per ognuno. Ora consideriamo la coppia $E,F$ , è chiaro che sia $A$ che $B$ sono collegati ad $E,F$ , ma tu li stai contando di nuovo e quindi per te i vertici sono $8$, mentre in realtà sono sempre $4$. Detto ciò, devi fare double-counting su un'altra cosa...

Soluzione:

Testo nascosto:

Contiamo le terne ordinate $(A,B,C)$ tali che $C$ ha stretto la mano sia ad $A$ che a $B$:

$1^\circ $ modo:Scelgo $A$ in $12k$ modi, poi scelgo $C$ in $3k+6$ modi (tra gli amici di $A$) ed infine scelgo $B$ in $3k+5$ modi(tra i restanti amici di $C$), quindi $12k \cdot (3k+6)\cdot (3k+5)$

$2^\circ $ modo: Scelgo $A$ in $12k$ modi, scelgo $B$ in $12k-1$ modi ed infine, dato che ho scelto $A,B$, rimangono $N$ possibilità per $C$, quindi $12k \cdot (12k-1) \cdot N $

Quindi:

$$12k \cdot (3k+6)\cdot (3k+5) = 12k \cdot (12k-1) \cdot N \iff k=3,N=6$$

Non ti resta che mostrare un esempio che verifica.

[polarized]

Grazie mille Rho! Sto cercando di capire se il mio modo di contarli li conti semplicemente due volte o anche di più ma credo che sia una strada senza fine, senza dubbio la tua soluzione è molto più veloce e intelligente

[Rho33]

Mah, a prima vista (ci ho pensato meno di 10 secondi ), non credo sia strada che spunti. Per $k=3,N=6$ ottieni: $270=7560$ , che di certo non è il doppio, ma $28$ volte il LHS.