Dancing partners

In a party with $n$ boys and $n$ girls, each boy dances with some girls and vice versa. (No pair of boy and girl dance more than once). There are $n^2-n+1$ dances that occurred throughout the night. Show that we can pair each boy with each girl so that everyone is paired with someone he/she danced with.

Solution

The key fact is because the number of dances is more than $n^2-n$. If it were exactly $n^2-n$, we could have a situation where $n-1$ boys danced with all the girls, and one boy never danced, and this effectively blocks that boy from being paired correctly.

Suppose that there is no way to pair them correctly. That is, for every given pairing, there's always a pair that did not dance. For each pairing, we define the score of said pairing to be the number of pairs that actually danced. This means a legal pairing is the one with score $n$.

Now let $S$ be the sum of all the scores of all possible pairings. Our contrapositive hypothesis is that all pairings have a score of at most $n-1$, so $S \leq (n-1)n!$ (because there are $n!$ possible pairings).

On the other hand, for each dance that happened throughout the night, we want to count how many points it contributes to $S$. Suppose the dance happens between boy $B$ and girl $G$. Then it contributes one point of score whenever the pairing pairs $B$ and $G$. In other words, there are $(n-1)!$ such pairings (because one pair is fixed and we have complete freedom to pair the other $n-1$ boys and $n-1$ girls. So the total number of score is: $$S = (n^2-n+1)(n-1)! > (n^2-n)(n-1)! = (n-1)n!$$ A contradiction.

Tournament, number of dominated players

In a tournament with $n$ people, each player plays against each other player exactly once, with each game results in a win or a loss (no draw).

If we choose $A$ a set of 5 players at random, let $X_3$ denote the number of players not in $A$ that lose to exactly 3 players in $A$. What's $E[X_3]$? What about $E[X_4]$?

Remark: by choosing $n$ carefully, we can write problems such as: Show that we can choose $A$ and $B$ disjoint groups containing 5 players each so that each player in $B$ loses to exactly 3 players in $A$. The number 5 can be replaced by other numbers too.

Solution

There are $N = {n \choose 5}$ ways to choose set $A$. Of all those choices, we sum up the total number each player loses to exactly 3 players in $A$.

That is, for a given player $x$ that loses $p_x$ times, he contributes to ${p_x \choose 3} {n-p_x-1 \choose 2}$ to the total sum. This is because we can choose ${p_x \choose 3}$ ways to form the part of $A$ that beats $x$, and ${n-p_x-1 \choose 2}$ ways to form the part that doesn't beat $x$, and these are mutually exclusive and independent. Note that if $p_x < 3$ that number is zero as expected.

So the expected value is: $$E[X_3] = \frac{\sum_x {p_x \choose 3} {n-p_x-1 \choose 2}}{n \choose 5}$$ Because $f(t) = {p_x \choose 3} {n-p_x-1 \choose 2} - \frac{t(t-1)(t-2)(n-t-1)(n-t-2)}{3! 2!}$ is a convex function in $t$, we can bound this number by Jensen, noting that $\sum_x p_x = n(n-1)/2$ $$E[X_3] > \frac{{(n-1)/2 \choose 3} {n-(n-1)/2-1 \choose 2}}{n \choose 5}$$ By choosing $n$ carefully, or replacing the numbers 5 and 3 accordingly, we can write problems like: in such and such tournament, show that we can choose 5 players into group $A$ and 5 other players into group $B$ such that each player in group $B$ loses the majority of his games against players in group $A$, or each player in group $A$ wins the majority of his games against players in group $B$.

But finding $E[X_4]$ is a wholly different issue. We can still use the fact that $$E[X_4] = \frac{\sum_x {p_x \choose 4} {n-p_x-1 \choose 1}}{n \choose 5} = \frac{\sum_x {p_x \choose 4} (n-p_x-1)}{n \choose 5}$$ but unfortunately now $f(t) = {t \choose 4} (n-t-1)$ is a concave function, so we can't use Jensen. We can still use majorization theorem however, noting that $\sum_x p_x = n(n-1)/2$. If we want to find a sequence of $p_i$ that's absolutely majorized, we can say that: $$(n-1, n-2, \dots, 1, 0) \succ (p_1, p_2, \dots, p_n)$$ which must be true in the most extreme example that each player has an absolute skill level and each victory is transitive. However, computing $E_4$ in that case is difficult. $$E[X_4] > \frac{1}{n \choose 5} \sum_{k=0}^{n-1} {k \choose 4} (n-k-1)$$ which can be done analytically because the sums of $\sum k, \sum k^2, dots \sum k^5$ can all be computed via telescoping arguments.

If you want to be lazy, you can also say that $(n(n-1)/2,0,\dots,0)$ majorizes everything, but that lower bound is probably lame.

Why did I mention this? Because this type of analysis eventually opens up to problems like:

Show that we can choose $A$ and $B$ such that each member of $B$ loses at least 3 times against $A$, or that players from $A$ wins at least $22$ times against $B$, and so on.

What about the number of victories from $A$ to $B$ though? If we label this quantity $V$, then $E[V] = E[X_1 + 2X_2 + 3X_3 + 4X_4 + 5X_5]$, each of which can be evaluated but the even terms are ugly. $E[X_2]$ is not that bad but $E[X_4]$ is definitely not something you want to do too often.

However, there's a faster way to calculate $E[V]$. By symmetry we know it would be $25/2$, because for every choice of $A$ and $B$, there's an equal probability of choosing $B$ and $A$, and the sum of those victories must be 25.

A related problem from Iran Team Selection Test 2008/6.)

