2

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?

Hagen von Eitzen
  • 374,180
Gandalf
  • 23
  • Hm, (1) For every vertex (=city) $x$ we count $\deg x=$ difference of "outgoing" and "incoming" roads. We have $\sum\limits_x \deg x=0$, so either $\forall x \deg x=0$ or $\exists x \deg x>0$ – Alexey Burdin May 10 '15 at 13:54

1 Answers1

0

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.

Hagen von Eitzen
  • 374,180