algorithm problem solving [closed]

0

$begingroup$

In a party some people shake hands and some don't. Suppose everyone counts the number of handshakes that he performed. Prove that at least two people have same number of handshakes.

pigeonhole-principle

share|cite|improve this question

edited Jan 2 at 21:43

Peter Chikov

505

asked Jan 2 at 16:24

Bilal TahirBilal Tahir

6

$endgroup$

closed as off-topic by Davide Giraudo, amWhy, A. Pongrácz, Cesareo, Leucippus Jan 3 at 0:39

This question appears to be off-topic. The users who voted to close gave this specific reason:

• "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – Davide Giraudo, amWhy, A. Pongrácz, Cesareo, Leucippus

If this question can be reworded to fit the rules in the help center, please edit the question.

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  Generally it's a good idea to show what ideas you have and how far you've got with solving this yourself, as others then know better what you don't understand.
  $endgroup$
  – postmortes
  Jan 2 at 16:30
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  You can use the Pigeonhole Principle for this problem.
  $endgroup$
  – harshit54
  Jan 2 at 16:31
  
  
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  This has nothing whatsoever to do with probability.
  $endgroup$
  – saulspatz
  Jan 2 at 17:35
  

  
  
  
  

add a comment | 

0

$begingroup$

In a party some people shake hands and some don't. Suppose everyone counts the number of handshakes that he performed. Prove that at least two people have same number of handshakes.

pigeonhole-principle

share|cite|improve this question

edited Jan 2 at 21:43

Peter Chikov

505

asked Jan 2 at 16:24

Bilal TahirBilal Tahir

6

$endgroup$

closed as off-topic by Davide Giraudo, amWhy, A. Pongrácz, Cesareo, Leucippus Jan 3 at 0:39

This question appears to be off-topic. The users who voted to close gave this specific reason:

• "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – Davide Giraudo, amWhy, A. Pongrácz, Cesareo, Leucippus

If this question can be reworded to fit the rules in the help center, please edit the question.

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  Generally it's a good idea to show what ideas you have and how far you've got with solving this yourself, as others then know better what you don't understand.
  $endgroup$
  – postmortes
  Jan 2 at 16:30
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  You can use the Pigeonhole Principle for this problem.
  $endgroup$
  – harshit54
  Jan 2 at 16:31
  
  
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  This has nothing whatsoever to do with probability.
  $endgroup$
  – saulspatz
  Jan 2 at 17:35
  

  
  
  
  

add a comment | 

0

0

0

$begingroup$

In a party some people shake hands and some don't. Suppose everyone counts the number of handshakes that he performed. Prove that at least two people have same number of handshakes.

pigeonhole-principle

share|cite|improve this question

edited Jan 2 at 21:43

Peter Chikov

505

asked Jan 2 at 16:24

Bilal TahirBilal Tahir

6

$endgroup$

In a party some people shake hands and some don't. Suppose everyone counts the number of handshakes that he performed. Prove that at least two people have same number of handshakes.

pigeonhole-principle

pigeonhole-principle

share|cite|improve this question

edited Jan 2 at 21:43

Peter Chikov

505

asked Jan 2 at 16:24

Bilal TahirBilal Tahir

6

share|cite|improve this question

edited Jan 2 at 21:43

Peter Chikov

505

asked Jan 2 at 16:24

Bilal TahirBilal Tahir

6

share|cite|improve this question

share|cite|improve this question

edited Jan 2 at 21:43

Peter Chikov

505

edited Jan 2 at 21:43

Peter Chikov

505

edited Jan 2 at 21:43

Peter Chikov

505

505

asked Jan 2 at 16:24

Bilal TahirBilal Tahir

6

asked Jan 2 at 16:24

Bilal TahirBilal Tahir

6

asked Jan 2 at 16:24

Bilal TahirBilal Tahir

6

6

closed as off-topic by Davide Giraudo, amWhy, A. Pongrácz, Cesareo, Leucippus Jan 3 at 0:39

This question appears to be off-topic. The users who voted to close gave this specific reason:

• "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – Davide Giraudo, amWhy, A. Pongrácz, Cesareo, Leucippus

If this question can be reworded to fit the rules in the help center, please edit the question.

closed as off-topic by Davide Giraudo, amWhy, A. Pongrácz, Cesareo, Leucippus Jan 3 at 0:39

This question appears to be off-topic. The users who voted to close gave this specific reason:

• "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – Davide Giraudo, amWhy, A. Pongrácz, Cesareo, Leucippus

