These problems total to 100 points.
(10 points)
Refer to the original definition of modular equivalence to explain each of the following. If it doesn't fit the original definition, does it make sense to extend the definition to allow it, and what would it mean?
(10 points) Rosen 6th ed. 3.5 #32
Show that if a, b, and m are integers such that m≥2 and a≡b (mod m), then gcd(a,m)=gcd(b,m).
(5 points) Let ads be the "alternating digit sum" of n. ads([dm…d1d0]10) = ∑i=0…m (-1)idi.
E.g., ads(48725) = 4-8+7-2+5 = 6. Observe that 48725 ≅ 6 (mod 11).
Prove that for all n∈ℤ, n ≡ ads(n) (mod 11).
(5 points) Rosen 6th ed. 3.7 #22
Use the Chinese Remainder Theorem to show that an integer a, with 0≤a<m=m1m2…mn, where the integers m1, m2, …, mn are pairwise relatively prime, can be represented uniquely by the n-tuple (a mod m1, a mod m2, a mod mn).
(5 points) Rosen 6th ed. 3.7 #46
Encrypt the message ATTACK using the RSA system with n=43⋅59 and e=13, translating each letter into integers and grouping together pairs of integers, as done in Rosen Section 3.7 Example 11.
(10 points) Rosen 6th ed. 5.2 #36
Prove that at a party where there are at least two people, there are two people who know the same number of other people there. (Assume that "knowing" is a symmetric relation.)
(5 points) Rosen 6th ed. 5.2 #42
Let n1, n2, …, nt be positive integers. Show that if n1+n2+…+nt-t+1 objects are placed into t boxes, then for some i in {1, 2, …, t}, the ith box contains at least ni objects.
(10 points)
Consider the set of all strings of length ≤ n over the alphabet Σ = {a,…,z}. What fraction of these strings are of length exactly n? Give your answer as a constant plus a big-O error term that goes to zero as n grows — something like "1/2 + O(1/log(n))". Show your work.
(15 points)
To commemorate the upcoming graduation ceremonies, your college is having a fancy dinner. You have been picked to be in charge of seating arrangements. Unfortunately, after years of living in the same college, not everyone is on speaking terms anymore.
There are n guests and a single large circular table with n place settings. Of course, since n can be fairly large, this has to be set up outside under a big tent.
To arrange the seating, you're thinking about listing all the possible seating arrangements, and you want to know how difficult that will be.
How many ways are there to assign the guests to the table positions?
You realize that if you just rotate the guests around the table, you're not changing any crucial issues of who sits next to whom. Similarly, two seating arrangements are equivalent if in one you list the guests going clockwise and in the other you list them going counter-clockwise, and the two lists are the same. After all, that just flips who is sitting on the left- and right-hand side of each guest. So, how many seating assignments are there if you ignore these equivalences?
The Social Committee reminds you that the guests arrive in pairs, i.e, everyone has a date. (We'll be optimistic here.) Note that this implies n is even. Of course, each couple should be seated together. How many of the arrangements from part (b) satisfy this constraint?
(5 points) Rosen 6th ed. 5.4 #18, slightly reworded
Suppose that b is an integer with b≥7. Use the Binomial Theorem and the appropriate row of Pascal's triangle to find the base-b expansion of the fourth power of (11)b4.
(10 points — 5 points each part) Rosen 6th ed. 5.4 #22ab
Prove the identity C(n,r)⋅C(r,k) = C(n,k)⋅C(n-k,r-k), whenever n, r, and k are nonnegative integers with r≤n and k≤r,
(5 points) Rosen 6th ed. 5.4 #28a
Show that if n is a positive integer, then C(2n,2) = 2C(n,2)+n2 using a combinatorial argument (i.e., a prose explanation based on what these formulas mean conceptually).
(5 points) Rosen 6th ed. 5.5 #60
Suppose that a basketball league has 32 teams, split into two conferences of 16 teams each. Each conference is split into three divisions. Suppose that the North Central Division has five teams. Each of the teams in the North Central Division plays four games against each of the other teams in this division, three games against each of the 11 remaining teams in the conference, and two games against each of the 16 teams in the other conference. In how many different orders can the games of one of the teams in the North Central Division be scheduled?