Geometry PuzzleLet 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, AO ^{2} + OB^{2} = AB^{2}.Using AO = x + 60, OB = y + 60, AB = 221, (x + 60) ^{2} + (y + 60)^{2} = 221^{2} » 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 = l ^{2} » eq. IIIAlso, eq. II becomes, (x + l) ^{2} + (y + l)^{2} = d^{2} » 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,x ^{2} + 2*l*x + l^{2} + y^{2} + 2*l*y + l^{2} = d^{2} »x ^{2} + y^{2} + 2*l^{2} + l*(x+y) = d^{2}» eq. V
Using eq. III in eq. V,x ^{2} + y^{2} + 2*x*y + l*(x+y) = d^{2} »(x + y) ^{2} + 2*l*(x + y) = d^{2} »(x + y) * (x + y + 2*l) = d ^{2} » eq. VI
Assigning, z = (x + y + l) in eq. VI,(z - l) * (z + l) = d ^{2} »z ^{2} = l^{2} + d^{2} »x + y + l = sqrt(l ^{2} + d^{2}) » 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 SumsIn 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 DetectorThis 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 FollowingWell ... this one is tough to explain :( You basically have to consider all the hints and arrive at the full matrix which is: - Norwegain has a yellow house (which is the first one), drinks water, smokes Dun Hill and has Cats as pet.
- Dane is at the second house, which is blue, drinks tea, smokes Blend and has Horses.
- Brit is at the center red house, drinks milk, smokes Pall Mall and rears Birds.
- German is the next, in a green house. He drinks coffee, smokes Prince Blue and and has ... well Fish.
- Swede is in the last white house. He drinks beer, smokes Blue Master and has a dog as pet.
Searching Two-Dimensional ArrayThe 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 e _{n,0}. If the value we are searching for, 'v', is less than e_{n,0}, the last row may be eliminated (since all elements in this row is greater than the first element e_{n,0} and hence greater than v). If v > e_{n,0}, the first column may be eliminated, since all elements in this column are less than the last element e_{n,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:- Do a linear search along the top-left to bottom-right diagonal of the 2-d array. Since m may not always be same as n, the diagonal may not be easy to identify. But, it will suffice to choose elements approximating a diagonal of length max(n,m). Lets say, n, in this case, since we are assuming n > m.
- Now, the last element in this diagonal which is lesser than v, helps us eliminate the rectangle smaller than this diagonal element.
- Similarly, the first element in this diagonal which is greater than v, helps us eliminate the rectangle higher than this diagonal element.
- Note that both the elements are next to each other and may be found after a max of log(n) comparisons.
- Also, after eliminating the two rectangles, we'll be left with two rectangles to the top right and bottom left of the elements found.
- Now, recursively search in these smaller rectangles.
^{k}. For this case, S = log(n) + 2*log(n/2) + 4*log(n/4) + ... + (m/2)*log(2*(n/m)).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 = 2 ^{k}, to k + 2*(k-1) + 4*(k-2) + ... + 2^{(k-1)}*1.Converting this to a series and taking out m = 2 ^{k} as common factor, S = m*log(n/m) + m*∑_{i}^{k}_{= 1} i / 2^{i}.This may be approximated to, S = m * [log(n/m) + ∑ _{i}^{k}_{= 1} i / 2^{i}].Lets say S1 = ∑ _{i}^{k}_{= 1} i / 2^{i}, for S = m * [log(n/m) + S1]Now, S1 = [∑ _{i}^{k}_{= 1} 1 / 2^{i}
+ ∑_{i}^{k}_{= 2} 1 / 2^{i} + ∑_{i}^{k}_{= 3} 1 / 2^{i} + ... +∑_{i}^{k}_{= k-1} 1 / 2^{i}]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 WeightsFirst, 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 3 ^{N}. 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 (3^{N} - 1) / 2.
So, for our solution, (3^{N} - 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:- For N = 1, 1kg is the obvious choice and u can only measure 1kg using that.
- For N = 2, u can measure from 1kg to 4kg (using the formula) and the obvious choices are 1kg and 3kg.
- For N = 3, u can measure from 1kg to 13kg and the choice of weights are not as straightforward. But, lets say u retained 1kg and 3kg (atleast we dont have any overlap from 1 to 4) and want to pick up one more weight, say X. We have, 1 + 3 + X = 13 and X = 9. Now, one can easily verify that 1, 3 and 9 is a good choice if u r asked to pick up three weights.
_{i}^{N}_{= 0}3^{i} = (3^{(N+1)} - 1) / 2! But, what I cudnt prove was that this is the only way of chosing the weight! Lemme know if anybody has a proof for this.
Faulty BallAs 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): - Weigh with R, A on first side and B, C on the second side.
- If the scale stays straight, the faulty ball is one of D or E. Place R on one side of the scale and D on the other side to identify the faulty one.
- If the scale tilts to one side (lets say, R, A is heavier), we know that either A is has one kind of fault or one among B, C has the other kind of fault (A is heavier or one among B and C is lighter).
- For the 2nd weighing, place A, B on first side and two reference balls (R and one among D, E) on the other side.
- If the scale tilts to the same side as in the previous weighing, the faulty ball is A.
- If the scale tilts to the opposite side compared to the previous weighing, the faulty ball is B.
- If the scale stays straight, the faulty ball is C.
- Split the group of 13 balls to three subgroups G1 and G2 containing 4 balls each and G3 with 5 balls.
- Place groups G1 and G2 on either side of the scale, if the scale doesnt tilt, the faulty one is in G3 and we can cull it in two more weighings.
- If the scale tilts, we now have a group G1 with one kind of fault or another group G2 with another kind of fault.
- In this case, we will swap three of the balls (say group G4), keep three balls on the same side (say group G5) and keep the remaining two outside (say group G6).
- If the scale tilts to the same direction in the second weighing, the faulty ball is in G4 (the unchanged balls), if it tilts to the other side, the faulty one is in G5 (the swapped balls) and if it doesnt tilt, the faulty one is in G6 (the ones outside).
- For both G4 and G5 we also know the kind of fault and this now reduces to a divide by 3 and conquer.
- For G6, we can make use of the reference ball and find out the faulty one in just one more weighings.
^{N} - 1) / 2 balls among which one is faulty:- Create three groups, group G1 and G2 of size (3
^{(N-1)}- 1) / 2 and another group G3 of size (3^{(N-1)}+ 1) / 2. - Put group G1 on one side and group G2 on the other. If the scale doesnt tilt, we have a group of (3
^{(N-1)}+ 1) / 2 balls (group G3) to cull the faulty one from and a lot of refernce balls. This can be done in (N-1) more weighings (use the algorithm recursively). - If the scale tilts, create three more groups, G4 and G5 with 3
^{(N-2)}balls and G6 with (3^{(N-2)}- 1) balls. G4 is kept at the same side, G5 is swapped and G6 is taken out. This weighing will converge the search space to utmost 3^{(N-2)}and we also know the kind of fault. This can be solved in (N-2) weighings, using divide by 3 and conquer.
Speed of the RiverThe 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 PacketsLets 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 PuzzleConsider that this happened some day in 2003, say oct 6th. The possible birthdates are - All days from 2000 oct 7th to dec 31st (completed age = 2)
- All days from 1978 jan 1 to october 6th (completed age = 25)
- All days from 1982 oct 7th to dec 31st (completed age = 20)
- 2000 jan 2nd to dec 31st
- 1978 jan 1st
- 1982 jan 2nd to dec 31st
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 - for even x < 1922, there is no integer solution for eq (V)
- for even x > 1916 there is no integer solution for eq (VI)
- for 1916 < even x < 1922, eq (III) and eq (IV) has solutions
Product 'n SumA : 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 10 ^{14} > 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 2^{a} + p = S = 2^{b} + q, with a > b >= 1, and p,q odd primes.
B knows that S is odd. Both 2^{a} * p and 2^{b} * 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 (2^{a},p) or (2^{b},q)
Note that this rules out:- 11 = 8 + 3 = 4 + 7
- 23 = 16 + 7 = 4 + 19
- 27 = 16 + 11 = 8 + 19
- 35 = 32 + 3 = 16 + 19
- 37 = 32 + 5 = 8 + 29
- 47 = 16 + 31 = 4 + 43
- 51 = 32 + 19 = 8 + 43
- 17 = 9 + 8; 72 = 9 * 8 = 24 * 3; 24 + 3 = 27 is secure
- 17 = 10 + 7; 70 = 10 * 7 = 35 * 2; 35 + 2 = 37 is secure
- 17 = 11 + 6; 66 = 11 * 6 = 33 * 2; 33 + 2 = 35 is secure
- 17 = 12 + 5; 60 = 12 * 5 = 20 * 3; 20 + 3 = 23 is secure
- 17 = 13 + 4; 52 = 13 * 4 = 26 * 2; 26 + 2 = 28 is insecure (28 = 11 + 17)
- 17 = 14 + 3; 42 = 14 * 3 = 21 * 2; 21 + 2 = 23 is secure
- 17 = 15 + 2; 30 = 15 * 2 = 6 * 5; 6 + 5 = 11 is secure
Ant 'n RodThe 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 = 10 ^{5}*(2n+1) in cms
Now, the time the ant reaches the other end l <= d, which will give (2n+1) * 10^{5} <= (2n+1) + (2n+1)/3 + (2n+1)/5 + ... + (2n+1)/(2n+1)On simplifying 10 ^{5} <= 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 10 ^{5}, which is big. So we can use an integral approximation and estimate the value of n.
Let me do it for you:
S(n) = ∑_{i}^{n}_{= 0} 1 / (2i + 1) => (IV)S(n) = ∑ _{i}^{n}_{= 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) =}^{1}_{1/(2n+1)} 1/x(i) * δx => (VIII)Observing that n > 10 ^{5}, n » 1, δx tends to zero, we can use the definition of integralThus 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 >= e ^{200000}, n >= ½ * (e^{200000} - 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 !!!!!!!!!!!!!!!!!!!!!!!! Powerlong 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. |

© 2015 Sandeep Unnimadhavan