(ii) A factory makes automobile parts. Each part has a code consisting a letter
ID: 3142162 • Letter: #
Question
(ii) A factory makes automobile parts. Each part has a code consisting a letter (A-Z) followed by three digits (0-9), such as C117, K076, or Z920. If the factory makes 60,000 parts, prove that at least three (3) of them must have the same serial number. (10/100) (iii) Find gcd(20!, 12!), (50! mod 50), and P(P({ phi})), where P denotes the power set of a set. (15/100) (iv) Which of the following functions grows faster, (n^1,000,000 + n middot log_2 n) or (1.001^n - n middot log_2 n)? Justify your answer.Explanation / Answer
(ii) Let us find the total number of codes possible.
The first letter can come in 26 ways.
The next three digits can come in 10 ways each.
So the total number of codes = 26 * 10 * 10 * 10 = 26000.
Number of parts made = 60000
According to Pigeon hole principle, there should be one code that is shared by [60000/26000] + 1 = 2 + 1 = 3 parts.
Thus atleast 3 of them must have same serial number.
(iii) 20! = 12! * 13 * 14 * .....20
Thus 12! is a factor of 20!
Thus gcd(20!,12!) = 12!
50! = 50 * 49!
Thus 50! is divisible by 50
=> 50! mod 50 = 0
P({}) = {}
P(P({})) = {}
(iv) Let f(n) = n1,000,000 + n log2 n
Differentiating,
f'(n) = 1,000,000 n999,999 + log2 n + (1/ln 2)
Let g(n) = 1.001n - n log2 n
Differentiating,
g'(n) = 1.001n ln 1.001 - log2 n - (1/ln 2)
If we continue in this way, the power of n in the derivative will diminish by1 each time and will eventually drop to 0.
The second function will continue to grow exponentially.
As a result, the second function grows faster.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.