Show that in any finite gathering of people, there are at least two people who know...

Show that in any finite gathering of people, there are at least two people who know the same number of people at the gathering (assume that “knowing” is a mutual relationship). Hint available.

Solutions

Expert Solution

Lets recall the Pigeon hole principle, it says if we have n+1 pigeon and n holes and we have to put the all pigeon in the holes then there will be at least one hole in which there are two pigeon.

Now lets come to the problem , let we have n no of people in the gathering then there is two case

case -1 there is one person who knows everyone that means each one knows at least one person(because "knowing" is a mutual relation ) ,so the set that represent the possible no of people one can know is {1,2,......,n-1},but we have n people so by Pigeon hole principle there will be at least two person who know the same no of people.

case-2 there is a person who does not know anyone that means each people can know at most n-2 people ,so out set of possibility is given as {0,1,2,.......,n-2} ,but we have n people so again using Pigeon hole principle there will be at least two people who know same no of people.

Colby Messinger answered 1 year ago

Next > < Previous

Related Solutions

Identify the task. Pick at least three people that you know, who also know how to...

Identify the task. Pick at least three people that you know, who also know how to do the task. Ask the person to perform the task. Identify each person and record the time it takes for the person to complete the task. Perform a rate of work calculation to determine how long it would take all people assessed to perform the task together. Share your calculations. Does the value you calculated make sense? Why? Would it be reasonable to have...

Consider any two finite sets A and B. Prove that |A×B|=|A||B|

iii Show that any finite Lattice L has a b0 and b1, where t ≥ b0,...

iii Show that any finite Lattice L has a b0 and b1, where t ≥ b0, t ≤ b1, for all t ∈ L.

Jenny wanted to know if people who exercise regularly eat more apples than people who don’t...

Jenny wanted to know if people who exercise regularly eat more apples than people who don’t exercise regularly. She took a simple random sample of six people who exercise. Their standard deviation was 2.00. She then took a new simple random sample of eight people who don’t exercise. Their standard deviation was 1.51. Please calculate the test statistic for this experiment; then state the critical value; then come to a conclusion concerning the null hypothesis; and then state what the...

Neutralization theory suggests that people who break the law know

Problem 7. Show that in a room full of 20 people there are 2 people who...

Problem 7. Show that in a room full of 20 people there are 2 people who have the same number of friends present. Friendship is symmetric. If A is friends with B then B is friends with A.

Finite Math Four fair six sided dice are rolled. Given that at least two of the...

Finite Math Four fair six sided dice are rolled. Given that at least two of the dice land on an odd number, what is the probability that the sum of the result of all four dice is equal to 14?

If you want to know if there is any difference at all in how many people...

If you want to know if there is any difference at all in how many people prefer any of five different salad dressings, you would do what kind of test? Chi square goodness of fit Chi square test of independence Independent sample (simple) ANOVA Repeated measures(matched sample)ANOVA Factorial ANOVA

Requirements Gathering (Online Questionnaire) Task : Creating Google Form Consider any requirements gathering problem, create a...

Requirements Gathering (Online Questionnaire) Task : Creating Google Form Consider any requirements gathering problem, create a google form to gather related data, and try it by circulating it to your classmates make sure that your questionnaire contains multiple question types i.e. Short answers, paragraphs, multiple choice, checkboxes, Dropdown, Linear scale, Multiple choice grid, date, and time Hints: the problem could be term project of any of your courses. Ask your instructor to assist in choosing the problem and in designing...

Some studies show that people who think they are intoxicated will show signs of intoxication, even...

Some studies show that people who think they are intoxicated will show signs of intoxication, even if they did not consume alcohol. To test whether this is true, researchers had a group of five adults consume nonalcoholic drinks, which they were told contained alcohol. The participants completed a standard driving test before drinking and then after one nonalcoholic drink and after five nonalcoholic drinks. A standard driving test was conducted in a school parking lot where the participants had to...

Subjects