$n$ ragazze e $2n-1$ ragazzi

[karlosson_sul_tetto]

(La vicenda è ambientata nel $\pi$-day 14/03/2016)
In una città A(lbertoronto) ci sono $n$ ragazze e $n$ ragazzi, dove tutte le ragazze conoscono tutti i ragazzi (la conoscenza è reciproca). Invece nella città B(arbarabiasaudita) invece ci sono $n$ ragazze $g_1, g_2, \ldots g_n$ e $2n-1$ ragazzi $b_1,b_2 \ldots b_{2n-1}$ e ogni ragazza $g_i$ conosce $2i-1$ ragazzi, da $b_1$ a $b_{2i-1}$.

In entrambe le città per festeggiare la schiacciante vittoria ottenuta dall'Italia nella (attualmente futura, ma ai tempi dell'evento da poco passata) gara internazionale, si decide di fare un grande ballo. Per questo, in ogni città sceglieranno $r$ coppie composte da un ragazzo e una ragazza in modo che i due si conoscano. (ovviamente, visto che le coppie balleranno contemporaneamente, una persona non può appartenere a due coppie diverse)

Dimostrare il numero di scelte di $r$ coppie nella città A e nella città B coincidono (per ogni $r$).

[RiccardoKelso]

??

Testo nascosto:

Basta fare il conto diretto? Per la città A si hanno $n!$ composizioni possibili delle coppie, mentre per la città B.. La povera $g_1$ ha scelta obbligata conoscendone solo uno, quindi a $g_2$ ne rimangono 2 possibili (essendo i ragazzi conosciuti "ordinati"); mostriamo che ogni ragazza ha una scelta possibile in più della precedente:
Scelte possibili per la ragazza $g_i$:$2i-1-(i-1)=i$, cioè i ragazzi conosciuti meno quelli già scelti.
Scelte possibili per la ragazza $g_{i+1}$:$2(i+1)-1-(i+1-1)=i+1$.
A questo punto (o anche prima, dato che fare il confronto tra due ragazze successive era inutile ) per calcolo diretto si ha che le possibili composizioni di coppie nella città B sono anch'esse $n!$.

[karlosson_sul_tetto]

Il problema non chiede di far ballare tutte le ragazze di entrambe le città, ma solo $r$. In questo caso hai dimostrato che se $r=n$ allora coincidono, ma se $r=$, chessò, $3$ devi prendere solo tre ragazze (per esempio $g_2, g_{15}, g_{16}$) e vedere che per la somma degli accoppiamenti possibili per ogni terna è la stessa.


Visto che ho aggiustato un typo, approfitto dell'edit per confermare quello che c'è scritto nel post di sotto: le ragazze e i ragazzi in entrambe le città sono tutti diversi tra di loro.

[RiccardoKelso]

Ora tutto ha senso anche nella mia testa, avevo bisogno di qualcuno che esplicasse

Quindi, per capirsi (o meglio, per far capire me), nella città A con $r=1$ abbiamo $n^2$ coppie possibili o le donnine sono indistinguibili?
EDIT Ok, non c'è bisogno di replicare in quanto spero di esserci arrivato autonomamente :'D

EDIT2,3,etc..:

Testo nascosto:

****
***
***
**
**
*
*
VS
****
****
****
**** ($n=4$)
Oppure, per la città B, traslando qualcosina
*
**
***
****
***
**
*
Porta da qualche parte l'approccio grafico? Assegnando righe e colonne a ragazzi e ragazze e considerando una coppia come annerimento di una casella, il che rende inaccessibili tutte le caselle che hanno in comune con un'annerita una riga o una colonna, e robbe così

Non ho davvero la minima idea di come formalizzare, ma..

Testo nascosto:

Considererò $n=4$ per i disegni, ma non particolarizzo nulla. Come detto, utilizziamo un approccio grafico: ad ogni colonna corrisponde una ragazza e ad ogni riga un ragazzo; una ragazza conosce tutti i ragazzi che ci sono sulla sua colonna, il fatto che siano in coppia insieme viene rappresentato annerendo la casella corrispondente all'incontro riga/colonna.
Città B
****
***
***
**
**
*
*
Città A
****
****
****
****
Traslando si ottiene l'equivalente città B'
*
**
***
****
***
**
*
I possibili modi di annerire $r$ caselle in modo che non ce ne siano due annerite sulla stessa riga o sulla stessa colonna corrispondono alla richiesta del problema. Parlando della città B' (e quindi anche della B): per ogni casella tale che venendo annerita oscuri un numero $x$ diverso da $2n-1$ di caselle, ne esiste un'altra che ne oscura $y$ tale che $x+y=2(2n-1)$, per via della figura. Questo dimostra che per $r=2$ la tesi è verificata. Per $r=1$ lo è in quanto il numero totale di caselle è il medesimo. Come proseguire? boh

[bern-1-16-4-13]

LEMMA:
$$\left(\frac{n!}{\left(n-r\right)!}\right)^2=r\sum_{k=r}^n\left(\left(\frac{\left(k-1\right)!}{\left(k-r\right)!}\right)^{2}\left(2k-r\right)\right)\ \ \ \ \ \forall r\leq n:\ \ r,n\in\mathbb{Z}^+.$$

Come si dimostra?