Results 1 to 2 of 2
Like Tree1Thanks
  • 1 Post By farlap

Thread: Networking

  1. #1
    Aug 2012
    New Zealand


    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.
    Thanks from senoj
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Oct 2009

    Re: Networking

    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 4
    Last Post: Oct 11th 2011, 02:21 PM
  2. Networking
    Posted in the Math Topics Forum
    Replies: 1
    Last Post: Aug 26th 2010, 03:10 AM
  3. Computer networking
    Posted in the Algebra Forum
    Replies: 1
    Last Post: Aug 10th 2007, 11:31 PM
  4. Networking
    Posted in the Advanced Math Topics Forum
    Replies: 7
    Last Post: Apr 27th 2006, 02:25 PM

Search Tags

/mathhelpforum @mathhelpforum