Ryan just bought five cats from a pet store. a) prove that there must be two cat
ID: 2943119 • Letter: R
Question
Ryan just bought five cats from a pet store.
a) prove that there must be two cats in the group that make friends with the same number of cats in the group.
conditions:
*cats getting along with each other is a mutual condition (for example, if there was a white cat that gets along with a black cat, then automatically the black cat is considered to get along with the white cat).
**cats cannot make friends with themselves. only with other cats.
HINT: use the pigeonhole principle, cats are the pigeons , and the holes are the number of friends each cat can have
b) show that this property can be general to a group of n cats. where n is in N
Explanation / Answer
a) The way to go on this problem is what's indicated in the hint. The Pigeonhole Principle states that for m pigeons being slotted into n holes, if m > n then there must be at least one hole that contains more than one pigeon. For this problem, we want pigeons to be the cats and the holes to be the number of friends each cat can have. Since any one cat cannot be friends with itself, it must have 1, 2, 3, or 4 friends, but not 5. However, since there are 5 cats, and we are trying to slot them into the four "holes" of having 1, 2, 3, or 4 friends, by the Pigeonhole Principle, since 5 > 4 we must have at least two cats in the same "hole" -- i.e., at least two cats with the same number of friends. We don't know if multiple cats have 1 friend, or multiple cats have 2 friends, or 3 friends, or 4 friends, but there must be at least two cats with the same number of friends.
** Note: I have assumed here that each cat makes friends with at least one other cat. But what if we allow a cat to have 0 friends? The statement still holds; the proof is only slightly more complicated. Proof by contradiction. Assume each cat has a different number of friends. Then one of each of the five cats must have 0, 1, 2, 3, and 4 friends, since no cat can make friends with itself so cannot have more than four friends (and if we remove a possible number of friends for the cats, e.g. if we only have cats that have 0, 1, 2, or 3 friends, then we have a contradiction already by the Pigeonhold Principle in that 5 > 4 so more than one cat already has the same number of friends, as above). Since friendships are mutual, no other cat is friends with the cat who has 0 friends -- call it cat A -- so the other four cats -- call them cats B, C, D, and E -- must have their friendships among themselves. But that requires the cat with four friends, say that's cat E, to have four friendships by only being friends with cats B, C, and D -- a contradiction, as only three friendships are possible.
b) This generalizes to n cats, because, since no cat can be friends with itself still, the number of friendships each cat can have is 1, 2, 3, 4, ..., n-2, or n-1, but not n. So there are n cats, and n-1 possibilities for number-of-friends-a-cat-can-have. Since n > n-1, by the Pigeonhole Principle there must be more than one cat with the same number of friends.
Once again, that assumes that each cat is friends with at least one other cat, but we can generalize allowing for zero friendships as well. Proof by contradiction: Assume each of cats A, B, C, ..., N has a different number of friends. The numbers of friends the cats have must be 0, 1, 2, ..., n-1, because otherwise we will have our "holes," meaning our possible numbers of friends, be less than n -- and by the Pigeonhole Principle at least one cat has the same number of friends. But if we again remove the cat with 0 friends, the cat with n-1 friends must have n-1 friends among a group of n-1 cats that includes itself, which is impossible as the maximum number of friends it can have is n-2.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.