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

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

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

Started by BMAD, Mar 02 2013 11:26 PM

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
7 replies to this topic

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

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

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

Posted 03 March 2013 - 02:36 AM Best Answer

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

Spoiler for

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

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

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

Past prime, actually.

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 members, 0 guests, 0 anonymous users