Finding The Number of People At A Party

[Bashyboy]

Homework Statement

The question is to find the number of people at a party, if every two people shake hands and the number of handshakes is 1275.

Homework Equations

The Attempt at a Solution

Here is my partial solution:

After having performed simple cases of the problem--when there are 2, 3, 4, and 5 people--, I found that if there are n people, then first person chooses to shake hands with n - 1 people.

The number of handshakes can be written as

(n-1) + (n-2) + (n-3) +...+ 1 + 0 = 1275 (the zero connotes the fact that the last person does not choose to shake hands with anyone.) If we could somehow collect the n-terms so that it takes the form of an, where a is a some function (either a constant or some function of n)

Let's now investigate the relationship between the number of people and the number of handshakes.

# of people......# of handshakes
...2........1 = 1
...3.......2 + 1 = 3
...4......3 + 2 + 1 = 6
...5.... 4 + 3 + 2 + 1 = 10

Looking at the n = 5 equation, 4 the is actually an n term; it's n - 1, with n = 5; and so isn't 3,
n - 2, as well as 2 and 1, n - 3 and n - 4, respectively. So, there are 4 terms with n them, or there are n - 1 terms. So, the number of handshakes is n(n-1). But this is an over count. This says that every person shakes hands with n-1 people. We know that each person shakes hands with one less person than the last. If we use the formula n(n-1) to calculate the number of handshakes, we get 5(5-4) = 20, which is double the actual number of handshakes. n(n-1) must be twice the number of handshakes. Hence, n(n-1)/2.

------------------------------------------------------------

As I look back at this, I feel like my arguments are a little vague. Is there a more mathematical argument to derive the formula n(n-1)/2, especially the 1/2 factor. I understand that this isn't a mathematically rigorous class, the intention is to stimulate thinking, but I would to see if there is in fact a way to derive the formula, and to see if I can understand.

-------------------------------------------------------------

Here is another solution that I was unsure how to use:

Looking back at our table, we see the number of hand shakes is 1 = y2, 3 = y3, 6 = y4, 10 = y5.

y4 - y3 = 3 and y5 - y4 = 4

(y5 - y4) - (y4 - y3) = 4 - 3

y5 - y3 = 1

So, my conjecture is that [itex]y_n - y_{n-2} = 1[/itex] But I can't quite figure out how to use this fact.

 

[Mentallic]

Homework Statement

The question is to find the number of people at a party, if every two people shake hands and the number of handshakes is 1275.

Homework Equations

The Attempt at a Solution

Here is my partial solution:

After having performed simple cases of the problem--when there are 2, 3, 4, and 5 people--, I found that if there are n people, then first person chooses to shake hands with n - 1 people.

The number of handshakes can be written as

(n-1) + (n-2) + (n-3) +...+ 1 + 0 = 1275 (the zero connotes the fact that the last person does not choose to shake hands with anyone.) If we could somehow collect the n-terms so that it takes the form of an, where a is a some function (either a constant or some function of n)

Let's now investigate the relationship between the number of people and the number of handshakes.

# of people......# of handshakes
...2........1 = 1
...3.......2 + 1 = 3
...4......3 + 2 + 1 = 6
...5.... 4 + 3 + 2 + 1 = 10

Looking at the n = 5 equation, 4 the is actually an n term; it's n - 1, with n = 5; and so isn't 3,
n - 2, as well as 2 and 1, n - 3 and n - 4, respectively. So, there are 4 terms with n them, or there are n - 1 terms. So, the number of handshakes is n(n-1). But this is an over count. This says that every person shakes hands with n-1 people. We know that each person shakes hands with one less person than the last. If we use the formula n(n-1) to calculate the number of handshakes, we get 5(5-4) = 20, which is double the actual number of handshakes. n(n-1) must be twice the number of handshakes. Hence, n(n-1)/2.

------------------------------------------------------------

Yes, so to finish off your problem, you'll need to solve the quadratic n(n-1)/2 = 1275

As I look back at this, I feel like my arguments are a little vague. Is there a more mathematical argument to derive the formula n(n-1)/2, especially the 1/2 factor. I understand that this isn't a mathematically rigorous class, the intention is to stimulate thinking, but I would to see if there is in fact a way to derive the formula, and to see if I can understand.

-------------------------------------------------------------

You can always prove that your formula is correct by using mathematical induction. Even if you're iffy about the procedure you used to get to your result, if you can show that it holds true by mathematical induction, then you have found the correct formula.

Although, imagine that you found induction didn't work, either because the formula was wrong or the induction was incapable / too hard to use to prove the formula correct. There are various well known methods to find closed form solutions for summations. One of them is as follows:

Let

[tex]S_n = (n-1) + (n-2) + ... + 2 + 1[/tex]

If we reverse the order of the summation, we also get

[tex]S_n = 1 + 2 + ... + (n-2) + (n-1)[/tex]

And now, if we add both equations together, and line up each term on the RHS of each equation so that 1 adds to (n-1), 2 adds to (n-2), etc. then we get

[tex]2S_n = [(n-1)+1] + [(n-2)+2] + ... + [2+(n-2)] + [1+(n-1)][/tex]

and you'll notice that every pair of numbers on the RHS add to n

[tex]2S_n = n + n + ... + n + n[/tex]

With n-1 values of n on the RHS,

[tex]2S_n = (n-1)n = n(n-1)[/tex]

And finally, dividing both sides by 2 to get S_n alone yields the formula you found.

Here is another solution that I was unsure how to use:

Looking back at our table, we see the number of hand shakes is 1 = y2, 3 = y3, 6 = y4, 10 = y5.

y4 - y3 = 3 and y5 - y4 = 4

(y5 - y4) - (y4 - y3) = 4 - 3

y5 - y3 = 1

So, my conjecture is that [itex]y_n - y_{n-2} = 1[/itex] But I can't quite figure out how to use this fact.

You made a mistake.

(y5 - y4) - (y4 - y3) = y5 -2y4 + y3 = 4 - 3 = 1

And y_n - 2y_n-1 + y_n-2 = 1 is a recurrence equation that can be solved using some more advanced techniques. I don't know if you'd be ready for them, but if you're curious, you can always do a little bit of research on it.

 

[Bashyboy]

How are you able to determine that there are n-1 n-terms by inspection?

 

[Mentallic]

Because [itex]2S_n[/itex] has the same number of terms as [itex]S_n[/itex] and

[tex]S_n=1+2+...+(n-1)[/tex]

which clearly has n-1 terms.

 

[Curious3141]

It's elementary to solve the quadratic ##\frac{n(n-1)}{2} = 1275## from first principles, but if one just wants a quick answer, then it's OK to say ##n(n-1) = 2550##. Now since ##n## is clearly rather close to the square root of ##2550##. Testing the integer values bounding this figure almost immediately yields the correct answer.

 

[Chestermiller]

In your first post, you wrote out the sum of an arithmetic progression, with the first term 1 and the last term (n-1). Just use the formula for the sum of an arithmetic progression. Another way of getting the result is to use the formula for the number of combinations of n items taken two at a time.

Chet

 

[lendav_rott]

Combinations out of X, 2 at a time = 1275 seems fine to me.