The Sex Problem

[Ender]

Prove that in any party with a finite number of people, there are at least two people who have had sex with the same number of people at the party.

rot13 your answer. (Let this be a guideline for the future.)

Edit: I will post the proof on Sunday, and a hint on Friday.

Hint (well, Saturday, not Friday): Consider the pigeonhole principle, which is that if you are to put p pigeons in h holes, and p > h, then at least one hole has more than one pigeon.

SOLUTION

[Ergot]

Gvz naq V ner va gur cnegl.

[Joe]

Arjol naq V jbhyq znxr fher gb uvg rirel fvatyr tvey, fb jr'q or rdhny.

Ohg jura ur uvgf gur ubyr va gur jnyy ur'f +1 gubhtu..

Ergot, I don't understand yours, but I think it's the same as mine, right?

[Ergot]

I'm not clear on what he's asking, but I thought it meant that if the party had x (say 200) number of people... that at least two of them would have had sex with the same x number of people (which is 200).

But I can easily disprove the problem. If there's one person in the party, then there's no way "at least two people... have had sex with the same number of people at the party."

[Ender]

It's implied that there's more than one. It's a party.

[Sidoh]

V thrff sbe guvf cebbs gb jbex, lbh unir gb nffhzr gung rirelbar ng gur cnegl znfgheongrf (unf "unq frk" jvgu gurzfrys).

Sbe rirelbar ng gur cnegl gb unir unq frk jvgu qvssrerag ahzoref bs crbcyr, gurer jvyy unir gb or bar crefba jub'f unq frk jvgu bayl uvz/urefrys, bar crefba jub'f unq frk jvgu uvz/urefrys naq nabgure crefba ng gur cnegl, rgp nyy gur jnl guebhtu fbzrbar jub'f unq frk jvgu rirelbar ng gur cnegl.  Vs gurer'f fbzrbar jub'f unq frk jvgu rirelbar va gur cnegl, gura gurer pna'g or fbzrbar jub'f unq frk jvgu bayl uvz/urefrys.

[Joe]

V thrff sbe guvf cebbs gb jbex, lbh unir gb nffhzr gung rirelbar ng gur cnegl znfgheongrf (unf "unq frk" jvgu gurzfrys).

Sbe rirelbar ng gur cnegl gb unir unq frk jvgu qvssrerag ahzoref bs crbcyr, gurer jvyy unir gb or bar crefba jub'f unq frk jvgu bayl uvz/urefrys, bar crefba jub'f unq frk jvgu uvz/urefrys naq nabgure crefba ng gur cnegl, rgp nyy gur jnl guebhtu fbzrbar jub'f unq frk jvgu rirelbar ng gur cnegl.  Vs gurer'f fbzrbar jub'f unq frk jvgu rirelbar va gur cnegl, gura gurer pna'g or fbzrbar jub'f unq frk jvgu bayl uvz/urefrys.

Abg vs fbzrbar chyyf bhg naq fgvpxf vg va fbzrbar ryfr. ^_^

[Sidoh]

*10^23

[Joe]

Ender, are they allowed to knock up more than one partner?

[Sidoh]

If they couldn't bump uglies with more than one person at the party, then you don't need to do much work to prove that the quandary is correct...

[Ender]

Sidoh: On the right track but your assumption is wrong. Sex is mutual. (If masturbating counted then I woulda said that Newby was at the party, or moreover, was the party...)

[Ender]

Solution:

Consider a party with n people. Each person at the party has n - 1 possibilities for the number of people they have had sex with. There are n people at the party, so by the pigeonhole principle at least two people has had sex with the same number of people.

w^5 (which is what we wanted)

Further Explanation:

I will explain how we used the pigeonhole principle, which was stated as a hint in the first post. The n - 1 possibilities that each person has for his or her number are the holes. The people themselves are the pigeons. Since there are more pigeons than holes, at least two pigeons must be in the same hole (yes, every pigeon has to be in a hole, there's no such thing as "The number of people I've had sex with is undefined").

The pigeonhole principle is a useful principle that can make complex problems seem simple and elegant. When considering the pigeonhole principle, identify what the holes and pigeons are.

[Sidoh]

I'm pretty sure that my solution was a less direct way of saying that.  I made the assumption that people would have to have sex with themselves for this "pigeonhole principle" to work (I wasn't familiar with it, but it's pretty obvious thing) because in a party of n people, any given person would have n possibilities (they could not have had sex with anyone or they could have had sex with n-1 people, 1+n-1=n).

That said, I see how the problem simplifies, even with the possibility of a virgin.  There would be a party of n-1 people with n-2 possibilities (since one is already a virgin, no one left at the party can be a virgin to find a contradiction).  I think that's probably a good addition to your proof.

[MyndFyre]

Wait, I don't understand. 

Given a party of 5 people: A, B, C, D, and E, you could have the following configuration:

A: no sexual partners.
B: 1 sexual partner.
C: 2 sexual partners.
D: 3 sexual partners.
E: 20 sexual partners.

I'm not quite sure I see where you're taking this.

[Sidoh]

The partners are only counted if they're present at the party as well.