Tricolored polygon

Given a regular $(3n+2)$-gon, the vertices are colored with red, blue, or green such that there are $n+1$ green points, $n+1$ blue points, and $n$ red points. Prove that there exists a line going through a blue point and a green point, such that on one side of the line there are $k$ points of each color, and on the other side there are $(n-k)$ of each color (with $k \geq 0$).

Solution

First we claim that there is a way to pair each blue point with a green point such that the segments formed by each pair is non-intersecting. Proof:

Delete all the red points for now, so we are left with polygon with $(n+1)$ blue and green points each. Take any adjacent pair of a blue point and a green point, pair them, and then delete them. Now we are left with $n$ blue and green points each. Recursively apply this procedure until we are done. It's easy to see that the resulting segments are non-intersecting.

Now that we have $n+1$ such segments, label the points $(b_1, \dots, b_{n+1}, g_1, \dots, g_{n+1})$ where $b_i$ is a blue point that is paired with $g_i$. Let $S_i$ denote the segment formed by $b_ih_i$. Pick an arbitrary red point $R$. We define the following terminology: each segment divides the polygon into two. The "good" side of the segment is the side that contains $R$.

Since no two segments can intersect, then for two different segments $S_i,S_j$, one is fully on the good side of the other. If $S_i$ is fully contained in the good side of $S_j$ then we say that $S_j$ "covers" $S_i$. Note that for any two segments, if $S_i$ covers $S_j$ then $S_j$ does not cover $S_i$, and one necessarily covers the other.

Note the following properties. If $S_a$ covers $S_b$ and $S_b$ covers $S_c$ then $S_a$ covers $S_c$. Conversely, if $S_a$ and $S_b$ both cover $S_c$ then either $S_a$ covers $S_b$ or $S_b$ covers $S_a$. So we may define the relationship called "immediate covering." We say $S_a$ immediately covers $S_b$ if $S_a$ covers $S_b$ and there's no other $S_c$ such that $S_a$ covers $S_c$ and $S_c$ covers $S_b$.

Consider the graph with $n+1$ vertices $1,2,\dots,n+1$ and the edges where $i \to j$ if $S_i$ immediately covers $S_j$. Each segment can only be immediately covered by at most one other segment, so this graph is a tree. It cannot be a forest because for each root of each tree, one necessarily covers the other so there can only be one true root. Define the "height" of each node to be the distance between node $i$ to it's farthest leaf. So every leaf has height zero. If $i$ is a leaf and $S_j$ immediately covers $S_i$ (and only $S_i$), then $j$ has height 1, and so on. If a node has several children of differing heights, then the height of the node is 1 plus the maximum of its children's height.

Now also for each $i$, define $A_i$ to be the number of red points that are located on the good side of $S_i$. Define $B_i$ to be the number of descendants of $i$ in the above-mentioned graph. So, our aim is to show that there exists an $i$ such that $A_i = B_i$, because this would mean that on the good side of $S_i$, there are precisely $A_i$ red points, and $B_i$ segments, each of which contains $B_i$ blue points and $B_i$ green points. Now suppose, in our configuration, there is no $i$ such that $A_i = B_i$.

Our claim now is that for each $i$, $A_i > B_i$. We prove this by induction on the height of the nodes.

We start by looking at the leaves. If there's any leaf $i$ with $A_i = 0$ then there is a contradiction, because $B_i = 0$. So for each leaf $i$, $A_i \geq 1 > 0 = B_i$.

