In country some cities are connected by oneway flights( There are no more then one flight between two cities). City $A$ called "available" for city $B$, if there is flight from $B$ to $A$, maybe with some transfers. It is known, that for every 2 cities $P$ and $Q$ exist city $R$, such that $P$ and $Q$ are available from $R$. Prove, that exist city $A$, such that every city is available for $A$.
Problem
Source: All Russian Olympiad 2017,Day1,grade 9,P1
Tags: combinatorics
tarzanjunior
03.05.2017 15:14
I will proceed by induction. It is obviously true for $3$ flights. Assume it is true for $m$ flights. Let there exist a city $A$ such that all the other towns are available from $A$. We add another city $B$. Then, there is a town , say $C$ such that both $A$ and $B$ are available from $C$.From our previous assumption, $C$ is available from $A$. Since $B$ is available from $C$, $C$ is available from $A$. Hence the city $A$ exists by induction hypothesis. Someone pls. check my solution.
anantmudgal09
03.07.2017 17:23
@above, your solution seems to rely on "adding a new town", however that loses generality. Perhaps you meant to take away a city and then apply induction hypothesis to the remaining graph but that still fails since we do not know whether the induced graph satisfies the original condition. RagvaloD wrote: In country some cities are connected by oneway flights( There are no more then one flight between two cities). City $A$ called "available" for city $B$, if there is flight from $B$ to $A$, maybe with some transfers. It is known, that for every 2 cities $P$ and $Q$ exist city $R$, such that $P$ and $Q$ are available from $R$. Prove, that exist city $A$, such that every city is available for $A$. Look at the city with the maximal "outreach"; call it $A$. We show this is the desired city; indeed, if this is not the case then there is a city $B$ which is unavailable from $A$. Hence, a city $C$ exists for which both $A, B$ are available, so all cities available for $A$ are also available for $C$. However, with the addition of the availability of $B$; we contradict the maximality of $A$'s outreach. $\blacksquare$
rafayaashary1
03.07.2017 18:03
Consider the Category $\mathcal{C}$ whose objects are cities and whose morphisms represent the possibility of flight (maybe with some transfers) between some cities. Aside from the necessary identity morphisms (which do not harm the combinatorial interpretation of the problem), $\mathcal{C}$ is entirely generated by the direct flights above. In particular, we can identify the cities with their equivalence classes under isomorphism to obtain a poset category $\mathcal{C}'$. We simply want to show the existence of an initial object in $\mathcal{C}$, which is an initial object in $\mathcal{C}'$ thanks to the obvious functor $F:\mathcal{C}\to\mathcal{C}'$. The proof I found is basically the above though, so I don't think there's any real reason to use Category stuff on this problem.
mathuz
08.11.2017 13:53
It's equivalent to Friendship theorem
vsathiam
06.01.2018 22:10
From the condition that for every two cities P and Q, there exists a city R such that P and Q are available from R, it follows that for $n \geq 3$, there exists a city A with two distinct available cities P and Q.
Let the cities in the country be called A = $\{ A_1, A_2, \dots A_n \}$ and the set of available cities to $A_i$ be $A_{i_C} = \{ C_{i_1}, C_{i_2}, \dots C_{i_k} \} \subset A$.
Suppose on the contrary that there does not exist a city $A_i$ such that every city in $A - \{A_i\}$ is available for $A_i$. Let $A_m$ be the city whose set $A_{m_C}$ is maximal over all $A_i$, and D be a city that is not available to $A_m$.
From the second condition, it follows that there exists a city for which $A_m$ and D are available.
If this city, which we call $A_{m'}$ is among $A_{m_C}$, then it follows that $ \mid A_{m'_C} \mid \geq \mid A_{m_C} \mid + 2$ since $A_m$, all of $A_m$'s available cities, and D are available to $A_{m'}$, which a contradiction of $A_m$'s maximality.
If $A_{m'}$ is not among $A_{m_C}$, then $\mid A_{m'_C} \mid \geq \mid A_{m_C} \mid + 2$ since $A_m$, $A_{m_C}$, and D are all available to $A_{m'}$, which is also a contradiction.
Hence, it follows that a city among A such that every other city in A is available to it exists.
Delray
06.01.2018 23:19
Let $S$ be the set of cities. Let each city $C_i\in S$ be assigned a value $c_i$. Basically, the city $C_i$ is available from $C_j$ if $c_j\mid c_i$. The second problem condition gives that for every $C_i, C_i \in S$, we have that there exists $C_m\in S$ for which $c_m\mid \gcd (c_i,c_j)$. Now let $C_{t_1}\in S$ be a city for which $c_{t_1}\mid\gcd(c_1, c_2)$. Let $C_{t_2}\in S$ be a city for which $c_{t_2}\mid\gcd(c_{t_1}, c_2)$. Continue in this process until we get $C_{t_{n-1}}$, and we are done.
Garfield
07.01.2018 00:27
Suppose opposite.Let $m$ be maximum number of cities that are available for some city,let's say city $A$,$m\neq n-1$ where $n$ is number of cities.Take some city that isn't available for $A$,let's say $B$.Now there is a city $C$ such that both $A$ and $B$ are available for $C$ but that means that $C$ has at least $m+1$ cities available (all cities available for $A$ + city $B$),contradiction.
ayan.nmath
09.06.2018 09:09
RagvaloD wrote: In country some cities are connected by oneway flights( There are no more then one flight between two cities). City $A$ called "available" for city $B$, if there is flight from $B$ to $A$, maybe with some transfers. It is known, that for every 2 cities $P$ and $Q$ exist city $R$, such that $P$ and $Q$ are available from $R$. Prove, that exist city $A$, such that every city is available for $A$. Solution. Let $n$ be the number of cities(vertices), $A$ be the city from which maximum no. of cities are available and $D(A)$ be the set of the cities which are available from $A$ (note that $A\notin D(A)$) and for a pair of cities $(I,J),$ define it's associate as the city from which both are available. For $n=3$ it is trivial. For the sake of contradiction, let $m$ be the least $n$ for which the result is false. If $X\notin D(A),$ note that the associate of any pair $(X,\star)$ is not in $D(A)$. Consider $K=\{\text{associate of }(I,J)\mid I,J\in D(A)\},$ if $D(A)\cap K=\varnothing,$ then we can delete any city in $D(A),$ if $|D(A)\cap K|\ge 1,$ we can delete any element of $D(A)\cap K$, so the result is also true for $n=m-1,$ which contradicts the minimality of $m.$ $\blacksquare$
triangle112
03.07.2020 23:58
I have induction solution based on the number of cities, so can anyone check it because I'm not good in combo?: Base case: $n=3$, trivial by the problem statement Suppose that for ANY configuration of flights between $k$ cities that obeys the condition there exists town $a_i$ that is connected to any other town. Now, suppose that we add town $a_{k+1}$. If there is a flight $a_i \rightarrow a_{k+1}$, we are done, and similarly if $a_{k+1} \rightarrow a_i$. By the statement there exists town $a_j$ that is connected to both $a_i$ and $a_{k+1}$ and that town is the desired one ($a_i$ is connected to $a_j$ if there exists the flight $a_i \rightarrow a_j$) .
chakrabortyahan
14.10.2023 19:55
Let $ A$ have a maximal number of available cities. Name the set of available cities from $A$ as $f(A)$. Now take a city $B$ which is unavailable from $A$ and there is another city $C$ so that $A$ and $B$ are available from $C$.Again $B$ is not available from any city of $f(A)$ as then it would available from $A$ and as $B$ is available from $C$ so $C\notin f(A)$ and so $A\cup B \cup f(A)$ is the set of available cities from $C$ which is contradicting the maximality of $A$ and hence we prove non-existence of any such city $B$ and hence every city is available from $A$ .