If this question can be reworded to fit the rules in the help center, please edit the question.

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  Generally it's a good idea to show what ideas you have and how far you've got with solving this yourself, as others then know better what you don't understand.
  $endgroup$
  – postmortes
  Jan 2 at 16:30
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  You can use the Pigeonhole Principle for this problem.
  $endgroup$
  – harshit54
  Jan 2 at 16:31
  
  
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  This has nothing whatsoever to do with probability.
  $endgroup$
  – saulspatz
  Jan 2 at 17:35
  

  
  
  
  

add a comment | 

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  Generally it's a good idea to show what ideas you have and how far you've got with solving this yourself, as others then know better what you don't understand.
  $endgroup$
  – postmortes
  Jan 2 at 16:30
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  You can use the Pigeonhole Principle for this problem.
  $endgroup$
  – harshit54
  Jan 2 at 16:31
  
  
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  This has nothing whatsoever to do with probability.
  $endgroup$
  – saulspatz
  Jan 2 at 17:35
  

  
  
  
  

1

1

$begingroup$
Generally it's a good idea to show what ideas you have and how far you've got with solving this yourself, as others then know better what you don't understand.
$endgroup$
– postmortes
Jan 2 at 16:30

$begingroup$
Generally it's a good idea to show what ideas you have and how far you've got with solving this yourself, as others then know better what you don't understand.
$endgroup$
– postmortes
Jan 2 at 16:30

$begingroup$
You can use the Pigeonhole Principle for this problem.
$endgroup$
– harshit54
Jan 2 at 16:31

$begingroup$
You can use the Pigeonhole Principle for this problem.
$endgroup$
– harshit54
Jan 2 at 16:31

1

1

$begingroup$
This has nothing whatsoever to do with probability.
$endgroup$
– saulspatz
Jan 2 at 17:35

$begingroup$
This has nothing whatsoever to do with probability.
$endgroup$
– saulspatz
Jan 2 at 17:35

add a comment | 

2 Answers
2

active

oldest

votes

1

$begingroup$

Suppose there are $n$ people at the party.

The most gregarious person there shakes at most $n-1$ hands. i.e. everyone but himself.

It is possible that someone is a germaphobe who doesn't shake anyone's hand. However, it is not possible for both one person to shake everyone's hand and one person to shake nobody's hand.

This leaves $n-1$ pigeon holes.

If $n$ people count a different number of handshakes, that is $n$ pigeons.

If there are more pigeons that pigeon-holes, at least one pigeon-hole holds 2 pigeons.

share|cite|improve this answer

edited Jan 3 at 15:41

answered Jan 2 at 22:35

Doug MDoug M

44.3k31854

$endgroup$

add a comment | 

0

$begingroup$

There are n people at that party. That means everyone can shake hands with $0$ to $n-1$ other persons.
Now let X be the set of people that don't shake other peoples hand and do a case analysis.

$|X|=0$
Then there are n people with $1$ to $n-1$ possible handshake partners(which are in sum n-1 possibilities). Now you can apply the pidgeonhole principle.

$|X|=1$
Then we have a new set of $n-1$ persons that shake at least the hand with one person. That can shake $1$ to $n-2$ the hand. Apply the pidgeonhole principle.

$|X| >= 1$
Trivial true.

share|cite|improve this answer

answered Jan 2 at 22:41

jt0202jt0202

1

$endgroup$

add a comment | 

2 Answers
2

active

oldest

votes

2 Answers
2

active

oldest

votes

active

oldest

votes

active

oldest

votes

1

$begingroup$

Suppose there are $n$ people at the party.

The most gregarious person there shakes at most $n-1$ hands. i.e. everyone but himself.

It is possible that someone is a germaphobe who doesn't shake anyone's hand. However, it is not possible for both one person to shake everyone's hand and one person to shake nobody's hand.

This leaves $n-1$ pigeon holes.

If $n$ people count a different number of handshakes, that is $n$ pigeons.

If there are more pigeons that pigeon-holes, at least one pigeon-hole holds 2 pigeons.

share|cite|improve this answer

edited Jan 3 at 15:41

answered Jan 2 at 22:35

Doug MDoug M

44.3k31854

$endgroup$

add a comment | 

1

$begingroup$

Suppose there are $n$ people at the party.

The most gregarious person there shakes at most $n-1$ hands. i.e. everyone but himself.

It is possible that someone is a germaphobe who doesn't shake anyone's hand. However, it is not possible for both one person to shake everyone's hand and one person to shake nobody's hand.

This leaves $n-1$ pigeon holes.

If $n$ people count a different number of handshakes, that is $n$ pigeons.

If there are more pigeons that pigeon-holes, at least one pigeon-hole holds 2 pigeons.

share|cite|improve this answer

edited Jan 3 at 15:41

answered Jan 2 at 22:35

Doug MDoug M

44.3k31854

$endgroup$

add a comment | 

1

1

1

$begingroup$

Suppose there are $n$ people at the party.

