Conference rusure::math

This problem made the rounds of the Universities about a year ago
after the case n=10 was proposed by Halmos in [1].  Since I have
already seen (and solved) this problem, I will wait a while to
give some one else a chance to work on it.

			Reference

[1] Paul R. Halmos, The Thrills of Abstraction. The Two Year College
	Mathematics Journal. 13(Sept. 1982)243-251.

____________________________________________________________________________
NOTE: Usage hereunder of only male forms of words (he, himself, his...) is
strictly for convenience, and does not imply any chauvinistic inclination...
			(^:    :^)
----------------------------------------------------------------------------

Firstly, note that n is even, as guests came to the party as pairs.

I asked everyone at the party, including my spouse: "How many people have you
shaken hands with?"

Since a person shakes hands with only people he has not met, the largest
answer is (n-2), eg.  all guests at the party less himself and his spouse.

Since the (n-1) party guests all gave me different answers, their answers must
form the set of the (n-1) consecutive integers { 0,1,2,3,...,(n/2),...,(n-2) }

Consider the person A who greeted (n-2) other guests, eg. ALL guests at the
party OTHER than him/herself and his/her spouse. Since ALL guest at the party
OTHER than himself and his spouse has shaken hands at least ONCE (with him),
the person having shaken hands 0 time is none other than his spouse A' .

Consider B who greeted (n-3) other guests. He has greeted every people at the
party, except 3 persons: himself, his spouse B', and A' . Since everyone except
these 3 persons have greeted B and A, the person having shaken hands exactly 
once must be his spouse B' .

By continuing the same reasoning, if C greeted (n-4) guests, his spouse C'
has greeted 2 guests.

If we pair off the answers in the answer set { 0,1,2,...,(n/2),...(n-2) } into
"complementary" pairs which add up to (n-2), these complementary pairs are the
answers from the couples in the party other than my wife:

	A  (n-2)      0   A'
	B  (n-3)      1   B'
	C  (n-4)      2   C'
	    ...       ..

The only answer left for my wife is therefore (n/2), the answer in the middle
of the answer set. 

Van Luong Nguyen,
Digital Equipment Corp.

    The above is a very nice presentation of the solution.  Thank you!
    
    However, I came up with a different final answer.  I think it's
    n/2-1.  Sorry to nitpick!

    I have a variation of a handshaking problem, and if there's a solution,
    I'd be very grateful.
    
    Here's the situation:  there is a team of six men.  Each week, each man
    on the team is supposed to call another man.  In the course of five
    weeks, each man should call every other man on the team.  No pattern
    should repeat itself in the five-week cycle.  That is, if A calls B
    in week 1, then A cannot call B again (however, B can call A). Also,
    If A calls D, then D cannot call A that same week.
    
    I can't make this work.  I'm beginning to suspect there is no solution
    for teams of six. I can contruct a pattern for five and seven, but
    not for six -- and I can't change the number of men on the tteam.
    
    					andrew

Let the men be numbered from 0 to 5, and the weeks from 0 to 4.
On the i'th week, have the j'th man call the k'th man, where k = (i+j+1) mod 6.

                    -< solutions exist for all n <> 2 or 4 >-

>    Here's the situation:  there is a team of six men.  Each week, each man
>    on the team is supposed to call another man.  In the course of five
>    weeks, each man should call every other man on the team.  No pattern
>    should repeat itself in the five-week cycle.  That is, if A calls B
>    in week 1, then A cannot call B again (however, B can call A). Also,
>    If A calls D, then D cannot call A that same week.
>    
>    					andrew


>Let the men be numbered from 0 to 5, and the weeks from 0 to 4.
>On the i'th week, have the j'th man call the k'th man, where k = (i+j+1) mod 6.
>
>					peter

	In Peter's solution, in week 2, everyone calls the person that calls
them, violating violently the last constraint in the problem statement.   So
let's start again.

	This constraint, since we have 6 people, implies that each week we
either have a cycle of six calls, or two cycles of three.   Suppose that we
have a week which comprises two cycles of three.   Wlog, call one cycle the 
men, the other the women.   Now look at each kind of week, and see how many 
man-to-man calls are required.   For two cycles of three, the number of m-m 
calls is 3 or 1.   For one cycle of six, the number of m-m calls is 2,1 or 0.  
Over five weeks, the total number of m-m calls must be 6.   since one week 
alone gives us 3 of them, the decomposition of the six across the weeks must 
be one of:

(a) 3+3+0+0+0
(b) 3+2+1+0+0
(c) 3+1+1+1+0

	(a) gives us:
(012)(345)
(021)(354)
(031425)
(041523)
(051324)

	It would be possible to replace the first two weeks by
(012)(354)
(021)(345)
but all solutions of form (a) are symmetries of one of these two distinct 
solutions.

	(b) or (c) fall the wrong side of the time/interest tradeoff curve. :-)

	On the other hand, if every week is a cycle of six, then pick one such
