There are (m − 1)n + 1 people in a room. Show that either there are...

There are (m − 1)n + 1 people in a room. Show that either there are m people who mutually do not know each other, or there is a person who knows at least n others.

Solutions

Expert Solution

If there is a person who knows at least n others then there is nothing to prove.

So assume that no person knows at least n others. That is, given any person, that person knows at most n persons(including himself).

Consider one person among them, say P1. Then since that person knows at most n persons, there are surely (m-1)n+1-n=(m-2)n+1 persons that he doesn't know. Consider a person P2 among them.

So, P1,P2 do not know each other mutually.

Now P2 knows at most n persons among those (m-2)n+1. Thus there are at least (m-3)n+1 in those (m-2)n+1 persons that he doesn't know. Pick a person P3 among them. Now P1,P2,P3 do not know each other mutually.

Continuing like this, we get P1,P2,...,P(m-1) such that they do not know each other mutually and since (m-(m-1+1))+1=1, we are left with at least one person who doesn't know P1,...,P(m-1) mutually. Call that person as Pm.

Thus we have got m persons P1,...,Pm who do not know each other mutually.

This completes the solution.

Colby Messinger answered 1 year ago

Next > < Previous

Related Solutions

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.

Show that M is a subgroup N; N is a subgroup D4, but that M is not a subgroup of D4

D4 = {(1),(1, 2, 3, 4),(1, 3)(2, 4),(1, 4, 3, 2),(1, 2)(3, 4),(1, 4)(2, 3),(2, 4),(1, 3)} M = {(1),(1, 4)(2, 3)} N = {(1),(1, 4)(2, 3),(1, 3)(2, 4),(1, 2)(3, 4)} Show that M is a subgroup N; N is a subgroup D4, but that M is not a subgroup of D4

1. Must be nicely written up AS A PROOF. a. Show that gcd(m + n, m)...

1. Must be nicely written up AS A PROOF. a. Show that gcd(m + n, m) = gcd(m, n). b. If n | k(n + 1), show that n | k. c. Show that any two consecutive odd integers are relatively prime.

Prove via induction the following properties of Pascal’s Triangle: •P(n,2)=(n(n-1))/2 • P(n+m+1,n) = P(n+m,n)+P(n+m−1,n−1)+P(n+m−2,n−2)+···+P(m,0) for all...

Prove via induction the following properties of Pascal’s Triangle: •P(n,2)=(n(n-1))/2 • P(n+m+1,n) = P(n+m,n)+P(n+m−1,n−1)+P(n+m−2,n−2)+···+P(m,0) for all m ≥ 0

A team of size m has to be chosen from a group of n people (m...

A team of size m has to be chosen from a group of n people (m < n) and a captain chosen for the team. (a) How many ways can the captained team be chosen if the captain is chosen first then the remainder of the team chosen. (b) How many ways can the captained team be chosen if the team is chosen first then the captain chosen from the team? This should give the same number as a) but...

Let function F(n, m) outputs n if m = 0 and F(n, m − 1) +...

Let function F(n, m) outputs n if m = 0 and F(n, m − 1) + 1 otherwise. 1. Evaluate F(10, 6). 2. Write a recursion of the running time and solve it . 3. What does F(n, m) compute? Express it in terms of n and m.

10. Assume k is a scalar and A is a m × n matrix. Show that...

10. Assume k is a scalar and A is a m × n matrix. Show that if kA = 0 then either k = 0 or A = 0m x n

Let S={1,2,3,6} and define the relation ~ on S2 by (m,n) ~ (k,l) for m+l=n+k Show...

Let S={1,2,3,6} and define the relation ~ on S2 by (m,n) ~ (k,l) for m+l=n+k Show that it is an equivalent relation Find the number of different equivalent classes and write all of them

A group of n people get on an elevator at Floor 0. There are m floors...

A group of n people get on an elevator at Floor 0. There are m floors besides Floor 0. Each person uniformly randomly chooses one of those m floors to stop at. (All choices are independent, and no one gets on the elevator after Floor 0.) The elevator stops at a floor if at least one person has chosen to stop there. Let X be the number of stops that the elevator makes after Floor 0. (a) What is E[X]?...

By computing both sides, show that for an m × n matrix A, vectors u and...

By computing both sides, show that for an m × n matrix A, vectors u and v ∈ Rn , and a scalar s ∈ R, we have (a) A(sv) = s(Av); (b) A(u + v) = Au + Av; (c) A(0) = 0. Here 0 denotes the zero vector. Is the meaning of 0 on the two sides identical? Why or why not? Hint: Let x = (x1, . . . , xn) and y = (y1, . ....

Subjects