🚀 go-pugleaf

X-Orig-MsgId: <84e2db$cr2$1@news1.bu.edu>

I apologize for the wrong wordings, and hence the meaning of this 
last puzzle. The correct one should be:

4. Given 2n people (n=2,3,4,..) where each person knows not less than n 
people, prove that there can be a roundtable arrangement of 4 people
where each person knows the two persons on his/her side. 

This is trvially true where each person knows all others.
Following up on the puzzles, and to make up for the mistake, I also 
have an extra puzzle now:

5. Given n people, where two people who are acquainted with each 
other do not have any mutual acquaintances, and two people not
acquainted with each other have exactly two mutual acquaintances,
prove that all the people have exactly the same number of acquaintances.
Also, what are the values of 'n' which will permit this?

happy puzzling!

Joe Mac <joemacmail@this.is.invalid> wrote:
: Nick@maproom.co.uk wrote:

:>>4. given 2n people (n=1,2,3,..) where each person knows atleast n-1
:>>people show that there can be an arrangement of four people on a round
:>>table where each person does not know the person at his side but knows
:>>the person on the opposite side.
:>
:>This cannot be proved.  Here are two counterexamples:
:>
:>n=1.  There are not enough people to go round the table.

: Well, if you sit the two people across from each other, they'll know each 
: other, but not know the people in the other seats because there are no 
: people in the other seats.  Or you can just say n must be > 1.

:>
:>n=5, everyone knows all the other 9.  It is not possible to arrange four
:>so that someone does not know his neighbour.
:>
: Wait a second.  n=5, so there's 10 people, and everyone knows at least 4
: people.  ABCDEFGHIJ A knows BCDE
: B knows ACDE
: C knows ABDE
: D knows ABCE
: E knows ABCD
: So everyone in ABCDE know each other.
: Likewise, everyone in FGHIJ know each other.
: Nobody from ABCDE knows anyone from FGHIJ.
: So, place two from ABCDE opposite each other and two from FGHIJ in the
: remaining seats and you satisfy the problem. 

: Did I miss something?
: -- 
: Joe Mac
: My email id is correct, but the provider is Yahoo.