Looking for help with problem 11? Let A and B be two sets and let f: A rightarro

Question

Looking for help with problem 11?

Let A and B be two sets and let f: A rightarrow B be a function. use the Pigeonhole Principle to show that if |A| > |B|, then there exist a_1, a_2 A such that a_1 notequalto a_2 and f(a_2) = f(a_2) (that is, f is not one-to-one). Let S be a set of k + 1 greaterthanorequalto 2 integers. Use the Pigeonhole Principle to show that there are at least two integers in S that have the same remainder when divided by k. How many integers must a set S contain to be certain that at least 35 integer in S have the same remainder when divided by 4? A boy has a collection of 20 pennies, 8 nickels, 10 dimes and 15 quarters. How man coins must the boy take from his collection to be certain that he has (a) 12 coins of the same kind? (b) 10 pennies, 5 nickels, 6 dimes or 8 quarters? (c) 15 pennies, 10 nickels, 12 dimes or 8 quarters? (a) How many 6-bit strings begin with 0101 and end with 111? (b) How many 6-bit strings begin with 111 and end with 0101? (c) How many 6-bit strings begin with 1011 or end with 1001? (d) How many 0-bit strings begin with 1010 or end with 1010? Suppose that we fire interested in determining the number of 4-bit strings containing two consecutive 0s. This could be determined by listing all of these 4-bit strings:

Explanation / Answer

11.

There are 4 distinct remainders on division by 4:0,1,2,3

We can have 34 integers corresponding to each remainder so:34*4=136 integers.

If we add one more integer then there will be 35 integers giving same remainder modulo 4.

So, we must have at least:136+1=137 integers

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.