Thread: Networking

Hi struggling with the question here any help gratefully accepted.

Two courier companies offer services in the country of Old Aland. For any two towns, at least one of the companies offers a direct link in both directions between them. Aditionally, each company is willing to chain together deliveries( so if they offer a direct link from A to B, and B to C, and C to D for instance, they will deliver from A to D) Show that at least one of the two companies must be able to deliver packages between any two towns in Old Aland.

Using technical language, the claim says that if the union of two equivalence relations is the set of all pairs, then so is at least one of the relations.

If A and B are two cities, let us write 1(AB) to say that company 1 offers a link between A and B, and similarly for 2(AB). Let us also write ~1(AB) and ~2(AB) for the negation of 1(AB) and 2(AB), respectively. In reading the following, it would help to draw a diagram. Suppose the conclusion of the claim is false, i.e., there exist cities A, B, C, D such that ~2(AB) and ~1(CD). Then 1(AB) and 2(CD). Suppose 1(AC) (the case when 2(AC) is similar). If 1(BD), then we have 1(CA), 1(AB), 1(BD), therefore, 1(CD), a contradiction. Therefore, 2(BD). What about AD? If 1(AD), then 1(CA) and 1(AD) imply 1(CD), a contradiction. If 2(AD), then 2(AD) and 2(DB) imply 2(AB), also a contradiction.