dansparen vormen
Opgave - BxMO 2009 dag 1 vraag 3
Zij $n \ge 1$ een geheel getal. In dorp $X$ wonen $ n$ meisjes en $n$ jongens; elk
meisje hier kent elke jongen. In dorp $Y$ wonen $n$ meisjes: $g_1, g_2, . . . , g_n$, en $2n - 1$
jongens: $b1, b2, . . . , b_{2n-1}.$ Voor $i = 1, 2,..., n$ geldt dat meisje $g_i$ jongens $b1, b2, . . . ,b_{2i-1}$ kent en geen andere jongens. Zij r een geheel getal met $1 \le r \le n. $ In elk van de dorpen wordt een feest gehouden waarbij $r$ meisjes uit het betreffende dorp en $r$ jongens
uit hetzelfde dorp geacht worden met elkaar te dansen in $r$ dansparen. Echter, elk meisje wil alleen dansen met een jongen die ze kent. Noem $X(r)$ het aantal manieren waarop
we $r$ dansparen kunnen kiezen in dorp $X$; noem $Y (r)$ het aantal manieren waarop we $r$
dansparen kunnen kiezen in dorp $Y .$
Bewijs dat $X(r) = Y (r) $ voor iedere $r$.
- login om te reageren
Oplossing
Zij $X(r,n)$ $X(r)$ bij $n$ personen en $Y(r,n)$ $Y(r)$ bij $n$ personen.
We geven een bewijs dat $\forall 1 \leq r \leq n; n,r \in \mathbb{N}$:$ Y(r,n)=X(r,n)$ per inductie.
Inductiebegin: Zij $n=1$. Dan zijn alle mogelijke waarden van $r$ $1$. Het is duidelijk dat $Y(1,1)=X(1,1)=1$.
Inductiehypothese: Veronderstel dat het geldt voor $n$ personen.
Inductiestap: We bewijzen eerst twee lemma's:
Lemma 1: Als $1$ < $r$ <$n$ geldt dat $Y(r,n)=(2n-r)Y(r-1,n-1)+Y(r,n-1)$.
Bewijs: Veronderstel dat $g_n$ meedanst. Dan zijn er voor de overige koppels nog $Y(r-1,n-1$ mogelijkheden en heeft $g_n$ keuze uit $2n-1-(r-1)=2n-r$ jongens. Veronderstel dat $g_n$ niet meedanst. Dan zijn er $Y(r,n-1)$ mogelijkheden. Hieruit volgt het lemma.
Lemma 2: Als $1$ < $r$ <$n$ geldt dat $X(r,n)=(2n-r)X(r-1,n-1)+X(r,n-1)$.
Bewijs: We noemen de jongens van dorp $X$ $j_1,j_2,...,j_n$ en de meisjes $m_1,m_2,...,m_n$. Veronderstel dat geen van $m_n$ en $j_n$ meedansen. Dan zijn er $X(r,n-1)$ mogelijkheden. Veronderstel dat $m_n$ meedanst maar $j_n$ niet. Voor de eerste $r-1$ koppels zijn er dan $X(r-1,n-1)$ mogelijkheden. Voor $m_n$ zijn er nog $n-1-(r-1)=n-r$ mogelijkheden. In totaal zijn er in dit geval dus $(n-r)X(r-1,n-1)$ mogelijkheden. Analoog zijn er evenveel mogelijkheden als $j_n$ meedanst maar $m_n$ niet. Stel nu dat zowel $m_n$ als $j_n$ meedansen. Er zijn $X(r-1,n-1)$ manieren om zonder hen $r-1$ koppels te kiezen. Voor jongen $j_n$ zijn er nu nog $r$ mogelijkheden om een meisje te kiezen: ofwel neemt hij $m_n$, ofwel wisselt hij met één van de andere $r-1$ meisjes met een andere jongen die dan met $m_n$ danst . Er zijn in dit geval dus $r X(r-1,n-1)$ mogelijkheden.
Merk hiervoor op dat we iedere $r$ paren die met elkaar kunnen dansen zo exact \'e\'en keer hebben geteld. Als $j_n$ en $m_n$ dansen, maar niet met elkaar, voeg je wel degelijk hun partners samen in de telling om zo een bijectie te hebben tussen de getelde verzameling van paren.
Er geldt dus dat
\begin{align*}X(n,r)&=2(n-r)X(r-1,n-1)+r X(r-1,n-1)+X(r,n-1)\\&=(2n-r)X(r-1,n-1)+X(r,n-1)\end{align*}, waarmee het lemma bewezen is.
Veronderstel nu dat $1$ < $r$ <$n+1$. Dan geldt dat
\begin{align*}
Y(r,n+1)&=(2n+2-r)Y(r-1,n)+Y(r,n)\\
&=(2n+2-r)X(r-1,n)+X(r,n)\\&=X(r,n+1)
\end{align*}
wegens lemma 1 en 2 en de inductiehypothese.
Veronderstel dat $r=1$. Er geldt dat $X(1,n+1)=(n+1)^2$, aangezien er $n+1$ mogelijke jongens en $n+1$ mogelijke meisjes zijn. Voor $Y(1,n+1)$ geldt dat het totaal aantal mogelijkheden gelijk is aan $\sum^{n+1}_{i=1}(2i-1)=(n+1)^2$, dus $Y(1,n+1)=X(1,n+1)$.
Veronderstel dat $r=n+1$. Er geldt dat $X(n+1,n+1)=(n+1)!$, aangezien er $(n+1)!$ permutaties zijn van $\{ 1,2,...,n+1 \}$, zodat het eerste element van de permutatie aan jongen $j_1$ wordt gekoppeld enzovoort. Voor $Y(n+1,n+1)$ geldt dat er $1$ mogelijkheid is voor $g_1$, twee mogelijkheden voor $g_2$, ..., $2i-1-(i-1)=i$ mogelijkheden voor $g_i$. Dus $Y(n+1,n+1)=(n+1)!=X(n+1,n+1)$.
Hieruit volgt dat ook bij $n+1$ voor alle $1 \leq r \leq n+1$ geldt dat $X(r,n+1)=Y(r,n+1)$, waarmee de inductie compleet is. Q.E.D.