Suppose 799 teams participate in a tournament in which every pair of teams plays against each other exactly once. Prove that there exist two disjoint groups $A$ and $B$ of 7 teams each such that every team from $A$ defeated every team from $B$.

From a friend

From a friend

If $f(x) = \sec(x^{333})$ then find $f^{666}(x)$ Where $f^n(x)$ represents the $n$-th derivative of a function.

Solution

At first this looks crazy but we quickly notice that a lot of terms in the 666-th derivative will evaluate to zero at $x=0$. More precisely, the first derivative contains factors $\sec(x^{333}), \tan(x^{333}),$ and $x^{332}$.

The tangent and the $x^n$ factors evaluate to zero, but the secant factor evaluates to 1. So all we need to figure out is, at each derivative step, which terms will affect the final derivatives.

To make it clearer, let's generalize into: $f(x) = \sec(x^n)$. $$f^1(x) = nx^{n-1} \sec(x^n) \tan(x^n)$$ $$f^2((x) = n^2x^{2n-2} \sec(x^n) \tan^2(x^n) + n(n-1)x^{n-2} \sec(x^n) \tan(x^n) + n^2 x^{2n-2} \sec^3(x^n)$$ The first term will continue to have higher derivatives with higher powers of $x$ and $\tan(x^n)$. Ditto for the second term. What we need to worry about is only the third term.

Tangents and secant

On a circle $L_1$ centered at $O$, we draw two points $A$ and $B$ that are not diametrically opposite. The tangents at $A$ and $B$ meet at $P$. Circle $L_2$ are created with $OB$ as the diameter. $L_2$ and $AB$ intersect at $B$ and $Q$. Show that $Q$ lies on $OP$.

four tangent circles

Given four circles: $L_1,L_2,L_3,L_4$ such that $L_1$ is tangent to $L_2$ at $X$, $L_2$ is tangent to $L_3$ at $Y$, $L_3$ is tangent to $L_4$ at $Z$ and $L_4$ is tangent to $L_1$ at $W$. All tangencies are outside (the circles do not overlap each other other than at the points of tangency).

Show that $X,Y,Z,W$ all lie on a circle.

Excircle and circumcircle

