Party with strangers

[BMAD]

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

[k-man]

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

Let's say there are n>2 people in the group with 0 friends each.

Pick one person A and introduce him/her to everybody. A now has n-1 friends. Everyone else, so far, has 1 friend. Remove A and one other person (let's call him B) from any further introductions. If we only have one person left then we achieved the goal - A has 2 friends, while the other two have one.

If we have more than one people remaining, then from the remaining group of n-2 people pick a person C and introduce him/her to everybody remaining. C now has n-2 friends (including A) and others in the group have 2. Remove C and one other person D from further introductions.

After 2 iterations we have:

A has n-1 friends

B has 1 friend

C has n-2 friends

D has 2 friends

All other people have 2 friends.

Repeat this process until you have 1 person or 0 people left.

[austinm]

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.

recognize that the necessity of a zero-friend person in the group of n people eliminates that person from consideration of friendship with the n+1th person; now you have fewer pigeonholes than pigeons.

[BMAD]

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.

recognize that the necessity of a zero-friend person in the group of n people eliminates that person from consideration of friendship with the n+1th person; now you have fewer pigeonholes than pigeons.

[BMAD]

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.

Let's say there are n>2 people in the group with 0 friends each.

Pick one person A and introduce him/her to everybody. A now has n-1 friends. Everyone else, so far, has 1 friend. Remove A and one other person (let's call him B) from any further introductions. If we only have one person left then we achieved the goal - A has 2 friends, while the other two have one.

If we have more than one people remaining, then from the remaining group of n-2 people pick a person C and introduce him/her to everybody remaining. C now has n-2 friends (including A) and others in the group have 2. Remove C and one other person D from further introductions.

After 2 iterations we have:

A has n-1 friends

B has 1 friend

C has n-2 friends

D has 2 friends

All other people have 2 friends.

Repeat this process until you have 1 person or 0 people left.

[k-man]

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.

Let's say there are n>2 people in the group with 0 friends each.

Pick one person A and introduce him/her to everybody. A now has n-1 friends. Everyone else, so far, has 1 friend. Remove A and one other person (let's call him B) from any further introductions. If we only have one person left then we achieved the goal - A has 2 friends, while the other two have one.

If we have more than one people remaining, then from the remaining group of n-2 people pick a person C and introduce him/her to everybody remaining. C now has n-2 friends (including A) and others in the group have 2. Remove C and one other person D from further introductions.

After 2 iterations we have:

A has n-1 friends

B has 1 friend

C has n-2 friends

D has 2 friends

All other people have 2 friends.

Repeat this process until you have 1 person or 0 people left.

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.

For any n, the most friends a single person can have is n-1. If someone has n-1 friends then the least number of friends for anybody in the group is 1. My method ensures that only one person has 1 friend and only one person has n-1 friends. Then it does the same for 2 and n-2, etc. With each iteration the group is reduced by 2. If n is even the 2 people will have n/2 friends. if n is odd, then 2 people will end up with (n-1)/2 friends.

[Prime]

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

Number them from 1 to n and arrange in order.

Divide the line in half (if odd, put the middle man into the top half.) Introduce everone to each other in the top half.
For the bottom half: Introduce 1st man to the n-th man only; 2nd man to the n-th and n-1st; 3rd man -- to top 3, and so on until the bottom half is all taken care of.
This way only the middle two would have same number of friends.

Or here is an alternate procedure amounting to the same thing.

Introduce first two men to each other. For each additional man, introduce him to the top half of the introduced men (sorted by number of friends.) When odd number of men introduce, the top half should include an extra man.

This way the introduced field will grow like so:

1 1

2 1 1

3 2 2 1

4 3 2 2 1

5 4 3 3 2 1

and so on. (Each newcomer is marked in red.)

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 March 3, 2013 by Prime

[austinm]

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.