and define the men to be alternate with the women.   This contributes 0 to
the m-m total, which must therefore be one of:

(d) 2+2+2+0+0
(e) 2+2+1+1+0

	(d) is impossible, since one cannot divide up the m-m calls in this
way over 3 men (try it).

	(e) yields ??? again remains to be pursued if someone's interested.



	What about a general solution for any number of people?

If n is odd, then I believe that Peter's idea of j calling k = (i+j+1) mod n
will work fine.

If we have solved n, then we can solve 2n, using a trivial generalization of
the solution that I've got for the n=6 case above.

So all that we need to do is to find the smallest power of 2 which we can
solve (above 2^0=1 which is vacuously solvable).   2 and 4 are not solvable,
so let's examine n=8.

j calls k = (i+j+1) mod 8 *nearly* works, except for week 3, which is totally
awful.   Can we perturb the near-solution to get something that works?

(01234567)
(0246)(1357)
(03614725)
(04)(15)(26)(37)
(05274163)
(0642)(1753)
(07654321)

	Let's take weeks 3 and 4 above:
(04)(15)(26)(37)
(05274163)

	and replace them by the healthier:
(04152637)
(05162734)

	This nearly works, except that we have
3->4 and not 3->0
7->0 and not 7->4

	However if we repair week 1:
(01234567)

becoming:
(0123)(4567)

then we have overcome this difficulty.


	So our solution for n=8 is as follows:
(0123)(4567)
(0246)(1357)
(03614725)
(04152637)
(05162734)
(0642)(1753)
(07654321)

	Not very pretty perhaps, but the ease of solving the problem
indicates that there may be lots and lots of solutions.

	Thus the handshaking in the way that Andrew Kenah wanted is possible 
for all n <> 2 or 4.

Regards,
Andrew.

    Andrew:
    
    I don't understand --  perhaps I'm missing something, but I don't
    see how the problem is solved.
    
    If we look at this pattern:
    
	(012)(345)
	(021)(354)
	(031425)
	(041523)
	(051324)
    
    There are a few difficulties.  Now, if I didn't clearly state the
    problem, I apologize. 
    
    First, it's a cycle of six. Second, the last man in the cycle calls
    the first man (For example, for week #0, man #5 calls man #0). 
    
    Now, in the solution above, there are several duplications, and several
    omissions.  In  week #1, man #1 calls man #5; this occurs again in week
    #4. #2 calls #3 in weeks #0 and #3.  Man #1 never calls man #0.             
    
    Help!
    
    					andrew

	Re -.1.   I suspect that we have still not achieved an common
understanding (a) of what the problem is (b) of what my solution is to what
I understood to be the problem.

(a) the problem.

	We have n people, say n = 6.   We have (n-1) weeks.   Each week,
each person must telephone exactly one of the other (n-1) people.   Each
week, each person must receive a phone call from one of the other (n-1)
people.   Over the (n-1) weeks, no person may ring the same person twice.
In any one week, no person rings themself, or rings the person that
rings them that week.

	Is this your understanding of the problem?
	If not, how does your understanding differ.

(b) my solution.
	Each solution appears as one line for each week.   In any one line,
there are a series of bracketed expressions.   The interpretation was intended
to be that, for instance:
	(012)(345)
is shorthand for
	0 telephones 1
	1 telephones 2
	2 telephones 0
	3 telephones 4
	4 telephones 5
	5 telephones 3
all in the same week.

	This notation is standard for permutations, but perhaps I should have
explained it here.   Hence my solution for 6 people, 5 weeks:

	(012)(345)	week 0
	(021)(354)	week 1
	(031425)	week 2
	(041523)	week 3
	(051324)	week 4
    
>    First, it's a cycle of six. 

	What is "it" in the previous line?   Do you mean that *each* *week*
the phone calls must form a cycle of six, rather than permitting two cycles
of 3 as happens in the first two weeks above?

>    Second, the last man in the cycle calls the first man (For example, for 
>    week #0, man #5 calls man #0). 
 
	I can't figure out how you parse what I have written in order to
imply the last sentence.   
   
>    Now, in the solution above, there are several duplications, and several
>    omissions.  

	I can't figure out how you're interpreting what I wrote in order to
make these assertions.

>    In  week #1, man #1 calls man #5; 
	No: in week 1 man 1 calls man 0

>    this occurs again in week # 4
	No: in week 4 man 1 calls man 3

>    #2 calls #3 in weeks #0 and #3.  
	No: 2 calls 0 in week 0, but yes he does call 3 in week 3

>    Man #1 never calls man #0.             
        No: in week 1.

	If we can agree on issues (a) & (b) above, then then let's look at
this problem further.

Cheers,
Andrew.

    Now I understand!  Okay, the pattern in .6 works eminently well.
    
    					thanks,
    					andrew