|
Geometry Puzzle Let us first get the obvious things out: Since AOB (also DOE) and DCE are right angles and DC = CE = 60, DCEO is a square. Now, as DC and OE are parallel lines, angles DCA and EBC are same, which means that AD / DC = CE / EB. Using AD = x, CE = y and DC = CE = 60, AD / DC = CE / EB » x/60 = 60/y » x * y = 3600 » eq. I Since AOB is a right triangle, AO2 + OB2 = AB2. Using AO = x + 60, OB = y + 60, AB = 221, (x + 60)2 + (y + 60)2 = 2212 » eq. II At this juncture, it is easy to deduce the value of x, using trial and error (or by looking at the pythagorean triplets of 221), but let us move forward and do this using equations. To make the solution generic, let us use d = 221 and l = 60. So, eq. I becomes, xy = l2 » eq. III Also, eq. II becomes, (x + l)2 + (y + l)2 = d2 » eq. IV Even though eq. III and eq. IV looks simple enough, trying to deduce x or y from these two is not easy as we need to solve a polynomial equation of order 4. So, let us look to simplify this further. Expanding eq. IV, x2 + 2*l*x + l2 + y2 + 2*l*y + l2 = d2 » x2 + y2 + 2*l2 + l*(x+y) = d2» eq. V Using eq. III in eq. V, x2 + y2 + 2*x*y + l*(x+y) = d2 » (x + y)2 + 2*l*(x + y) = d2 » (x + y) * (x + y + 2*l) = d2 » eq. VI Assigning, z = (x + y + l) in eq. VI, (z - l) * (z + l) = d2 » z2 = l2 + d2 » x + y + l = sqrt(l2 + d2) » eq. VII For l = 60 and d = 221, using eq. III and eq. VII, x can be determined as 144 or 25. Utilizing the final condition in the puzzle (OA is longer than OB), x > y, which means that x = 144 and OA = x + 60 = 204. Also, for the general case, using eq. III and eq. VII, x = {[sqrt(d^2 + l^2) - l] + sqrt[(d^2 + l^2) - 2*l*sqrt(d^2 + l^2) - 3*l^2]} / 2 Factor of Sums In general, if k1 * n1 = k2 * n2, 1. If k1 = k2, both n1 & n2 is divisible by n1 + n2 {n1 + n2 = 2 * n1 = 2 * n2} 2. If k1 = m * k2 where 'm' is an integer, only n1 is divisible by n1 + n2 {n1 + n2 = (m + 1) * n1 = (1/m + 1) * n2} Now, let us consider a, b, c, d as the four distinct integers. And say: a + b = r1 * (c + d) » eq. I a + c = r2 * (b + d) » eq. II a + d = r3 * (b + c) » eq. III If r1 = r2 = r3 = 1, all the pairs (a + b, a + c, a + d, b + c ... etc) are divisible by a + b + c + d, using statements 1 & 2 In this case, substituting r1 = 1 in eq. I, a + b = c + d » d = (a + b - c). Substituting this in eq. II and using r2 = 1, a + c = b + (a + b - c) » 2c = 2b, which breaks the original assumption that c ≠ b. So, if r1 = 1, r2 ≠ 1 and hence all six pairs cannot be divisible by a + b + c + d. Similarly, if r1 = 1, r3 ≠ 1 and hence more than four pairs cannot be divisible by a + b + c + d. Now, if we substitute r1 = 1, r2 = m and r3 = n, where m, n are positive integers, greater than 1. Using this in eq. I, a + b = c + d » d = (a + b - c) » eq. IV Substituting eq. IV and k2 = m, in eq. II, a + c = m * (b + a + b - c) » (m + 1) * c = 2 * m * b + (m - 1) * a » eq. V Substituting eq. IV and k3 = n, in eq. III, a + a + b - c = n x (b + c) » 2 * a = (n - 1) * b + (n + 1) * c » eq. VI Using, eq. V in eq. VI 2 *(m + 1) * a = ( n - 1) * (m + 1) * b + (n + 1) * [2 * m * b + (m - 1) * a] » [(n + 1) * (m - 1) - 2 * (m + 1)] * a + [( n - 1) * (m + 1) + (n + 1) * 2 x m] * b = 0 » eq. VII Using, m = 2 and n = 3 in eq. VII, [4 * 1 - 2 * 3] * a + [2 * 3 + 4 * 2 * 2] * b = 0, or 11b = a Using this in eq. V, 3 * c = 2 * 2 * b + 11 * b, or c = 5 * b. Similarly, from eq. IV, d = (11 + 1 - 5) * b = 7 * b. For example, setting b = 1: a = 11, b = 1, c = 5, d = 7, a + b + c + d = 24, which is divisible by four pairs, 11 + 1, 5 + 7, 1 + 5 and 1 + 7. Substituting different values of m, n, b in eq IV, V & VII, we can obtain many combinations like this. Car Thief and Lie Detector This is a fairly simple puzzle - the key is to pick up the fact that there can only be four true statements. Also, suspect A's third statement is already known to be true (this is part of the question statement itself). Now, note that there are three pairs of contradicting statements as well. B in his first statement contradicts D's first statement. B's second statement and D's third statement is also contradictory. Finally, C's third statement contradicts with D's second statement. Only one from each pair can be true ... more importantly, one from each pair should be true. So, we already have four true statements and everything else should be a lie! Now, look at the second statement of C, which has to be a lie. This means, B is the thief! To complete the solution, the true statements are A's first, B's second, D's first and D's second statements. Everything else is a lie! Btw ... the police chief does not know that A's third statement is true and thats why it may be difficult for him. Match the Following Well ... this one is tough to explain :( You basically have to consider all the hints and arrive at the full matrix which is:
Searching Two-Dimensional Array The easiest approach is obviously a linear search, individually on all rows. This will give you the result @ O(n*m). An easy modification of this algorithm is to convert the individual linear searches to binary searches. i.e., binary search individually on all rows. The order here is O(m*log(n)), assuming n > m. Another easy search algorithm is to start with the lower left cell, lets say en,0. If the value we are searching for, 'v', is less than en,0, the last row may be eliminated (since all elements in this row is greater than the first element en,0 and hence greater than v). If v > en,0, the first column may be eliminated, since all elements in this column are less than the last element en,0 and hence lesser than v. Now, we have a smaller 2-d array of dimension either (n-1) * m or n * (m-1). If we continue the same algorithm with this smaller 2-d array, we can finally get to the result after n+m comparisons. A slightly more involved algorithm with compareable number of comparisons is the best I know of:
This evaluates to S = log(m*(n/m)) + 2*log((m/2)*(n/m)) + 4*log((m/4)*(n/m)) + ... + (m/2)*log(2*(n/m)). Taking out the common log(n/m), this will become: S = [1 + 2 + 4 + ... + m/2]*log(n/m) + [log(m) + 2*log(m/2) + 4*log(m/4) + ... + (m/2)*log(2)] Now, the first portion of this expression evaluates to (m-1)*log(n/m) or approximately m*log(n/m) for large m. The second portion can be simplified, with the relation m = 2k, to k + 2*(k-1) + 4*(k-2) + ... + 2(k-1)*1. Converting this to a series and taking out m = 2k as common factor, S = m*log(n/m) + m*∑ik= 1 i / 2i. This may be approximated to, S = m * [log(n/m) + ∑ik= 1 i / 2i]. Lets say S1 = ∑ik= 1 i / 2i, for S = m * [log(n/m) + S1] Now, S1 = [∑ik= 1 1 / 2i + ∑ik= 2 1 / 2i + ∑ik= 3 1 / 2i + ... +∑ik= k-1 1 / 2i] This can be simplified to S1 = [(1-2-k) + (1-2-k)/2 + (1-2-k)/4 + ... + (1-2-k)/2(k-1)] ~= 2, again for large k. Hence, S = m * [log(n/m) + 2] The last two methods have similar complexities, with the O(n+m) offering a lot of simplicity in terms of implementation. Mostly, if n & m are compareable, the O(n+m) algoritm may be the prefered one. For n = m, both evaluates to 2*n, for n = 2*m, again both evaluates to 3*m. For all in between values, the O(n+m) algorithm may be better. But, with n > 2*m, the last algorithm starts to get better, with the number of comparisons evaluating to 17*m and 6*m respectively for n = 16*m. Choosing Weights First, let us find out how many weights will be needed to measure all integer weights from 1kg - 40kg. It being a common balance, u can put the weights on both sides of the balance. So, with every weight u have the option of using it on the either sides or not using it. i.e., three possibilities. So, the values u can measure using 'N' weights is 3N. Now, if none of the weights are used, its weight '0' and is useless. Also, if a weight is kept on the right or left, its practically the same. Hence, the practical (positive) numbers u can weigh is (3N - 1) / 2. So, for our solution, (3N - 1) / 2 >= 40; which means N >= 4. Infact, u can weigh from 1 upto 40kg, with 4 weights, provided there is no two ways of measuring the same weight! Now, this expression can give us useful hints on how to choose the weights as well:
Faulty Ball As usual, lets try to solve the easier problem: The solution (like every other problem related to common balance) is related to base 3 or divide by 3 and conquer. Group the balls in to three, each containing three balls each. Now, place two of the groups on either sides of the common balance. If any of the side is lighter, then the problem is reduced to finding the faulty ball among 3. If the scale stays straight, the faulty ball is outside. Again, a problem of finding the faulty ball from a group of 3, which can be done in one more weighing. But, the solution to the 13 ball problem is a li'l more involved. Here, the main problem is that u dont know whether the faulty ball is overweight or underweight. So, if the scale tilts, u still dont know if the faulty is on the right side or the left side :( The key here is to divide the problem into smaller chunks. Lemme start with a question. What is the number of balls from which u can identify a faulty one in one weighing, if u r provided with a reference ball? The answer is two. Keep one of the balls in the scales, with the reference ball on the other side. If the scale tilts, u got the faulty. If it didnt the other ball is faulty. Remember, u dont have to find the nature of the fault. Now, what abt two weighings? We already know that the faulty one can be seperated from a group of two balls, in a single weighing. And, we'll need one more weighing to converge the faulty ball into a group of two. So, the faulty ball can be identified from a group of four balls. But, is that it? Lets look at the process once more: we pick up the first two balls and compare it with each other. If the scale tilts the faulty one is in the scales and if it doesn't, its outside. Now, we have converged to a group of two balls and in one more weighing we can identify the faulty ball. Also, note that we have two reference balls after the 1st weighing and we really dont need additional reference balls! But, here, we are not making use of the reference balls. Lets modify the procedure slightly and start with a group of 5 balls (labelled A, B, C, D, E) and a reference ball (labelled R):
Speed of the River The trick is in chosing the right frame of reference. Lets say its fixed as the flow of the river. Once this is done, the log is still (wrt the frame of reference) and the man is roving at the same speed in both directions (again, wrt the frame of reference) and also covered same distance up and down, in between spotting the log. Obviously he'll take same time for both up and down journeys, which is 1hr! So, the total time elapsed = 2 hrs and the log moved 1 mile in that time. So, the answer is 1/2 miles per hr. For those who love equations, let the speed of the river be 'u' and the man's be 'v' (both in miles per hr), the distance he covered upstream in 1 hr be 's' miles and the time taken for the return journey be 't' hrs. So, we have, s = (v - u) * 1hr = v - u => (I) The distance he covered during his return journey is s + 1mile, = s + 1 and we have, s + 1 = (v + u) * t => (II) Also, the log covered a distance of 1 mile in 't' + 1 hrs at a velocity of 'u'. So, we have, 1 = u * (t + 1) => (III) Substituting eq (III) in eq (II), s + 1 = v * t + u * t => s + u * (t + 1) = v * t + u * t => s + u * t + u = v * t + u * t => s + u = v * t => (IV) Using the value of 's' from eq (I), v - u + u = v * t => v = v * t, t = 1 [This is basically the same outcome as shifting the frame of reference] Now, substituting t = 1 in eq (III), we have 1 = u * (1 + 1), Hence u = 1/2 miles per hr, which ratifies the original solution. Candy Packets Lets try to solve the easier problem first, with packet sizes of 3 and 20. Its easy to see that any number which is a multiple of 3 (of the form 3n), its always possible - just use packets of 3 Also, note that 20 itself is one less than a multiple of 3 (of the form 3n - 1). So, any number which is one less than a multiple of 3 (of the form 3n - 1), can be easily made by using one 20 packet and the remaining by 3 packets. For numbers in this category, it has to be higher than or equal to 20. So, counts like 17, 14, 11, 8, 5 and 2 cannot be made using packet sizes of 20 and 3. Meanwhile, 20, 23 (20 + 3), 26 (20 + 3 + 3) ... etc is always possible. Now, what abt the numbers which are one more than a multiple of 3. i.e., of the form 3n + 1? Here, we need to use two 20 packets, since 40 is also of the form 3n + 1! Now, using the same logic as before, counts like 40 (20 + 20), 43 (20 + 20 + 3), 46 (20 + 20 + 3 + 3) ... etc is always possible. But, what about numbers like 37, 34, 31 ... etc upto 1? They cannot be made using 20 and 3 sized packets. So, the answer in this case is 37! Now, for packet sizes of 6, 9 and 20. Any multiple of 3 can be made as long as it is higher than 3, like 6, 9, 12 (6 + 6), 15 (9 + 6) ... and so on. To prove this: For numbers, 3n with an even 'n' = 2 * m, 3n = 3 * 2 * m = 6m, so we can just use 'm' packets of size 6. For numbers, 3n with an odd n = 2 * m + 1 = 3 * 2 * m + 3 = 6m + 3 = 6 * (m - 1) + 9, just use 'm - 1' packets of size 6 and 1 packet of size 9. This is possible only if m > 1. Hence, all multiples of 3 greater than 3 is fine. Now, for numbers of the 3n + 1 and 3n - 1, the same rule applies as packet size 3 and 20. The only exception being 23 and 43! Hence, the answer is 43! Birthday Puzzle Consider that this happened some day in 2003, say oct 6th. The possible birthdates are
x - 1000 * y1000 - 100 * y100 - 10 * y10 - y1 - 1 = y1000 + y100 + y10 + y1 => (II) eq (I) is for completed years and (II) for incomplete years (that is when the mathematician cannot guess) Here, x is the year in which this happened, y1000, y100, y10, y1 are the 1000th, 100th, 10th and 1s position of the year in which somebody is born Now, y1000 is always 1, except for 21st century case (if u try 21st century cases 2000, 2001, 2002, u can see that they wont fit), y100 = 8 or 9 So the eqs gives four more eqns: x - 1900 - 10 * y10 - y1 = 1 + 9 + y10 + y1 => (III) x - 1800 - 10 * y10 - y1 = 1 + 8 + y10 + y1 => (IV) x - 1900 - 10 * y10 - y1 - 1 = 1 + 9 + y10 + y1 => (V) x - 1800 - 10 * y10 - y1 - 1 = 1 + 8 + y10 + y1 => (VI) Our aim is to find positive integer solutions for x, y10 and y1, which satisifies (III) and (IV), but does not satisfy (V) and (VI) Reducing the equations: x - 1910 = 11y10 + 2y1 => (III) x - 1809 = 11y10 + 2y1 => (IV) x - 1911 = 11y10 + 2y1 => (V) x - 1810 = 11y10 + 2y1 => (VI) Please observe that x > 1910 (age is always positive) and 0 <= y1, y10 < 10. This will imply
Product 'n Sum A : I know that you don't know the numbers B : Now I know the numbers A : Now I also know the numbers. (The first statement of B is redundant and is removed) Assume, with 75% loss of generality, that A and B are men Let the numbers be X and Y, both given to be integers between 2 and 99. Let S = X+Y and P = XY We define (X,Y) to be a feasible factorisation of a product P, if X and Y are integers between 2 and 99 such that P = XY. We say that P has unique feasible factorisation property if P has exactly one feasible factorisation. In particular, if P is a product of two primes it has uffp. Clearly, B can find X and Y from P iff P has uffp. If N can be written as U+V such that UV has uffp then we say that N is insecure. From A's first statement, it follows that S is secure. Since Goldbach's conjecture has been checked upto 1014 > 200, every even number up to 100 can be written as the sum of two primes, and is therefore insecure. Also, N+2 is insecure whenever N is prime. Observe that for all N, P = 53N has uffp, since (53,N) is the only feasible factorisation of P. Thus N is insecure, for 55 <= N <= 152 Also P = 97N has uffp, so that N is insecure, for 99 <= N <= 196 197 is insecure, since 98*99 has uffp. That leaves only the following numbers as candidates for S: 11,17,23,27,29,35,37,41,47,51,53 After A makes his first statement, B comes up with this list of candidates for S. He now computes the sum U+V for each feasible factorisation (U,V) of the product P. Exactly one of these has a secure sum. Thus he is able to find X and Y from P. He announces that he has found X and Y. On hearing this, A announces that he has found them too. For what value(s) of S is this possible? Suppose 2a + p = S = 2b + q, with a > b >= 1, and p,q odd primes. B knows that S is odd. Both 2a * p and 2b * q have exactly one feasible factorisation (X,Y) with X+Y odd. In either case, B would be able to find out the numbers. So, given S, there is no way A can tell whether the factorisation was (2a,p) or (2b,q) Note that this rules out:
Ant 'n Rod The crux of the problem is in understanding the word 'stretch'. Consider a rubber band with a pen mark 1cm away from one end. Now 'stretch' the band so that it becomes twice the size. How far is the pen mark from the end point ? 2 cm ? Now, say the ant covered 1 cm in the 1st second. and the rod grew to 3km from 1km. How far is the ant from the end. 3cm. Now the ant moves another cm and the rod grows from 3 to 5kms. How far is the ant now from the end ? 4 * 5 / 3 cms. If you extend this, the distance covered by the ant in cms after 'n' seoncds is d = ( .... (((1*3 + 1)*5/3 + 1)*7/5 + 1) *9/7 .... + 1)*(2n+1)/(2n-1) + 1) => (I) Simplifying, d = (2n+1) + (2n+1)/3 + (2n+1)/5 + ... + (2n+1)/(2n+1) => (II) Ofcourse the length of the rod in kms is l = 2n+1, which is l = 105*(2n+1) in cms Now, the time the ant reaches the other end l <= d, which will give (2n+1) * 105 <= (2n+1) + (2n+1)/3 + (2n+1)/5 + ... + (2n+1)/(2n+1) On simplifying 105 <= 1 + 1/3 + 1/5 + 1/7 + ... + 1/(2n+1) => (III) This is seemingly impossible. But the truth is that the above series is a non convergent series. So, theoritically the ant should reach the other end (if it leaves for that much time) Now, to get an idea of the time required, observe that each term on RHS is less than or equal to 1. This means n has to be atleast 105, which is big. So we can use an integral approximation and estimate the value of n. Let me do it for you: S(n) = ∑in= 0 1 / (2i + 1) => (IV) S(n) = ∑in= 0 [ (2n + 1) / (2i + 1) ] / (2n + 1) => (V) Now say x(i) = [ (2i + 1) / (2n+ 1) ] => (VI) Eq (VI) => δx = x(i) - x(i-1) = 2 / (2n + 1) => δx = 2 / (2n + 1) => (VII) Using these, 2 * S(n) = ∑x(i) =11/(2n+1) 1/x(i) * δx => (VIII) Observing that n > 105, n » 1, δx tends to zero, we can use the definition of integral Thus 2 * S(n) ~ ∫1 /1(2n+1) (1/x) dx => (IX) 2 * S(n) ~ ln(2n+1) => (X) Using the approximate value for S(n) in eq (III) 100000 <= ½ * ln(2n+1), 2n + 1 >= e200000, n >= ½ * (e200000 - 1) This is an approximate value for 'n'. If u didnt get the enormity of this number, its about x years, where x is 1085 followed by 460506 zeors !!!!!!!!!!!!!!!!!!!!!!!! Power
long power( unsigned long base, int index )
{
long result = 1;
while ( index ) {
if ( index & 1 ) result *= base;
base *= base;
index >>= 1;
}
return result;
}
Now, dont ask me how will it work, its written in simple 'C'. Go figure. And you are welcome to let me know if you have a more efficient program in terms of memory usage and number of operations. I feel that 'if' condition for checking the last digit of 'index' can be optimized further.
|