There is a group of cities with the follwoing rule:
Each city is connected to each city linked by a oneway street:
For any two different cities $A$ and $B$ is it you either go directly from $A$ to $B$ or $B$ to $A$ but not both.
I have to show that there must be a city of which we can get directly half of all the other cities. And i have to show there is one city which can get to all the other cities with the maximum of one intermediate city.
I know that i have to use the pigeonhole principle but i dont know how. Any ideas?
For a city $a$ let $d(a)$ denote the number of streets originating at $a$. Then $\sum d(a)$ is the total number of streets, i.e., $\frac{n(n-1)}{2}$. Since there are $n$ summands, they cannot all be $<\frac{n-1}2$.
For part 2, let $a$ be a city and assume $b\ne a$ cannot be reached from $a$ with at most one intermediate city. Then certainly the conection between these is $b\to a$; also for each street $a\to x$ (so certainly $x\ne b$) we cannot have $x\to b$, hence have $b\to x$. This shows that $d(b)\ge d(a)+1$. We conclude that if $a$ is such that $d(a)$ is maximal, then no such $b$ exists, i.e., all other cities can be reached from $a$ with at most one intermediate city.