• Support PF! Buy your school textbooks, materials and every day products Here!

Finding The Number of People At A Party

  • Thread starter Bashyboy
  • Start date
  • #1
1,421
5

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.
 

Answers and Replies

  • #2
Mentallic
Homework Helper
3,798
94

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 Sn 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 yn - 2yn-1 + yn-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.
 
  • #3
1,421
5
How are you able to determine that there are n-1 n-terms by inspection?
 
  • #4
Mentallic
Homework Helper
3,798
94
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.
 
  • #5
Curious3141
Homework Helper
2,843
86
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.
 
  • #6
19,918
4,095
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
 
  • #7
223
10
Combinations out of X, 2 at a time = 1275 seems fine to me.
 

Related Threads on Finding The Number of People At A Party

Replies
10
Views
819
Replies
3
Views
899
Replies
10
Views
2K
Replies
2
Views
498
Replies
2
Views
737
Replies
2
Views
1K
Replies
5
Views
2K
Replies
3
Views
779
Replies
1
Views
1K
Replies
18
Views
744
Top