11 replies to this topic

[Guest]

Hey morons CodeCallers! I have a math problem for you guys to solve. The first person to solve it wins....... NOTHING!

If a group of 93983475 people shake hands with each other person exactly one time, how many handshakes will take place?

[Hignar]

4,416,446,739,546,070

[dbug]

I think you missed 5 handshakes... :P

4,416,446,739,546,075

[Guest]

dbug said:

4,416,446,739,546,075

Nice! Would you two mind sharing how you got your answers? I'm curious to see if we solved it the same way.

[Hignar]

dbug said:

I think you missed 5 handshakes... :P

4,416,446,739,546,075

Possibly. Excel's fairly well known for it's rounding errors.

[Hignar]

Guest said:

Nice! Would you two mind sharing how you got your answers? I'm curious to see if we solved it the same way.

If every person has to shake each persons hand once then the most logical way to do it would be for one person to start and shake everybody's hand once meaning he'll shake, in this case, 93983474 hands. The next person does the same thing but has already shaken the hand of the first person so he has to shake one less hand (ie 93983473). This continues until the next to last guy just has to shake one persons hand. So you get

93983474 + 93983473 + ... + 1 = 4,416,446,739,546,075

Which is more easily calculated as 93983475 * 93983474/2, or in the more general case involving n people

 n(n-1)/2

[Guest]

Hignar said:

If every person has to shake each persons hand once then the most logical way to do it would be for one person to start and shake everybody's hand once meaning he'll shake, in this case, 93983474 hands. The next person does the same thing but has already shaken the hand of the first person so he has to shake one less hand (ie 93983473). This continues until the next to last guy just has to shake one persons hand. So you get

93983474 + 93983473 + ... + 1 = 4,416,446,739,546,075

Which is more easily calculated as 93983475 * 93983474/2, or in the more general case involving n people

 n(n-1)/2

When I first stumbled upon this problem (a couple of years ago), it was the same type of thing, but with 10 people in a room. I actually made a little python program with a for loop to solve it for n cases. That's the obvious way for a programmer to do it.

The less obvious way is to find the equation for it. There are several ways to do it, but I was able to derive a quadratic equation from just the first 3 amounts of people.

[dbug]

From a more mathematical point of view, you have N elements (the persons) and they must be grouped in pairs (each handshake). This means that you have to find how many combinations of 2 elements can be done from a group of N elements.

There is a methematical term for this: Combinations

The general formula to do this is (N elements, groups of k elements): N! / ( (N - k)! * k! )

For this example, k = 2, so: N! / ( (N - 2)! * 2! ) = N * (N - 1) / 2

Edited by dbug, 15 September 2010 - 02:55 AM.
missing a /

[Guest]

I have never simplified factorials like that before, but it actually makes sense. Cool :D

[dbug]

There were a missing division in the last line in my previous post...

It's a simple common factor elimination:

Quote

N! = N * (N - 1) * (N - 2)!

so

Quote

N! / (N - 2)! = N * (N - 1) * (N - 2)! / (N - 2)! = N * (N - 1)

[agnl666]

in math you can use factorial as shown above though the easiest way is called sum of n. or to find the sum of n term in a sequence. the formula being S = [n(2a + (n-1)d)]/2 where a is the first term and d is the difference of terms. Simplified it is S = [n(a-tn)]/2 where tn is the last term in the sequence. for the sum of natural numbers incrementing down by one it is S = [n - n^2]/2 or what was demonstrated above already.

[WingedPanther]

C(93983475,2)