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.

Non-adjacent subsets

Find the number of subsets of $n$ such that if $i$ does not belong in the subset then either $i+1$ or $i-1$ belongs to the subset. (Hint: use double recursion, use fibonacci series)

symmetric 2 variable function

Suppose $S = \{1,2,\dots,n\}$ and $f: S \times S \to R$ satisfies the following: $$f(i,j) + f(j,i) = 0 \forall i,j \in S$$ Now for any two number $i,j$, we say that $i$ is superior to $j$ if there exists a $k$ (not necessarily distinct from $i,j$) such that $f(i,k) + f(k,j) \geq 0$. Show that there exists a number $x \in S$ such that $x$ is superior to all elements of $S$.

Combinatorial Proof

Give a combinatorial proof of this identity: $$n(n+1)2^{n-2} = \sum_{k=1}^n k^2 {n \choose k}$$ Solution

Let's say in a class there are $n$ students and you are asked to select one or more students, with the caveat that Joe must be selected. For each student that is selected, the whole class gets 1 dollar. So what is the expected value of the class' income?

Or if you want a non-probabilistic way to think about it, then over all the possible ways to select students, what is the sum of class income in all of those scenarios?

First way to count: Say there are $k \geq 1$ students who are selected (including Joe). There are $n-1 \choose k-1$ ways to choose the students (because Joe must be selected). So this particular way of selecting the students has $k {n-1 \choose k-1} = \frac{k^2}{n} {n \choose k}$ income. So the sum of all income over all scenarios is $\sum_{k=1}^n \frac{k^2}{n} {n \choose k}$

Second way to count: Consider a student, not Joe. How many dollars does he contribute to the total class income? He contributes 1 dollar everytime he is selected, which is $2^{n-2}$ times (because both he and Joe must be selected for him to contribute, so the other $n-2$ students can be chosen freely, selected or not selected). There are $(n-1)2^{n-2}$ contributions from these, because there are $n-1$ students that are not Joe.

But how many dollars did Joe contribute? He ALWAYS contributes 1 dollar for every selection, and there are $2^{n-1}$ selections total. So there are $2^{n-1}$ contributions from Joe.

So the total contribution is $(n-1)2^{n-2} + 2^{n-1} = (n+1)2^{n-2}$