Sandeep 's World >> Puzzles Unravelled


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:
  1. Norwegain has a yellow house (which is the first one), drinks water, smokes Dun Hill and has Cats as pet.
  2. Dane is at the second house, which is blue, drinks tea, smokes Blend and has Horses.
  3. Brit is at the center red house, drinks milk, smokes Pall Mall and rears Birds.
  4. German is the next, in a green house. He drinks coffee, smokes Prince Blue and and has ... well Fish.
  5. Swede is in the last white house. He drinks beer, smokes Blue Master and has a dog as pet.

Not that this is the only combination which satisfies all the hints. U already know the answer by now ... dont you?


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:
  1. 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.
  2. Now, the last element in this diagonal which is lesser than v, helps us eliminate the rectangle smaller than this diagonal element.
  3. Similarly, the first element in this diagonal which is greater than v, helps us eliminate the rectangle higher than this diagonal element.
  4. Note that both the elements are next to each other and may be found after a max of log(n) comparisons.
  5. Also, after eliminating the two rectangles, we'll be left with two rectangles to the top right and bottom left of the elements found.
  6. Now, recursively search in these smaller rectangles.

The number of comparisons, say S, needed (in worst case), using this method may be approximated, for m = 2k. 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 = 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:
  • 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.

For our problem, we have N = 4. If we retain the original choices 1, 3, 9 and want to choose one more weight X, to measure upto 40, we have 1 + 3 + 9 + X = 40, X = 27.

Another way of arriving at the same number is that, since we already know how to measure till 13, we want the next number 'X', large enough so that X - 13 = 14, the next weight to be measured. This also wil give us, X = 27. Please note that this argument is true even for N = 3 case, since X - 4 = 5, for X = 9.

This gave us one answer, but is that the only answer? I am not really sure about that. I feel it is the only solution and have emperical proofs, but not a generic one :(

It's fun exploring higher values of 'N' too. Like say, N = 5, needs another weight 81, N = 6, needs 243 and so on. Its not a coincidence that all weights used are powers of 3. Infact, this is true for any value of 'N' and can be easily proved (using Principle of Mathematical Induction) since iN= 03i = (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 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):
  • 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.

So, by making better use of the reference ball we can actually identify the faulty ball from a group of five, in two weighings, given a reference ball. This process also outlines a method of swapping one-third and keeping one-third outside, which is again a divide by 3 and conquer method. We'll look at a generalization of this method when we look at higher number of balls.

Now that we know how to handle 5 balls, given a reference ball, and a method of divide by three and conquer, lets try to solve the problem:
  1. Split the group of 13 balls to three subgroups G1 and G2 containing 4 balls each and G3 with 5 balls.
  2. 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.
  3. If the scale tilts, we now have a group G1 with one kind of fault or another group G2 with another kind of fault.
  4. 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).
  5. 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).
  6. For both G4 and G5 we also know the kind of fault and this now reduces to a divide by 3 and conquer.
  7. For G6, we can make use of the reference ball and find out the faulty one in just one more weighings.

Hence, the culling of the faulty ball from a group of 13 balls may be done in all cases, with just three weighings!

As a side note, if we had a reference ball to start with, we cud've started off with 9 balls in one group and kept out 3 balls for second weighing. That means, we can actually cull out a faulty ball from a group of size 14, if provided with a reference ball.

Let me generalize this procedure before closing down. Lets say we have a group (3N - 1) / 2 balls among which one is faulty:
  1. 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.
  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).
  3. 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.
So, in all cases, we wud take a maximum of N weighings. Note that the original question is only a special case of this general solution, for N = 3!


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

  1. All days from 2000 oct 7th to dec 31st (completed age = 2)
  2. All days from 1978 jan 1 to october 6th (completed age = 25)
  3. All days from 1982 oct 7th to dec 31st (completed age = 20)
So, a day like oct 6th is uncertain for the mathematician. The only day when the mathematician could have some clarity of date is jan 1st. For example, if the day was 2003, jan 1st, the possible solutions comes down to

  1. 2000 jan 2nd to dec 31st
  2. 1978 jan 1st
  3. 1982 jan 2nd to dec 31st
Note that the mathematician can be sure of the date atleast in one case (the 2nd one here). And the other two cases will not work in the scope of this problem (since the date of birth is always different from current date). So our objective is to find out years were we have two possibilities similar to case 2 and no possibilities similar to case 1 & 3

Keeping this in mind we will attend to solve this problem.

[there is no cases like case 2 for 21st century and since the question is when DID this happen, we can safely ignore 21st century. And 18th century is also ruled out since the first commerical train service started only in 1854 !!!]

We'll get a couple of equations:

x - 1000 * y1000 - 100 * y100 - 10 * y10 - y1 = y1000 + y100 + y10 + y1 => (I)
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

  1. for even x < 1922, there is no integer solution for eq (V)
  2. for even x > 1916 there is no integer solution for eq (VI)
  3. for 1916 < even x < 1922, eq (III) and eq (IV) has solutions
So the only possible values of 'x' satisfying these conditions is x = 1918 or 1920. And since 1918 Jan 1st is a tuesday thats the only day when this incidence could have happened. This will mean that the guys were born on 1904 Jan 1st and 1895 Jan 1st.

Other possible solutions in 19th and 18th century could have been 1817, 1819, 1716, 1718, but they are all before the first commercial train service.


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:

  • 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
Thus S = 17,29,41 or 53.

Note when A makes his statement, B knows that S belongs to the 11-element list above. (The reduction to 4 elements used all three statements, while B, as of now, knows only the first statement.)

53 = 47 + 6 = 37 + 16

47*6 has two feasible factorisations with odd sum - (47,6) and (94,3), but the latter sum is insecure.

Thus, given S = 53, A can not distinguish between (47,6) and (37,16), since B can find the numbers given either product.

41 = 37 + 4 = 25 + 16

25*16 has two feasible factorisations with odd sum - (25,16) and (5,80) but only the former is secure.

Thus A can not distinguish between (37,4) and (38,3).

29 = 13 + 16 = 25 + 4

25*4 has two feasible factorisations with odd sum - (25,4) and (5,20) but the latter sum is insecure.

Thus A can not distinguish between (13,16) and (25,4).

  • 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
Observe that, given S = 17, B can find out the numbers only if the product is 13 * 4 = 52. In all other cases, the products have more than one feasible factorisation with secure sum. Thus A can also find out X and Y, given S = 17.

Hence, S=17, P=52, and {X,Y} = {4,13}
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.



© 2018 Sandeep Unnimadhavan