Bharat Rakshak

Thanks, yes I was sloppy . (1,1,2) is ok.
The recursive relationship you gave above, for even n seems to be okay but, I believe, not for odd n.
(Try n=7 to see what I mean)

If one gets on the right track, answer is quite simple...

Key is: Given n weights, the answer is same, irrespective of the individual value of each of those n weights .. (as long as they are of the form 2^n)

(For example, if you are given three weights.. the answer for the number of ways remains the same if the weights were (1,2,4) or (1,4,32), or (2,8,16)..(A moments thought will make this obvious)

Rest is simple, if F(n-1) is the number of ways for (n-1) weights, the last weight to be placed (n possibilities - it can have any of the n values ) can go on either side, except when it the heaviest weight, (In that case it can go only on one side)... so there are (2n-1) ways.
So F(n) = (2n-1)* F(n-1)
= (2n-1)*(2n-3)*F(n-2)
= (2n-1)*(2n-3)*(2n-5)..... 5*3*F(1) ....(and we know that F(1)=1)
which gives F(n) = (2n-1)!!
(The values go as 1, 3, 3*5=15, 75, ....)
(2n-1)!! = 1*3*5*....(2n-1)

Very elegant. While I had considered that each weight can be placed in either side except when it is the heaviest so far, I did not relate the 2*n -1 part to it - stupid me was trying to work the chances of the heaviest being picked at a given point . Sense and Simplicity.

You are correct. I was sloppy. (I still do not understand the "fairly distributed" argument completely, but that (the result) happens to be correct)
****
The problem may seem artificial but this (similar problems/ techniques to solve) has many applications in physics.

For example, if one has K Rs-1 note, and L Rs-2 note (K is greater than or equal to L)
The the probability that it will be "ok" is just (K-L+1)/(K+1) (Simple result but not so easy to prove ).

Don't answer if you have heard it before. Don't google if you have not .

There is a duck in the center of a circular lake and a hungry fox on the periphery. The duck is a strange one, it can fly only when it reaches the ground i.e. when it is in the water, it can only swim and cannot fly. The fox is also a strange one, it is afraid of water and will not enter it. Assuming that both the duck and the fox are smart enough to know the perfect strategies for themselves, how much faster should the fox be (able to run) than the duck (can swim) to prevent it from flying to safety?

Amber G,

Bringing up some really old posts that I am going through. Kindly bear with me.

(7+5 sqrt(2))^2 = 49 + 50 + 70 sqrt(2) = 99 + 70 sqrt(2)
(7+5 sqrt(2))^4 = (99 + 70 sqrt(2))^2 = 9801 + 9800 + 6930 sqrt(2)
and so on..
I dont see the sqrt(2) part going away, no matter what the exponent. Hence how can the first 100 digits after the decimal point be 0?

^^^
Saar ji, you can see the solution here on this page:
http://forums.bharat-rakshak.com/viewtopic.php?f=2&t=4201&start=360
Of course, I cheated a little and banged out some python code . AmberG and Aditya posted more analytical solutions.

ArmenT ji from LPUA,

If you are referring to what I said, kindly elaborate in terms that would make sense to this dumb mujahid brought up on madrassa maths only.

Edited later ...

To elaborate what I am asking for, given that sqrt(2) is an irrational number and given that it can be demonstrated that (7 + 5 sqrt(2))^100 decomposes to the form x + y sqrt(2) where x and y are both naturals, how does finding
((300C1 * 2^0) + (300C3 * 2^1) + (300C5 * 2^2) + (300C7 + 2^3) + ....(300C299 * 2^149) or anything else make a difference?

ArmenT ji from LPUA,

Let me deconstruct your original argument -

<quote>
I'm going to say 0.
Reason:
1. Forget all the integral numbers into the expression above because they don't play any part in the digits after the decimal point in the first place. but they do, a moments thought will make this clear e.g. using python, (7 + 5 sqrt(2))^2 = pow(7 + 5*pow(5,.5), 2) = 330.5247584249853.. but (1 + 5 sqrt(2))^2 = pow(1 + 5*pow(5,.5), 2) = 148.36067977499792...reasonable to assume that in this particular case, what is true for exp 2 will be true for exp 100 also? using exp 2 only to ensure that precision does not come into the picture The digits after the decimal point are really influenced by (sqrt(n))^X
2. If n is an integer and if X is even in step 1, then (sqrt(n))^X is an integer as well, since (sqrt(n))^X is the same as n^(X/2). Since X is even, X/2 is an integer. Since n is an integer, therefore it follows n^(X/2) is integer as well nothing wrong here
3. Therefore first hundred digits after decimal point are 0. derived from the same flawed argument in 1
<unquote>

First the digits (first 100 digits after decimal) are NOT all 0's they are all nine(s)...
Key is to see that if (7+5 sqrt(2))^2 = 99 + 70 sqrt(2)
then (7-5 sqrt(2))^2 = 99 - 70 sqrt(2)

If you add them then the result is an integer..
.
Similarly (7+5sqrt(2))^100 + (7-5sqrt(2))^100 is an INTEGER!
But |(7-5sqrt(2))| = (1/(7+5sqrt(2)) < (1/10) (Actually about 1/14)
so (7-sqrt(2))^100 < (1/10)^100 = + 0.00000000.... (more than 100 zeros before something)
So (7+sqrt(2))^100 = Integer - 0.000000000.......{something}
= (something).9999999999 (at least 100 9's) {something}

(Similarly if the power was odd (eg (7+5sqrt(2))^99).. then it will have bunch of zeros after the decimal - this is because (7-5sqrt(2)) is negative, so its odd power is negative and even power is positive)

P.S ...(7+5sqrt(2))^100 will have .9999 (114 times and then) 85300...after the decimal point ...

Added later: This was discussed here before:
Previous Hint

Added still later, BTW my previous quote ("How that argument stands out for a smaller even integer, say x=2, or 4?") in your post above, was there precisely for the same point as skumar was driving..(that you do not always get "zeros").. The reason you get the value pretty close to an integer is that (a- b*sqrt(2)) happens to be pretty close to zero - IOW a/b happens to be a good expression of sqrt(2)).. The genius of people like Brhamgupta was that he found a simple way to calculate a and b (Essentially same as Skumar's way of getting 99 and 70 from 7 and 5 - BTW 99/70 is VERY good approx (best with 2 digit numbers) for sqrt(2))..

Of course this is also very much related (almost exactly) to seemingly unrelated discussion (around 12 June 2011) with respect for finding sigma(n) which are perfect squares...

Nice problem, I heard that when I was quite young (about 12) and liked it then too. My brother asked me (slightly changed .. with swimming chor and sipai who can not swim) and was quite proud of me because I got it right. .. Not too long ago, IIRC it was a problem in a MIT puzzle tournament.

(Also, had been asked by Microsoft in their placement interviews )

AmberG,

Thanks for elaborating the solution patiently again to this dumb (and now I suspect blind) mujahid brought up on madrassa maths (see, we were never taught this or I was out grazing)

^^^ In my opinion, your points were very sensible, the answer ((2n-1)!!) was correct, just as the answer to the movie ticket problem...

I still can't figure out how to explain that (n/(n+1)) factor by elementary logic (though the factor is correct, and I can show that by somewhat complicated math). (IOW the fact that exactly (1/(n+1)) will be of the type where #Rs1=#Rs2). (The final answer reduces to a fairly well known formula ... actually not much different from that ((2n-1)!!) type result of the other problem) )

I hope it is okay to put , perhaps a little easier, version of your duck/fox problem.
(Same as above +) Given that fox can run 4 times as fast as duck can swim. Can the duck escape? (The MS Placement question had this too "assuming that both fox and duck are intelligent ... actually they are not but we hope that interviewee is intelligent enough to assume that ..and not give a silly answer" )

Looking back, there was this question, which did not seem to get answered ...
(There was some discussion here but, from what I see, there is no solution...) Let me quote the question for convenience.


The answer to first part, is o fcouse, correct.
For the second part: the choice is yours, if you like to go for the second throw or not....

Obviously if the roll is 4(or more) you skip the second roll, If you get 3 (or less) you take chances and go for the second roll to see if you can do better...
In the first case (probability is 1/2 that your first roll was 4 or more) you on average make 5, on the second case (probability 1/2 also) (when you roll again and may be worse off than before .. but still on average ..) you make 3.5 (see the answer to the first part) ... so average (or expected cost) is (5+3.5)/2 or 4.25 .

(If you are always allowed to throw the second time, and keep the higher number , then expected return will be about about 4.47..)

Bringing up dead posts again .

At the end of n years ignoring starting salary, the sum of all incremental salaries will be -
1. You get an annual raise of Rs. x
n*(n-1)/2*x*12=n*(n-1)*x*6

2. You get a raise of Rs. y every 6 months.
2n*(2n-1)/2*y*6=n*(2n-1)*y*6

So would the tipping point not be roughly (n-1)/(2n-1)?

e.g. if you are considering 1000 in first case, the (minimum higher integral) equivalent for second case for say 5 years would be 4/9*1000 = ~ 445, for 2 years it would be 1/3*1000 ~ 334.

300 every 6 months would be better than 1000 every year only if you are planning to work for less than 17 months!

Unless I am missing something obvious

ArmenT, correct me if I am wrong, but I think what was meant was, the raise is *not* given as a lump sum at the end of the period, but rather as salary increase distributed over the next period.

(And again for clarity sake, we are assuming that option 2 - means raise of 50/month (compared to 6 month old check) in monthly pay-check..while raise of "1000/yr" means each month's pay check is about $83.33 more than last year's ) (Month's pay check means add both the checks given on First and 15th of the month)

That case 300/6months always is *much* better.. for example, extra income after the end of of 6 months period would be:

End of 6 months: 0 vs 0
End of 12 months: 300 vs 0
End of 18 months: 900 vs 500
End of 2 year: 1800 vs 1000 ((300+600+900) vs 1000)
End of 3 years: 4500 vs 3000 ((300+600+900+1200+1500) vs (1000+2000)

End of n years we have n(2n-1)*300 vs n(n-1)*500
Difference (=100n(n+2)), as mentioned in the previous post - is always non negative - and grows a little faster than n^2!)

(Intuitively .. 300/6months is equivalent to 1200/yr as 2^2 = 4)

(Another intuitive way is in one case you make only (1000/12= $83.33/month more than what you made last year, while in the second case you make $100/month more than what you made last year - as you have gotten 2 raises of (300/6= $50)

Thanks, Amber G. I guess you could look at it both ways.

Since I was looking at the Rs part and ignored the initial low Rs 10000 per annum, I was looking at it as a Rs 300 increment every six months or Rs 1000 every year. The Rs 50 increment every month looked intuitively low to me and hence probably subconsciously filtered out .

End of 12 months: 1800 vs 0
End of 18 months: 5400 vs 6000
End of 24 months: 10800 vs 12000
End of 36 months: 27000 vs 36000
and so on

So it brings us to what you mention often - unambiguous wording of a problem .

Today, The third anual Math Prize for Girls contest is being held at MIT (near Boston, USA). The contest is invitation only but was open to all US (or Canadian, or any resident living here) girls who are in 11th grade (or lower) and did well in AMC/AIME/USAMO... (Top 200-300 girls nation wide). About $50,000 in prize money.

Those who are interested ( parents of young kids) can work for next year.. (AMC 10-12, open to all US high school/ intermediate school takes place around Feb 2012, good marks there can earn a spot for next year)

Here is the site: Tell it to your friends etc..
http://mathprize.atfoundation.org/index
And check out the PBS video.

Here is a sample of the question from last year:


You can find the questions (and answers ) of last year here

AmberG, I recently came to know about the program Maple for mathematics modeling. What a treat to visualize the higher order functions etc.Would have made a world of difference while going in college!

^^^ Maple (and Mathematica ) is quite nice. BTW, for those who do no have connection to a university or corporation, or find it too expensive for occasional use, internet version Wolfram (http://www.wolframalpha.com/)is quite good. (Not only for physics, math, but also for health sciences, electronics, music and what have you...)

For those who are not familiar, try out (Just few random examples)
say [url=http://www.wolframalpha.com/input/?i=int+e^%28-t^2%29+dt]Integral and graph of gaussian[/url]

or Wind speed of a Hurricane

or Growth Chart

Not only that, You can design your own nukes as in:
http://www.wolframalpha.com/input/?i=uranium+235

BTW: Any replies/comments wrt duck/wolf problem ?

Pi.

^^^Hello Angre. Welcome ! (Assuming this is the answer to duck/wolf problem) .. What if wolf moves 4 (> pi) times as fast as the duck? Can the duck escape? (Hint: Answer is yes)

As said before, an easier version.


One similar, but different, (may be a little harder) problem was considered for Math Olympiad (Submitted by Yugoslavia but not chosen). It was a rabbit/fox problem where rabbit can only travel on the perimeter of an equilateral triangle and fox can take short cuts (and can run anywhere), and the aim was for the fox to catch the rabbit. Starting point - fox at the center and rabbit is at one vertex of the equilateral triangle.

X-posting from Nukkad thread, at the suggestion of a poster there. This is a question I had. I also had two other questions, which are not relevant for this Math's corner - those questions are still in the Nukkad thread. I'd appreciate responses to those Q's too (over there, of course ).

(1) Is there a word in Sanskrit for "Differential Equation?" Bhaskara II and Manjula/Munjala (among others) developed differential calculus to a good extent (long before Newton's time, I might add), so there should be some related terms. If there's no Sanskrit term, is there a modern-day Hindi term (adapted from some Western language)?

Dileep suggested the term "kalanam" for differentiation. Is there also a term for "Differential Equation?" How about ODE vs. PDE, or wasn't the mathematics of Bhaskara's time advanced enough for that?

Thanks,
Sudarshan

The duck / fox problem is interesting... But a bit clichéd ... Asked too often...

But the triangle modification from yugoslavia would have been hell a lot tougher...


Here is a partial solution to the circular version...

the obvious strategy for the duck would be to swim at diametrically opposite end of the pond...

but since pi(r) < 4(r) and the foxy is 4 times faster than daffy .. the duck would meet its 72...

but the duck went to MIT so there is an alternate plan...

the key strategy here is to keep increasing the distance ducky and fox

So let the duck swim in concentric circle of radius = r' ..r'< r/4...that is the onlee possibility by which duck will have greater angular velocity that the fox...when it is diametrically opposite of the fox r-r' will be the linear distance that duck will need to travel ...

So that way it ll gain distance over the fox .... the rest of the solution is easily intuitive...

mathematica can be easily downloaded via torrents.. even though I like stephen wolfram ,I don't mind robbing him of his IPR.. I have been using pirate versions since I was a kid... version 3 used to be used in those days ... now I have version 7..though these days its of little use to me .. I like to play with it... I used it for doing statistical work for my research papers... but then I found ..medistats and SPSS for that job.. these softwares are designed for medical statistics ... spss received federal funding so I guess it needed no funds from me... I took the liberty of getting the dvd from the webmaster,, I use the univ version in my laptops...

The standard term used (in text books etc) for calculus is "kalan" (कलन ) (Some times, additional words (Rashi-kalan or chal rashi karan - राशी कलन, or चल राशी कलन ) are added.

Obviously अवकल (for differential) and अनुकल (for integral) are additionally added when needed.

Another word used in Sanskrit for calculus of finite differences (where some of Kerala mathematicians were really good at) was something like
(परिमित अंतर कलन - almost same thing literally)

For more see any standard source ( Nagripracharani''s Hindi Visvakosh is quite good)

You can also check out, wiki or other internet sources. (Believe some of IIT's and other institutes have quite a good collection of old books in digital forms).

Wiki has an entree:
कलन

Added later: For (partial) diff. equations etc..people have used terms (आंशिक) अंतर समीकरण, (sometimes विभेदक समीकरण ) .

(There are some earlier posts here which have references to where you can see some math books on line: eg here:
ब्रह्मस्फुटसिद्धान्त

Angre, SriKumar, Gakakkad et al..

Yes it has been asked quite often (with fox running 4 times as fast as the duck.

Solution given above by gakakkad is nice. Duck will escape even if fox can run 4 times faster.

Now what if the speed of fox is 4.5 times that of the duck? Can duck still escape?

AmberG, all those solutions assume "dumb" or "relatively dumb" ducks an foxes. The optimal solution for the "smart" duck (and the fox) is to maintain a heading which is 180 deg AWAY from the fox at all times (trying to maximize separation at every instant). I tried solving this scenario when you posted earlier, but it became very complex soon and that the data given in the problem as stated is not sufficient and you will need to know the speed of the fox/duck and not sure if I remember correctly, the radius of the circle to get the answer. This is sort of like the missile track / wolf chasing a hare kind of curve kind of problem I think, if you don't simplify the problem too much.

Now since you posed this again, i googled pursuit curve and the answer to you problem is the inverse of the last circle chase problem with the quarry starting in the middle and moving outward and the hunter in the circumference. Pursuit Curve

AmberG,

gakkakad has answered the problem conceptually without revealing the (trivial) math around it.

Would the same concept apply to the Yugoslav problem i.e. the ratio of the perimeter of the triangle to the circumference of the inscribed circle?

Vinaji: Nice pointer towards pursuit curves.


While, for fox, I can understand the optimal solution is to minimize angular separation, BUT for duck to maintain a heading 180 deg away (for all times) may not be optimal. A seconds thought will show you why. (Suppose the duck is pretty close to the shore, and can make a break for it even though fox is close (but not too close) and only a few degrees away. In this case, duck should not head for the "other" direction. --- I am trying to be brief but I hope my point is clear..)

..
Yes, this can get relatively complex and calculus is almost always needed. If it helps, just assume duck speed is 1m/s, etc..The answer depends only on relative speed of duck and fox (and shape but not the size of the lake) . (One way is to think, take a movie of the chase, the answer does not change if you watch it on an small i-phone or large screen (absolute size of lake) or speed the movie up or slow it down

Curious, after all the math, what answer did you get? (for limiting value of duck/fox speed ratio)

For the Yugoslav problem, the answer is 2, (That is rabbit escapes if it can run 2x (or more) times faster). As gakkakad mentioned, the answer is by no means trivial.


So what do you (or other people here) think, will the duck still escape, if the ratio of speeds is 4.5 ?

Duck fox problem answer in the form of a puzzle -
Assuming no fish in the pond, either both die of
hunger or both die of Fatigue

Actually the fox will need to run @ a speed of 4.6 times that of the duck ...

Sorry for hand written solution..was a bit lenthy..don't have time to type ...and the typically bad hand writing of a doctor...





Further I explained conceptually b4 that duck will need to a concentric circle of radius r/x where x is the speed of fox..

some more steps and we get

pi+ COS^-1 (1/x) = √(x^2 – 1)

solving we get x = ~ 4.6

^^^Can you expand on that? One can safely assume that by "escape" here, one means: the duck in a finite time escapes by flying away. (one can even put reasonable upper limit for the time without changing the problem)..To calculate most 'optimal' path may not be trivial but the time required (distance traveled) is quite finite.
(If duck remains inside lake 'till some one dies of hunger etc ===> this will produce the answer ===> duck does not escape)
Added later: (Did not see the above post, it gives further info on what I was saying)

Nice!!
Actually this (and problems like this) is what got me hooked on math and calculus..
(And that is what got my kids interested in Math)
And the problem is beautiful in layers...

- First intuitive answer is Pi ... as duck can simply swim to the opposite shore.

- Most people (where problem is given with speed ratio of 4) get to the next level of pi+1 (about 4.14). In fact most people (even the riddle providers) assume that that answer is correct and people stay at that. In fact many items in google search (and some other math problem databases) stops at that. (They also do not mention the most optimal way to reach the inner circle)

(Google search gives one reference here: My tech interview)

- Some (with calculus) solve it as straight forward "pursuit curves" or integrating the length of a spiral .... where answer sometimes come as little bit better than (pi+1)

The answer 4.6 given above is seldom mentioned. Interesting part here is that total distance covered by duck is still quite reasonable (less than diameter).


And one solution here: http://www.mathrec.org/old/2003jul/solutions.html

Let me think about it.

Edited Later: Went through gakkad ji's solution. That is nice (continuity assumption across the land water boundary is required, I think). My answer was because I assumed open sets.Then duck can come as close as possible to shore without really stepping on to land and the fox can come as close to the water as possible without stepping in to the water.

to be honest I had solved this several years ago in my school days.. This was in the question set of IIT coaching insti's during those days..miraculously i still remember it... the beauty of calculus is that if properly taught , it gets stuck in your head...though eventually i selected medicine but i still miss physics/maths...like to stay in touch whenever possible..

Thanks, Amber, much appreciate the detailed response.

Regards,
Sudarshan