wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> easy >> hand shakes
        
(Message started by: black_death on May 5^th, 2008, 6:27am)

Title: hand shakes
Post by black_death on May 5^th, 2008, 6:27am

N students are seated at desks in an m x n array, where m, n >= 3. Each student shakes hands with the students who are adjacent horizontally, vertically or diagonally. If there are 81 handshakes, what are the values of N,m,n .... can a generic solution be found for a given number of handshakes?

Title: Re: hand shakes
Post by towr on May 5^th, 2008, 6:54am

[hide]For a given n x m array, you have
4 * 3 +
2 * (m-2) * 5 +
2 * (n-2) * 5 +
(m-2)(n-2) * 8
=
4 - 6m - 6n + 8mn half-handshakes
So, 2 - 3m - 3n + 4mn handshakes (since a handshake takes two people)
I'm not sure if there's a nice way to find the inverse for this (to go from X handshakes to m and n). But in any case {n,m}={4,7} works to get 81 handshakes.
[/hide]

Title: Re: hand shakes
Post by Hippo on May 5^th, 2008, 7:15am

It seems to me not all desks must be occupied ... otherwise only two parameters ... m,n are sufficient.

Title: Re: hand shakes
Post by black_death on May 5^th, 2008, 7:22am

on 05/05/08 at 07:15:08, Hippo wrote:

It seems to me not all desks must be occupied ... otherwise only two parameters ... m,n are sufficient.

ya actually the question in the original form was a MCQ so that you can work backwords .... but when my friend asked me he didn't give me choices so was wondering is there a way to find the values with only one equation ...

btw towr's answer is perfect :)

Title: Re: hand shakes
Post by Eigenray on May 6^th, 2008, 1:44pm

We can rewrite the formula as [hide](4m-3)(4n-3) = 4X+1[/hide]. There is only a solution when [hide]4X+1 has a divisor d=1 mod 4 with 5<d<(4X+1)/5[/hide], so for X = 20, 29, 38, 42, 47, 55, 56, 65, 68, 72, 74, 81, 83, 89, 92, 94, ...

The set of such X has density 1 in the natural numbers.