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

Math Help - Networking

  1. #1
    Newbie
    Joined
    Aug 2012
    From
    New Zealand
    Posts
    7
    Thanks
    1

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

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,545
    Thanks
    780

    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: October 11th 2011, 02:21 PM
  2. Networking
    Posted in the Math Topics Forum
    Replies: 1
    Last Post: August 26th 2010, 03:10 AM
  3. Computer networking
    Posted in the Algebra Forum
    Replies: 1
    Last Post: August 10th 2007, 11:31 PM
  4. Networking
    Posted in the Advanced Math Topics Forum
    Replies: 7
    Last Post: April 27th 2006, 02:25 PM

Search Tags


/mathhelpforum @mathhelpforum