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
- - - - -

Party with strangers


Best Answer k-man, 03 March 2013 - 02:36 AM

Not only it's possible, but it's quite simple too.

Spoiler for

Go to the full post


  • Please log in to reply
7 replies to this topic

#1 BMAD

BMAD

    Senior Member

  • Members
  • PipPipPipPip
  • 1674 posts
  • Gender:Female

Posted 02 March 2013 - 11:26 PM

There is a group of people at a party. Show that you can introduce some of them to each other so that after the introduction, no more than two people in the group would have the same number of friends (initial configuration doesn't work because they all initially have 0 friends).


  • 0

#2 austinm

austinm

    Newbie

  • Members
  • Pip
  • 12 posts

Posted 03 March 2013 - 12:02 AM

It's not possible, assuming that friendship is symmetric and not optionally-reflexive. That is, friendship is either reflexive or not, but it is that way for all people. (If one does not make those assumptions, it's both possible and uninteresting.)

Proof is inductive on number of people at party; inductive step uses the Pigeonhole Principle. There's a tiny subtlety in the inductive step.

Spoiler for If you get stuck...

 


  • 0

#3 BMAD

BMAD

    Senior Member

  • Members
  • PipPipPipPip
  • 1674 posts
  • Gender:Female

Posted 03 March 2013 - 12:10 AM

it is possinle.

It's not possible, assuming that friendship is symmetric and not optionally-reflexive. That is, friendship is either reflexive or not, but it is that way for all people. (If one does not make those assumptions, it's both possible and uninteresting.)

Proof is inductive on number of people at party; inductive step uses the Pigeonhole Principle. There's a tiny subtlety in the inductive step.

Spoiler for If you get stuck...


  • 0

#4 k-man

k-man

    Advanced Member

  • Members
  • PipPipPip
  • 450 posts
  • Gender:Male

Posted 03 March 2013 - 02:36 AM   Best Answer

Not only it's possible, but it's quite simple too.

Spoiler for


  • 0

#5 BMAD

BMAD

    Senior Member

  • Members
  • PipPipPipPip
  • 1674 posts
  • Gender:Female

Posted 03 March 2013 - 02:58 AM

k-man your process works if n is odd but if n is even does it still hold?  for example:

 

n= 4

a=3 friends

d= 1 friend

b = 2 friends

c=2 friends

 

Not only it's possible, but it's quite simple too.

Spoiler for


  • 0

#6 k-man

k-man

    Advanced Member

  • Members
  • PipPipPip
  • 450 posts
  • Gender:Male

Posted 03 March 2013 - 06:12 AM

 

k-man your process works if n is odd but if n is even does it still hold?  for example:

 

n= 4

a=3 friends

d= 1 friend

b = 2 friends

c=2 friends

 


Not only it's possible, but it's quite simple too.

Spoiler for

 

Sure it does. Your OP says "... no more than two people in the group would have the same number of friends". This means that 2 people can have the same number of friends. In your example there are only 2 people with 2 friends.

Spoiler for In general


  • 0

#7 Prime

Prime

    Senior Member

  • Members
  • PipPipPipPip
  • 872 posts
  • Gender:Male
  • Location:Illinois, US

Posted 03 March 2013 - 07:06 AM

I assume, like in real life, after an introduction two people immediately become fast friends.

Spoiler for an easy method

Same thing as k-man actually.

Note, it is impossible for all n people to have different number of friends, since the maximum number of people a person may know is n - 1, and with that, mininimum is 1. So at least two people must have equal number of introductions.


Edited by Prime, 03 March 2013 - 07:13 AM.

  • 0

Past prime, actually.


#8 austinm

austinm

    Newbie

  • Members
  • Pip
  • 12 posts

Posted 04 March 2013 - 06:30 PM

Horribly sorry--I mis-read the original as "no two people in the group..." rather than "no more than two people in the group...." For the OP it's clearly possible; my first reply applies to the situation in Prime's note.


  • 0




0 user(s) are reading this topic

0 members, 0 guests, 0 anonymous users