🚀 go-pugleaf

X-Orig-MsgId: <84aohs$f9c$1@news1.bu.edu>

Nick Wedd <Nick@maproom.co.uk> wrote:
: In article <848v1u$9up$1@news1.bu.edu>, Shantanu Desai <shantanu@bu.edu>
: writes

:>1. Prove that the number of people in the world, at any given time,
:>who have shaken hands with an odd numer of people (1,3,5,..)
:>is even (0,2,4,..)

: If it were odd, then the total number of halfhandshakes would be odd,
: which is impossible.

correct. I forgot to mention the case when a person dies and all his
existing handshakes with other people should vanish as well (re: the
previous posting by D.J.Schreffler)

:>2. Prove that in a group of six people there exists either a) a
:>group of three who dont know each other or b) a group of three 
:>who all know each other or c) both a and b.

: Wlog A knows B and C, who do not know each other.  If D knows A, he most
: not know B or C, and there is BCD not-know cycle.  So D does not know A.
: By the same logic, E and F do not know A.  If any two of DEF do not know
: each other, there is a not-know cycle involving those two and A;
: otherwise DEF form a know cycle.

correct.

:>3. prove that in a group of n people (n=1,2,3,..) there are atleast
:>two people who are acquainted with the same number of people within the
:>group

: With n people, the possible numbers of acquaintanceships are 
: (0,1,2,..n-1).  But 0 and n-1 cannot be possible at the same time.  So
: there can only be n-1 possible numbers, which is not enough to assign
: one each.

correct. 

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

the question I asked is obviously wrong. I dont remember the question 
correctly, though n=1 is surely not a case. the only alternative I can think 
of is that atleast n-2 people each know exactly n-1 other people AND
they all know atleast n-1 people. 

I will try to get the correct question though if possible.


: n=1.  There are not enough people to go round the table.

: n=5, everyone knows all the other 9.  It is not possible to arrange four
: so that someone does not know his neighbour.

: Nick
: -- 
: Nick Wedd    nick@maproom.co.uk