The mayor of a city wishes to establish a transport system with at least one bus line, in which: - each line passes exactly three stops, - every two different lines have exactly one stop in common, - for each two different bus stops there is exactly one line that passes through both. Determine the number of bus stops in the city.
Problem
Source: Cono Sur 1998 P6
Tags: combinatorics
ythomashu
30.08.2018 19:06
I can't read obviously
Mathlover_SH
31.08.2018 02:01
Just calculate the number of pairs(a,b) where a is a route,b is a stop and a includes b.
Kaskade
01.09.2018 19:42
Let $s$ be the number of stops and $L$ the number of lines. Now each pair of stops is covered by exactly one line, and each line has exactly three pairs of stops, so we get $3L=\frac{s\left(s-1\right)}{2}$ or $L=\frac{s\left(s-1\right)}{6}$
On the other hand, suppose the first line has stops $s_1,\ s_2,\ s_3$. There are $s-3$ remaining pairs of stops including $s_1$ and likewise for $s_2$ and $s_3$. Each line must have exactly one of $s_1$, $s_2$ or $s_3$ and each line will contain exactly two pairs of stops including one of $s_1$, $s_2$ or $s_3$. So there will be $1$ line will all $\left\{s_1,\ s_2,\ s_3\right\}$, then $\frac{s-3}{2}$ lines containing $s_1$, and likewise for $s_2$ and $s_3$, and this will cover all the lines. So we also have the relation $L=3\cdot\frac{s-3}{2}+1$.
So we have $3\cdot\frac{s-3}{2}+1=\frac{s\left(s-1\right)}{6}$ or $\left(s-3\right)\left(s-7\right)=0$
If $s=3$ we have the trivial case where we have one line passing through all three stops.
If $s=7$, call the seven stops $1, 2, 3, 4, 5, 6, 7$. Then from the above formula we get $L=7$ and could have for example the following arrangement:
$\left\{1,\ 2,\ 3\right\}$
$\left\{1,\ 4,\ 5\right\}$
$\left\{1,\ 6,\ 7\right\}$
$\left\{2,\ 4,\ 6\right\}$
$\left\{2,\ 5,\ 7\right\}$
$\left\{3,\ 4,\ 7\right\}$
$\left\{3,\ 5,\ 6\right\}$