Jump to content


Welcome to BrainDen.com - Brain Teasers Forum

Welcome to BrainDen.com - Brain Teasers Forum. Like most online communities you must register to post in our community, but don't worry this is a simple free process. To be a part of BrainDen Forums you may create a new account or sign in if you already have an account.
As a member you could start new topics, reply to others, subscribe to topics/forums to get automatic updates, get your own profile and make new friends.

Of course, you can also enjoy our collection of amazing optical illusions and cool math games.

If you like our site, you may support us by simply clicking Google "+1" or Facebook "Like" buttons at the top.
If you have a website, we would appreciate a little link to BrainDen.

Thanks and enjoy the Den :-)
Guest Message by DevFuse
 

Photo
- - - - -

Mutual relations


Best Answer m00li, 28 April 2014 - 10:35 PM

Spoiler for Max Population
Go to the full post


  • Please log in to reply
7 replies to this topic

#1 BMAD

BMAD

    Senior Member

  • Members
  • PipPipPipPip
  • 1702 posts
  • Gender:Female

Posted 28 April 2014 - 01:31 AM

Prove that in any group of 6 people, at least 3 must be either mutually acquainted with each other, or mutually unacquainted with each other.


  • 0

#2 bonanova

bonanova

    bonanova

  • Moderator
  • PipPipPipPip
  • 5918 posts
  • Gender:Male
  • Location:New York

Posted 28 April 2014 - 04:33 AM

Spoiler for easiest way


Not really a proof.


  • 0
The greatest challenge to any thinker is stating the problem in a way that will allow a solution.
- Bertrand Russell

#3 m00li

m00li

    Junior Member

  • Members
  • PipPip
  • 71 posts

Posted 28 April 2014 - 10:35 PM   Best Answer

Spoiler for Max Population

  • 0

#4 BMAD

BMAD

    Senior Member

  • Members
  • PipPipPipPip
  • 1702 posts
  • Gender:Female

Posted 29 April 2014 - 01:18 AM

Spoiler for Max Population


Well stated but I have two issues:

you said the max population is 6 but I asked you to prove for 6.

Mutually unacquainted is not the opposite of mutually acquainted. I forget the English word for what I mean...is it contrapositive. As in ...if it isn't night it is day (mutual Acquaintances do not work this way)
  • 0

#5 BMAD

BMAD

    Senior Member

  • Members
  • PipPipPipPip
  • 1702 posts
  • Gender:Female

Posted 29 April 2014 - 04:41 AM

I mean you said 5 but I said prove 6
  • 0

#6 m00li

m00li

    Junior Member

  • Members
  • PipPip
  • 71 posts

Posted 29 April 2014 - 08:05 AM

I proved that if there is a group which does not satisfy your condition, then its population CANNOT be more than 5. Hence, if the population is more than 5 (6,7,8,...) it HAS to satisfy your condition. 

My proof doesnt state that mutual acquaintances and mutual strangers are the only two possibilities, rather it states that we cannot have a group of more than 5 ever, where the size of both mutual acquaintances and mutual strangers is less than 3.


  • 0

#7 bonanova

bonanova

    bonanova

  • Moderator
  • PipPipPipPip
  • 5918 posts
  • Gender:Male
  • Location:New York

Posted 29 April 2014 - 11:57 AM

I would agree that any pair of two people are either strangers or acquaintances.

That is A cannot know B unless B also knows A, and A cannot be a stranger to B unless B is also a stranger to A.

So ...

 

Spoiler for Here is the proof


  • 0
The greatest challenge to any thinker is stating the problem in a way that will allow a solution.
- Bertrand Russell

#8 bonanova

bonanova

    bonanova

  • Moderator
  • PipPipPipPip
  • 5918 posts
  • Gender:Male
  • Location:New York

Posted 01 May 2014 - 09:06 PM

m00li's post #3 answers the OP.

 

Post #4 stated two objections. Let's look at the objections.

 

[1] Differences between 5 and 6.

 

OP asks for proof that in a group of 6 people condition A or condition B exists.

Post#3 proves that if A or B does not exist the group can have no more than 5 people.

"Not (A or B) implies less than 6" is logically the same as "6 implies (A or B)."

 

[2] "Mutually unacquainted" is different from "not mutually acquainted."

 

Post #3 (and post #7, but post #3 was first) assume they are the same.

If there is a third possibility then no proof exists.

 

To show this, let's construct a third, asymmetrical relationship:

Let's say that I am acquainted with someone who is not acquainted with me.

Say a groupie (not the fish) is "acquainted" with a Rock Star who is not acquainted with the groupie.

 

  • Since the groupie knows the star, they cannot be "mutually unacquainted."
    Since the star does not know the groupie, neither can they be "mutually acquainted."
    All that can be said of them is that they are "not mutually acquainted."

 

Using "mutually unacquainted" and "not mutually acquainted" as different relationships

prevents the requested proof. Here's how that might play out.

  1. Among three rock stars, Elvis knows Mick and Bob, but Mick and Bob are strangers.
  2. Among three groupies, Sam knows Pete and Jane, but Pete and Jane are strangers.
  3. Sam, Pete and Jane, being groupies, all know Elvis, Mick and Bob
  4. None of Elvis, Mick and Bob know any of Sam, Pete and Jane.
  5. No three of six are "mutually acquainted"
  6. No three of six are "mutually unacquainted"
  7. Ergo, with that interpretation there is no proof.
  8. Mick, Bob, Pete and Jane, however, are "not mutually acquainted."
  9. With that interpretation the proof exists.

  • 0
The greatest challenge to any thinker is stating the problem in a way that will allow a solution.
- Bertrand Russell




0 user(s) are reading this topic

0 members, 0 guests, 0 anonymous users