MathDB

A town has a road network that consists entirely of one-way streets that are used for bus routes. Along these routes, bus stops have been set up. If the one-way signs permit travel from bus stop

X

to bus stop

Y \neq X

, then we shall say

Y

can be reached from

X

. We shall use the phrase

Y

comes after

X

when we wish to express that every bus stop from which the bus stop

X

can be reached is a bus stop from which the bus stop

Y

can be reached, and every bus stop that can be reached from

Y

can also be reached from

X

. A visitor to this town discovers that if

X

and

Y

are any two different bus stops, then the two sentences “

Y

can be reached from

X

” and “

Y

comes after

X

” have exactly the same meaning in this town. Let

A

and

B

be two bus stops. Show that of the following two statements, exactly one is true: (i)

B

can be reached from

A;

(ii)

A

can be reached from

B.

Problem Statement