The most gregarious person there shakes at most $n-1$ hands. i.e. everyone but himself.

It is possible that someone is a germaphobe who doesn't shake anyone's hand. However, it is not possible for both one person to shake everyone's hand and one person to shake nobody's hand.

This leaves $n-1$ pigeon holes.

If $n$ people count a different number of handshakes, that is $n$ pigeons.

If there are more pigeons that pigeon-holes, at least one pigeon-hole holds 2 pigeons.

share|cite|improve this answer

edited Jan 3 at 15:41

answered Jan 2 at 22:35

Doug MDoug M

44.3k31854

$endgroup$

Suppose there are $n$ people at the party.

The most gregarious person there shakes at most $n-1$ hands. i.e. everyone but himself.

It is possible that someone is a germaphobe who doesn't shake anyone's hand. However, it is not possible for both one person to shake everyone's hand and one person to shake nobody's hand.

This leaves $n-1$ pigeon holes.

If $n$ people count a different number of handshakes, that is $n$ pigeons.

If there are more pigeons that pigeon-holes, at least one pigeon-hole holds 2 pigeons.

share|cite|improve this answer

edited Jan 3 at 15:41

answered Jan 2 at 22:35

Doug MDoug M

44.3k31854

share|cite|improve this answer

share|cite|improve this answer

edited Jan 3 at 15:41

edited Jan 3 at 15:41

edited Jan 3 at 15:41

answered Jan 2 at 22:35

Doug MDoug M

44.3k31854

answered Jan 2 at 22:35

Doug MDoug M

44.3k31854

answered Jan 2 at 22:35

Doug MDoug M

44.3k31854

44.3k31854

add a comment | 

add a comment | 

0

$begingroup$

There are n people at that party. That means everyone can shake hands with $0$ to $n-1$ other persons.
Now let X be the set of people that don't shake other peoples hand and do a case analysis.

$|X|=0$
Then there are n people with $1$ to $n-1$ possible handshake partners(which are in sum n-1 possibilities). Now you can apply the pidgeonhole principle.

$|X|=1$
Then we have a new set of $n-1$ persons that shake at least the hand with one person. That can shake $1$ to $n-2$ the hand. Apply the pidgeonhole principle.

$|X| >= 1$
Trivial true.

share|cite|improve this answer

answered Jan 2 at 22:41

jt0202jt0202

1

$endgroup$

add a comment | 

0

$begingroup$

There are n people at that party. That means everyone can shake hands with $0$ to $n-1$ other persons.
Now let X be the set of people that don't shake other peoples hand and do a case analysis.

$|X|=0$
Then there are n people with $1$ to $n-1$ possible handshake partners(which are in sum n-1 possibilities). Now you can apply the pidgeonhole principle.

$|X|=1$
Then we have a new set of $n-1$ persons that shake at least the hand with one person. That can shake $1$ to $n-2$ the hand. Apply the pidgeonhole principle.

$|X| >= 1$
Trivial true.

share|cite|improve this answer

answered Jan 2 at 22:41

jt0202jt0202

1

$endgroup$

add a comment | 

0

0

0

$begingroup$

There are n people at that party. That means everyone can shake hands with $0$ to $n-1$ other persons.
Now let X be the set of people that don't shake other peoples hand and do a case analysis.

$|X|=0$
Then there are n people with $1$ to $n-1$ possible handshake partners(which are in sum n-1 possibilities). Now you can apply the pidgeonhole principle.

$|X|=1$
Then we have a new set of $n-1$ persons that shake at least the hand with one person. That can shake $1$ to $n-2$ the hand. Apply the pidgeonhole principle.

$|X| >= 1$
Trivial true.

share|cite|improve this answer

answered Jan 2 at 22:41

jt0202jt0202

1

$endgroup$

There are n people at that party. That means everyone can shake hands with $0$ to $n-1$ other persons.
Now let X be the set of people that don't shake other peoples hand and do a case analysis.

$|X|=0$
Then there are n people with $1$ to $n-1$ possible handshake partners(which are in sum n-1 possibilities). Now you can apply the pidgeonhole principle.

$|X|=1$
Then we have a new set of $n-1$ persons that shake at least the hand with one person. That can shake $1$ to $n-2$ the hand. Apply the pidgeonhole principle.

$|X| >= 1$
Trivial true.

share|cite|improve this answer

answered Jan 2 at 22:41

jt0202jt0202

1

share|cite|improve this answer

share|cite|improve this answer

answered Jan 2 at 22:41

jt0202jt0202

1

answered Jan 2 at 22:41

jt0202jt0202

1

answered Jan 2 at 22:41

jt0202jt0202

1

1

add a comment | 

add a comment | 

This page is only for reference, If you need detailed information, please check here