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.

chessboard manhattan move

Given a $2015 \times 2015$ chessboard, a pawn is placed at the bottom left corner. At each turn, the pawn may move one, two, or three squares to the right or to the top, and the goal is to reach the top right corner. The rules are: If the previous move was to the top, then the next move must be to the right. If the previous move was to the right, then the next move must be to the top. The pawn may not move to the left or to the bottom at any point. The difference of length between each two adjacent moves must be exactly 1. How many legal paths are there for the pawn to reach the top right corner?