Now suppose that $A_i > B_i$ (which means $A_i \geq B_i + 1$) for each node of height $0, 1, \dots, k$, then let $S_a$ be a node of height $k+1$, and let its children be $S_{b_1}, \dots, S_{b_m}$. Its children has height at most $k$, so for each $i$, $A_{b_i} \geq B_{b_i}$ holds. Now, each red point on the good side of $S_{b_i}$ is also on the good side of $S_a$, therefore $$A_a \geq A_{b_1} + \dots + A_{b_m} \geq (B_{b_1} + 1) + \dots + (B_{b_m}+1) = m + \sum B_{b_i} = B_a$$ The first inequality is due to the fact that each red point in $A_{b_i}$ must be contained in $A_a$ as well (although there may be more red points in $A_a$. The second inequality is from induction hypothesis. The third inequality is by construction of the graph and definition of $B_a$, because the number of descendants of $S_a$ can be counted by summing the number of descendant of children, plus each of the children themselves.

So we established that $A_a \geq B_a$, but because we assumed that there is not $A_i = B_i$, then $A_a > B_a$. Thus, by induction on the height of each node, we can claim that $A_i > B_i$ for each $i$ in the whole graph.

Now consider the root node $r$. We concluded that $A_r > B_r$. But $A_r$ is the number of red points on the good side of $S_r$, which is at most $n$. $B_r$ is the number of descendants of $S_r$, which is $n$. Contradiction.

Thus there must be an $i$ such that $A_i = B_i$ and that is our desired segment.

A tale of two cities

In an island with 257 cities, there are 2018 railroad segments such that each segment connects exactly 2 cities, and each pair of cities are connected by at most 1 segment. A group of 10 cities is called "clustered" if each pair of those 10 is connected by a segment.

Prove that there exist 2 unconnected cities that we can connect without increasing the number of clustered groups.

Solution

Proof by contradiction. Suppose we cannot connect two cities without increasing the number of clustered groups.

Let $n=257$ be the number of cities. Take all possible groups of 10 cities, ${n \choose 10 }$ of them, and count how many segments there are among them. Of course, if the group is clustered, it should have ${10 \choose 2} = 45$ segments. Let $S$ be the sum of unconnected pairs, over all possible groups of 10 cities.

Now let us count $S$ in a different way. Take 2 connected cities $A$ and $B$. The segment $AB$ contributes to $S$ only when the chosen group of 10 cities include $AB$, so this segment is counted ${n-2 \choose 8}$ times. Because there are 2018 segments, then $S$ must be:

$$S = {n-2 \choose 8}.(2018)$$

Note that $2018 < 2020 = 8n-36$, so $S < {n-2 \choose 8}.(8n-26)$. That means, on average, there are $S / {n \choose 10 }$ segments.

Spanning set

Let $S = \{0,1,2,\dots,10\}$.

A set of numbers $A \subset S$ is called "spanning" if the set $\{ x, x+1, x+2, x+3 \mod 11 | x \in A \} = S$.

And a set of numbers $B \subset S$ is called "potentially spanning" if there is an integer $k$ such that the set $\{kb \mod 11 | b \in B \}$ is spanning.

Prove that every subset of $S$ with four elements are potentially spanning, and prove that there exists a subset of $S$ with three elements that is not potentially spanning.

Solution First, we show that there is a subset of three elements that is not potentially spanning.

Note that for a set to be spanning, it has to be $\{c,c+4, c+8\}$ for some $c$ (here we assume everything is modulo 11, so we don't write it for notational simplicity). This is because the maximum distance between two adjacent element is 4, so the distances between 3 elements must be 4+4+3 (or its rotation).

Now we claim that a set $\{x,y,z\}$ is potentially spanning if and only if there exists $r \neq 0$ and $s$ such that $\{x,y,z\} = \{r+s, 2r+s, 3r+s \mod 11\}$. First, clearly if a set is spanning, then all of its "rotations" are also spanning sets. Likewise, if a set is potentially spanning, then all of its rotations are also potentially spanning. So wlog we may assume that $s=0$. Then the set $\{r,2r,3r\}$ is potentially spanning because we can always take $k = 4r^{-1} \mod 11$ so that $\{kr,2kr,3kr\} = \{4,8,12=1\}$ a spanning set. The inverse modulo is guaranteed to exist because 11 is prime and $r \neq 0$.

Now the other direction. Suppose $\{x,y,z\}$ is potentially spanning, such that $\{kx,ky,kz\}$ is spanning. As we've established above, it must have form $\{c,c+4, c+8\}$ for some $c$. Thus we can take $r = 4k^{-1} \mod 11$ and $s = (c-4)k^{-1} \mod 11$ so that $\{k(r+s),2kr,3kr\} = \{4+ks,8+ks,12+ks\} = \{c,c+4,c+8\}$.

So we have shown that the potentially spanning sets are generated by (and only by) the number of $(r,s)$ pairs we can choose. There are 10 choices for $r$ and 11 for $s$, so there are at most 110 potentially spanning sets. We say at most because some choices of $r$ and $s$ may "collide" (result in the same spanning triplet). However, there are ${11 \choose 3} = 165$ possible triplets, so there are some triplets that are not generated by the $(r,s)$ construction above and thus not potentially spanning.

Now we show that a subset $B = \{b_1,b_2,b_3,b_4\}$ is always potentially spanning. Note that if any three of $b_i$s form a potentially spanning triplet then $B$ is potentially spanning. In particular, if $B$ contains an arithmetic sequence modulo 11 then $B$ is potentially spanning. So we assume that $B$ is free from arithmetic progression.

Now let $d_i = b_{i+1} - b_i$ (of course we mean $b_5 = b_1$. Then among all four $d_i$s, let $d$ be the maximal distance. If the maximal distance is 4, then we are done because $B$ itself is spanning. So we assume that the maximal distance is at least 5. Wlog, we may assume that this maximal distance is $d_4$ and that $b_1 = 0$. So this means $0=b_1 < b_2 < b_3 < b_4 = 11-d$ and $b_i$ must not contain arithmetic sequence. It's easy to see that the only possible combinations are:

Case 1: $d=5$, so $0=b_1 < b_2 < b_3 < b_4 = 6$. The only combinations are $\{0,1,4,6\}, \{0,1,5,6\},\{0,2,5,6\}$. All the other combinations contain an arithmetic sequence. But in the first two cases, we can take $k=8$ to get: $\{0,4,8,10\}, \{0,4,7,8\}$ which contains arithmetic sequence thus potentially spanning, and for the third case we can take $k=3$ to get $\{0,4,6,7\}$ which is spanning.

Case 2: $d=6$, so $0=b_1 < b_2 < b_3 < b_4 = 5$. The only combinations are $\{0,1,4,5\}$ and $\{0,2,3,5\}$. We can take $k=4$ to get $\{0,4,5,9\}$ and $k=2$ to get $\{0,4,6,10\}, both spanning sets.

Case 3: $d=7$, so $0=b_1 < b_2 < b_3 < b_4 = 5$. The only combination is $\{0,1,3,4\}$. We can take $k=5$ to get $\{0,4,5,9\}$, a spanning set.

And there is no way to have $d > 7$ and still fitting $b_2$ and $b_3$ without getting an arithmetic progression. So our proof is complete.

Various double counting problems

These problems can all be solved by the double counting principle, that is, to count the same object two different ways and assert that those must match.

Suppose $n > 4$. Let $A_1, A_2, \dots ,A_k$ each be a set of $n$ integers, where $k \leq 4^{n-1} / 3^n$. Show that we can color each integer with one of the four colors so that each set contains integers of 4 different colors.

In a party attended by $n$ people, there were a number of handshakes. A group of 10 persons is called "tight" if each person shook hands with the other 9. It is known that we cannot add another handshake (two people who didn't shake hands now shaking hands) without increasing the number of tight groups. Prove that the number of handshakes is at least $8n-36$

In a class with many students, we choose 2016 committees among them. Each committee has 11 students, and each student may belong to multiple committees. Prove that there is a way to choose some of the students so that each committee has at least one chosen and one unchosen student.

Paintings and colors

In a museum there are $n$ paintings, each of which was painted with at least 3 colors. The total number of colors from all paintings is $m << n$. The average number of colors per painting is $s$.

If we choose $k$ paintings at random, what's the expected number of colors that we get? What's the maximum and minimum value of this expectation, for a fixed color-painting configuration, but for varying choices of paintings?

If we choose $l$ colors at random, what's the expected number of paintings that can be replicated with those colors? (It means each painting is painted only with those colors). Again, what's the maximum and minimum value of this expectation?

Remark: by choosing $m,n,s,k,l$ judiciously we can write problems such as: show that we can choose $k$ paintings such that the number of colors among those paintings is at most / at least $x$.

Solution

There are $N = {n \choose k}$ ways to choose paintings. For each choice of paintings, we tally up the total number of colors produced, and then we sum it over all possible choice of paintings. Let $S$ be this sum of total number of colors. The expected number of colors is then $S / N$.

Suppose the color $c$ is used by $p_c$ paintings. We wish to count the contribution of $c$ towards $S$. The color contributes one point to $S$ for each choice of paintings that includes at least one of the $p_c$, and zero otherwise. That means now the question is, how many ways can we choose $k$ out of $n$ paintings such that at least one of them comes from the $p_c$ paintings? There are $N$ ways total to choose, and there are ${n-p_c \choose k}$ ways to choose such that none of the $p_c$ paintings are chosen, so the total number is: $${n \choose k} - {n-p_c \choose k}$$ So: $$S = \sum_c {n \choose k} - {n-p_c \choose k}$$ where the sum runs over all $m$ colors. This expression is exact. What follows from this point on is an attempted to upper/lower bound $S$, and it may not be exact, although we will give examples to show that the bound is tight.

Now consider the function $f(t) = {n \choose k} - {n-t \choose k}$, defined over $t \in [1,m]$ (the color must be used in at least 1 painting, and at most $m$ paintings obviously). We are given that $m << n$ so it's safe to assume that ${n-m \choose k} > 0$. The convexity and concavity analysis depends on if $k$ is even or odd. For now, assume $k$ is odd. The analysis if $k$ is even is very similar.

The function $(n-t)(n-t-1)\dots (n-t-k+1)$ is convex in the interval $(0,n-k-1)$, and since $m << n$, it is convex in the interval $[1,m]$. That means $f(t)$ is concave. On the other hand, we know that the average number of colors per painting is $s$, so there are $sn$ distinct painting-color pairs, so $\sum_c p_c = sn$.

By Jensen, the maximum of $\sum_c f(p_c)$ is achieved if all the $p_c$ is the same, that is $sn/m$. In that case, $$\frac{S}{N} \leq \frac{\sum_c {n \choose k} - {n-p_c \choose k}}{n \choose k} = \frac{ m({n \choose k} - {n-\frac{sn}{m} \choose k}) }{n \choose k}$$ For example, for $n=50,k=3,m=25,s=10$, we have $S/N = 19.8$. So we can write a problem such as: show that we can choose 3 paintings such that between them we get at most 19 colors.

In order to find the lower bound, by majorization theorem, the minimum of $\sum_c f(p_c)$ is achieved by $[p_c] = [m,m,m,\dots,m,r,1,\dots,1]$ because that's the configuration that majorizes everything else. The number of $m$s, and $1$s and the value of $r$ (if needed) will have to depend on the particular problem setup, to make sure the following two conditions are met:

1. $\sum_c p_c = sn$ 2. The number of elements in $[p_c]$ is $m$.

For example, in the $n=50,k=3,m=25,s=10$ case above, we would have $[p_c] = [25,25,\dots,25,20,1,1,\dots,1]$ where there are 19 25s and 6 1s. Then: $$S \geq 25 \times {50 \choose 3} - 19 \times {50-25 \choose 3} - 1 \times {50-20 \choose 3} - 6 \times {50-1 \choose 3}$$ $$\frac{S}{N} \geq 16.9$$ So we can say: show that we can choose 3 paintings such that between them we get at least 17 colors.

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$.