Questech
Anup Rao
1. How many numbers n are such that n! ends with 99 zeros ?
Ans: Five. It can be either 0 or 5. For any given n, number of zeros at the end in n! = [n/5] + [n/52]+ ... Check n=400 satisfies it. (If you cannot guess at the solution directly, then first give bound n to good enough value, write n in base 5 and solve for the coefficients).
2. Ram has three daughters. Suppose with the help of the following details Shyam calculated their ages, and that he could not have calculated the ages if he just knew a and the last two digits of the phone number.
- The product of their ages is 72.
- The sum of their ages is equal to the last two digits of the Ram’s phone number (Shyam knows the phone number).
- The oldest daughter likes chocolate.
What are the ages of the three daughters?
Ans: The possible ages ( factors of 72 ) and their sums are shown below:
Ages: Sum of ages:
1 1 72 74
1 2 36 39
1 3 24 28
1 4 18 23
1 6 12 19
1 8 9 18
2 2 18 22
2 3 12 17
2 4 9 15
2 6 6 14
3 3 8 14
3 4 6 13
We can deduce from the man’s confusion over the phone number that this wasn’t enough information to solve the problem. The chart shows the sum 14 twice for two different age possibilities, which would explain how knowing the building number alone would not have given him the answer. The clue that the “oldest one” started to play the piano rules out “2 6 6” as an answer, because there is no “oldest”. Since the first grad was certain with the piano clue, the first grad’s oldest daughter is 8.3. N cars move on a circular path with same speed. If two cars collide, then they just exchange their velocities (elastic collisions). Can you prove that motion is periodic?
Ans: First assume the cars are identical, then if they have elastic collisions as described above, then we can as will see the situation as if the cars never undergo collision, but just ‘pass through’ each other when they meet. In such a case, the motion repeats itself after every C/v time, where C=circumference and v=constant speed of the cars. Now, if the cars were not identical, then since the collision never changes the relative position of each car with respect to the others (note relative position here does not mean the ‘distance’ between the cars, but just that some car is k positions back), and all the collision does is to cyclically permute the velocities. Therefore, after every C/v time, we have the initial position repeated, but velocities being cyclically permuted. Therefore after certain nC/v time, the velocities must also be same as their initial value (permutation group has finite order).
4. An airplane has 100 seats, and 100 passengers were assigned seats. The first passenger, 'Joe,' enters the plane and rather than sitting in his assigned place, he sits in a random place. The next passengers come one by one and every passenger sits in his assigned seat if it is empty and in a random empty seat if his seat is already taken. What is the probability that the last passenger 'Jim' will sit in his assigned seat?
Ans: Consider a similar story with aggressive non-polite passengers. After Joe took his random seat, every passanger that sees his seat taken bumps Joe from the seat, sits in his assigned seat, and poor Joe goes on to sit in another random seat. Note that when k+1 passengers are sitting down all but Joe sit in their assigned places and Joe sits in a random place among his assigned place and the places of the remaining passengers. Therefore, when the last passenger enters, his place is empty with probability 1/2 and occupied by Joe with probability 1/2.
5. Does the infinite sum
converge?
Ans: Yes. The ratio/rational tests will not work. Use the integral test, where
, from which we can conclude it converges (check that the limit exists).
6. Consider a row of n seats. A child sits on each. How many arrangements are possible if each child is allowed to move by atmost one seat?
Ans: Fn, the nth Fibonacci number.
7. Can you construct a hexagon with sides 1,2,3,4,5,6 with each of the angle being 120 degrees?
Ans: Yes. Take an equilateral triangle of side 10 each and cut of equilateral triangles of side 5,3,1 from the three corners.
8. You are given an empty jar and 100 marbles: 50 white and 50 black. You should put all the marbles into two jars, in anyway you like. Afterwards, you will be blind folded and asked to pick one marble from one of the jars (the jars would be shuffled and you will not know which is which). How many of each coloured marbles should you put to each of the jars so as to maximize your chances of picking up a white marble?
Ans: Put one white marble to one jar and remaining marbles (49 white and 50 black) into the other jar.
9. There are n identical VLSI chips that in principle are capable of testing each other. Each chip can test any other chip and reports whether it is good or bad. A good chip always reports accurately whether the other chip is good or bad, but the answer of a bad chip cannot be trusted. If it is known that more than half of the chips are good, give an O(n) algorithm to find all the bad chips.
Pair the chips into N/2 pairs (assume it is an integer, check it holds for the other case aswell). In each pair, make the chips to test each other. The output for each test will be one of the following :
- Good-Good b) Good-Bad c) Bad-Bad Note: Good-Good => first chip evaluates the second chip to be good, and second evaluates first to be good, in a particular pair.
Eliminate all the pairs which corresponds to category (a). From category (b) eliminate all the chips which have been evaluated to be ‘bad’ and from (c), eliminate from each pair any one of the two chips.
Check that now the problem is reduced to <=N/2 witch more than half of the chips good. So, run the program recursively until you are left with one chip, which will be ‘good’, which will take O(n) time.10. Given a directed graph with n vertices. How can you find if there is a vertex such that there is no edge coming into it, but there is an edge going from it to all the other vertices, in O(n) (you can represent the graph by adjacency matrix and assume reading each entry of the matrix takes a unit time)?
Ans: Let Aij denote the (i,j)th element of the adjacency matrix, which is equal to one if there is and edge from ith node to jth node . Start with i=1, and check for j=1 to n if A1j is one. Two cases:
- If yes, then check if all Aj1 are zeros. If yes, the output is true and if no, the output of the program is false.
- If no, then say A1k =0, where k is first such number. Then repeat the above step for i=k, and j=k+1 to n. If all are 1, then j=1 to k-1 (in this case the program outputs 1 iff Akj =1 for j=1 to k-1 aswell. If for some j in {K+1, ... ,n}, Akj =0, then repeat the above steps as in the case of i=1.