In $\triangle ABC$, the $L_1$ be the excircle with respect to $AB$. It touches $CA$ and $CB$ and $M$ and $N$. The circle centered at $C$ and passing through $M$ and $N$ intersects $AB$'s extension at $P,Q$. Show that $L_2$ the circumcircle of $\triangle CPQ$ is tangent to $L_1$, and that the point of tangency between $L_1$ and $L_2$, the point of tangency between $L_1$ and $\triangle ABC$, and $C$ all lie on one line.

Solution Let $X$ be the tangency point of $L_1$ and $AB$. Let $CX$ meets $L_1$ in $Y_1$ and $CX$ meets $L_2$ in $Y_2$. We shall establish that $Y_1 = Y_2$.

Let $C'$ be the diameter of $L_2$ and let $CC'$ meets $AB$ (or its extension) at $D$. Because $CP = CQ$ then it's easy to see that $CD \perp PQ$. Let $s = CM = CN = CP = CQ$.

By power point on $L_1$: $$CX.CY_1 = CM^2 = s^2$$.

By similarity of $\triangle CXD \sim \triangle CC'Y_2$ and $\triangle CC'P \sim \triangle CDP$ : $$CX.CY_2 = CD.CC' = CP^2 = s^2$$

Thus $CY_1 = CY_2$ which means $Y_1 = Y_2$. Now we know that $L_1$ meets $L_2$ in at least one point $Y = Y_1 = Y_2$. Suppose they meet in another point $Z \neq Y$

Let $CZ$ meets $L_1$ in $CZ$ and $X_1 \neq X$. By power point we again have:$CX_1.CZ = s^2$.

Let $CZ$ meets $AB$ in $X_2$. Similar as above, because $Z \in L_2$, we can repeat the similarity argument to establish: $CX_2.CZ = s^2$. This means that $CX_1 = CX_2$, thus $X_1 = X_2 \in L_1, AB$ but that is a contradiction because $L_1$ is only tangent to $AB$, and can only meet $AB$ at $X$.

Now that we've established the tangency between $L_1$ and $L_2$, it's clear that $C,X,Y_1/Y_2$ all lie on one line from the proof.

Circumcenter and 3 circumcircles

Given an acute triangle $ABC$ and its circumcircle is centered at $O$ and has radius $R$.

$AO$ meets the circumcircle of $\triangle OBC$ at $X$, $BO$ meets the circumcircle of $\triangle OAC$ at $Y$, and $CO$ meets the circumcircle of $\triangle OAB$ at $Z$.

Show that $$AX + BY + CZ \geq 9R$$

Determine when equality occurs.

Solution

Let $AX$ meets $BC$ at $D$. And let $OO'$ be the diameter of the circumcircle of $\triangle OBC$, and let $M$ be the intersection of $OO'$ and $BC$.

$$\frac{OX}{OO'} = \frac{OM}{OD}$$ $$OX.OD = OO'.OM = OC^2 = R^2$$ $$AX = AO + OX = R + \frac{R^2}{OD} = \frac{R(R + OD)}{OD} = R\frac{AD}{OD}$$

If we define $E$ as the intersection of $BY$ and $AC$, and $F$ as the intersection of $CZ$ and $AB$, then similarly: $$BY = R \frac{BE}{OE}$$ $$CZ = R \frac{CF}{OF}$$

So: $$AX + BY + CZ = R(\frac{AD}{OD} + \frac{BE}{OE} + \frac{CF}{OF})$$ $$\geq \frac{9R}{\frac{OD}{AD} + \frac{OE}{BE} + \frac{OF}{CF}}$$ But $OD / AD = A_{\triangle OBC} / A_{\triangle ABC}$ and so on, so: $$\frac{OD}{AD} + \frac{OE}{BE} + \frac{OF}{CF} = 1$$ $$AX + BY + CZ \geq 9R$$

and equality happens when the area of $\triangle OBC$ is exactly $\triangle ABC / 3$. And this happens only when $O$ is the centroid of $\triangle ABC$, which means $ABC$ is an equilateral.