Bharat Rakshak Forum Announcement

Hello Everyone,

A warm welcome back to the Bharat Rakshak Forum.

Important Notice: Due to a corruption in the BR forum database we regret to announce that data records relating to some of our registered users have been lost. We estimate approx. 500 user details are deleted.

To ease the process of recreating the user IDs we request members that have previously posted on the BR forums to recognise and identify their posts, once the posts are identified please contact the BRF moderator team by emailing BRF Mod Team with your post details.

The mod team will be able to update your username, email etc. so that the user history can be maintained.

Unfortunately for members that have never posted or have had all their posts deleted i.e. users that have 0 posts, we will be unable to recreate your account hence we request that you re-register again.

We apologise for any inconvenience caused and thank you for your understanding.

Regards,
Seetal

BR Maths Corner-1

The Technology & Economic Forum is a venue to discuss issues pertaining to Technological and Economic developments in India. We request members to kindly stay within the mandate of this forum and keep their exchanges of views, on a civilised level, however vehemently any disagreement may be felt. All feedback regarding forum usage may be sent to the moderators using the Feedback Form or by clicking the Report Post Icon in any objectionable post for proper action. Please note that the views expressed by the Members and Moderators on these discussion boards are that of the individuals only and do not reflect the official policy or view of the Bharat-Rakshak.com Website. Copyright Violation is strictly prohibited and may result in revocation of your posting rights - please read the FAQ for full details. Users must also abide by the Forum Guidelines at all times.
Tuvaluan
BRFite
Posts: 1816
Joined: 11 Aug 2016 06:14

Re: BR Maths Corner-1

Postby Tuvaluan » 23 Jan 2015 09:22

There are 100 seats assigned to 100 passengers, but each person randomly sits on any empty seat he/she chooses.

What is the probability that at least one person is now sitting in his/her assigned seat.

(Instead of 100, one can choose a smaller number, say 3 or 4 to see if there is any pattern)


If we define Q(n) as probability of no one getting their allotted seat, then the required probability is
[1 - Q(n)]
Q(1) = 0
Q(2) = 1/2
Q(n) = ((n-1)*(n-3)*(n-5)..*1)/n!
which can be expressed recursively as Q(n) = [Q(n-2)*(n-1)]/[n*(n-1)] = Q(n-2)/n

Q(n)'s numerator is the number of ways you can arrange people on seats so that everyone gets the wrong seat. every time some one picks a wrong seat, another person is going to be sitting on a wrong seat no matter what, so you can keep that guy aside, and do this problem again for the remaining n-2 people and the n-2 seats alloted to those people. This is not really a proof of correctness, just handwaving. And the probability that at least one person gets allotted seat seems rather high, which is not intuitive, which could mean the solution is wrong, of course.

ArmenT
BR Mainsite Crew
Posts: 4239
Joined: 10 Sep 2007 05:57
Location: Loud, Proud, Ugly American

Re: BR Maths Corner-1

Postby ArmenT » 23 Jan 2015 12:47

Tuvaluan wrote:Did not say ArmenT was wrong. All I said was that I do not see how that the lack of mention of the two names Mr.CM and Mr.S means that they map to their corresponding trades -- I can see he intuitively figured out that was correct.

As an aside, it is painful to see solutions for problems in math and science texts that hide important detail under "clearly" and "obviously" while failing to state why. Many times it can just be intuition like ArmenT's initial leap of logic, but then intuition does not always work right.

Actually, this particular answer was pure logic, no intuition onlee :). However, I could have done a better job of explaining how I figured it out -- I pretty much used exactly what AmberG explained above, but she did a far better job than me of laying out the details. Mea culpa :oops:

// (for the record, I've never studied group theory. Sounds interesting though)

Amber G.
BRF Oldie
Posts: 5829
Joined: 17 Dec 2002 12:31
Location: Ohio, USA

Re: BR Maths Corner-1

Postby Amber G. » 23 Jan 2015 20:41

Tuvaluan wrote:
There are 100 seats assigned to 100 passengers, but each person randomly sits on any empty seat he/she chooses.

What is the probability that at least one person is now sitting in his/her assigned seat.

(Instead of 100, one can choose a smaller number, say 3 or 4 to see if there is any pattern)


If we define Q(n) as probability of no one getting their allotted seat, then the required probability is
[1 - Q(n)]
Q(1) = 0
Q(2) = 1/2
Q(n) = ((n-1)*(n-3)*(n-5)..*1)/n!
which can be expressed recursively as Q(n) = [Q(n-2)*(n-1)]/[n*(n-1)] = Q(n-2)/n
<snip>


(First let me assume that in your formula one "stops" before one reaches to zero (that is Q(3) = 2/3! and not 0 (= (3-1)(3-3) ..=0 ) :) )

Then: though values of Q(1) and Q(2) are correct ..and Q(n) comes out correct for n=3
(That is Q(3) is indeed 2/6 = 1/3)
but Q(4) is 9/24... (One can count all the cases)

(Hint: What makes this problem beautiful is that the answer for all practical purposes.. depends very little on "n".. so Q(n) is about 0.37 whether n=4 or n=100)

Amber G.
BRF Oldie
Posts: 5829
Joined: 17 Dec 2002 12:31
Location: Ohio, USA

Re: BR Maths Corner-1

Postby Amber G. » 23 Jan 2015 21:10

...As an aside, it is painful to see solutions for problems in math and science texts that hide important detail under "clearly" and "obviously" while failing to state why.


Let me share an anecdote involving the famous John von Neumann. In MIT he was notorious for omitting many steps on the blackboard leaving his students bewildered. He had the habit of simply writing answers to homework assignments on the board (the method of solution being, of course, "obvious").

(There are many stories about him but let me share a famous story (sorry if you have heard it before) which I am told actually happened in essentially the same way as it is described)

An MIT student cornered the famous professor in a hallway, and asked:

"Excuse me, Professor, could you please help me with a calculus problem?"
JvN: "Okay, sonny, if it's real quick -- I'm a sort of busy right now"
S: "I'm having trouble with this integral."
JvN: "Let's have a look." (a brief pause) "Alright, sonny, the answer's two-pi over 5."
S: "I know that, sir, the answer's in the back - I'm having trouble deriving it, though."
JvN: "Okay, let me see it again." (another pause) "Yep, the answer's two-pi over 5."
S (frustrated): "Uh, sir, I know the answer, I just don't see how to derive it."
JvN: "Whaddya want, sonny, I worked it out in two different ways!"
:)

Tuvaluan
BRFite
Posts: 1816
Joined: 11 Aug 2016 06:14

Re: BR Maths Corner-1

Postby Tuvaluan » 23 Jan 2015 22:59

Nice one, AmberG. VN was one of a kind, but they tend to do the "obvious" thingy more than others. :)

BTW, I think I messed up my counting in the previous solution (counting is hard..had to take my socks off)

The basis conditions are
Q[2] = 1/2
Q[3] = 1/3
so we stop evaluating the recursive function at 3 or 2 depending on whether n is even or odd, for n > 3.

Q(n) = [(n-1)(n-3)...*1)]^2/n!

Q(n) = (n-1)/n * Q(n-2) (The first guy picks a wrong seat from n-1 choices as does the second guy, which makes it (n-1)*(n-1) for the two out of a total of n!

Q(4) = 3/4*1/2 = 3/8 (9/24)

the asymptotic value of Q(n) is around 0.13 (or 0.87 for the probabily of at least one seat)

Amber G.
BRF Oldie
Posts: 5829
Joined: 17 Dec 2002 12:31
Location: Ohio, USA

Re: BR Maths Corner-1

Postby Amber G. » 24 Jan 2015 02:10

I am simply commenting on Tuvaluan's post, so if you like to ignore this, you can safely ignore...for context, if interested, look at Q(n)'s definition in his earlier posts...

Tuvaluan, If you like to check/verify the values..
Q(1)=0, Q(2)=1/2, Q(3)=1/3,Q(4)=3/8,Q(5)=11/30 (note 1),Q(6)=53/144 etc.. asymptotic value is about 0.368 (and it reaches the accuracy fairly quickly, as you can see)

(Note 1 - As an aside for Butcher/Sailor/CM..etc.. problem, the probability that no name will match their profession (for random 5 people) is 11/30)

Dan Mazer
BRFite -Trainee
Posts: 54
Joined: 03 Sep 2009 02:17

Re: BR Maths Corner-1

Postby Dan Mazer » 25 Jan 2015 10:46

Amber G. wrote:So, for convenience I am reproducing the problem I asked above. It is a classic problem and one of my favorite fun problem which teaches some basic idea. (If you have not heard it before, the answer may surprise you)

Problem:

There are 100 seats assigned to 100 passengers, but each person randomly sits on any empty seat he/she chooses.

What is the probability that at least one person is now sitting in his/her assigned seat.

(Instead of 100, one can choose a smaller number, say 3 or 4 to see if there is any pattern)


The number of seating arrangements for n seats

S_n = n S_(n-1) + (-1)^n .......(1)

n S_(n-1) = n(n-1) S_(n-2) + (-1)^(n-1) * n

n(n-1) S_(n-2) = n(n-1)(n-2) S_(n-3) + (-1)^(n-2) * n(n-1)

....

n(n-1).....4 S_3 = n(n-1)....3 S_2 + (-1)^3 * n(n-1)....4 (S_2 = 1)

Adding the equations
__________________________________________________

S_n = n!/2 + n! [(-1)^n/n! + (-1)^(n-1)/(n-1)! + (-1)^(n-2)/(n-2)! ...... + (-1)^3/3!]

= n! * Sum[(-1)^k/k!] for k = 0 to n

So the probability for n seats is Sum[(-1)^k /k!] for k->0 to n. Googled and found that this sum is a beautiful 1/e = 0.3678...... for n->inf

My derivation for equation (1) above is a little tortured though :P I'll try to arrive at it in a simpler manner before posting it.

Amber G.
BRF Oldie
Posts: 5829
Joined: 17 Dec 2002 12:31
Location: Ohio, USA

Re: BR Maths Corner-1

Postby Amber G. » 25 Jan 2015 22:40

^^^Nice. Yes, the answer for Q(n) (=1-P(n)) is about 1/e.

This is why this is very beautiful result...

Precise result is

Q(n) = 1-1/1!+ 1/2!-1/3!+1/4! - .... (+ or - ..whether n is even or odd) 1/n!

Since the series converges very fast, in practice the answer is pretty close to 1/e. (more than 10 significant figure for n>10, 4-5 significant as long as n is about 5 or more) etc,,

Since it is VERY well known problem, one can find the answer/method with little googling or (looking at any famous problem solving book)

Here are two easy methods..
Calculate P(n) ...(At least one person sitting in correct seat)



Remember using standard statistical theorem to avoid over counting....
P(A|B) = P(A)+P(B)-P(AB)
and P(A|B|C) = P(A)+P(B)+P(C) - P(AB) - P(BC) - P(CA) + P(ABC) etc...

Probability that one person say A gets his own seat = 1/n
and of course A could be any one of the n person.

Probability that A&B gets in their own seat (after A) = (1/n)(1/(n-1))

Probability that A&B&C gets in their own seat (1/(n)(n-1)(n-2)) etc...

Now since there are n ways to choose 1 person, nC2 ways to choose 2 people etc... we get

P(n) = n (1/n) - (nC2)(1/(n(n-1)) + nC3 (1/n(n-1)(n-2)) ...
which will turn out to be 1-1/2!+1/3!-1/4! ...


Calculate Q(n) ...(Ending what Tuvaluan's started ...)

For simplicity, let q(n) be number of ways one can seat n passengers where no one is sitting in the correct seat. (Q(n) = q(n)/n!)

So first person is not seating in her seat, let us assume she is sitting in kth persons seat..
(there are n-1 choices here for kth person)

Two cases -
Case 1) kth person is sitting is First person seat.
Case 2 kth person is NOT sitting in first person's seat..

In case 1 - it reduces to (n-2) case. (# of ways for the rest is q(n-2))
In case 2 - Think for a moment - It is nothing but (n-1) people case ...
so q(n) = (n-1)(q(n-2)+q(n-1))

Very nice formula... (one can check, q(1)=0, q(2)=1, q(3) = 2(1+0)=2, q(4)=3(2+1)=9, q(5)=4(9+2) etc...

A little math ( using Q(n)=q(n)/n!) will convert the above formula to the required one)


Vayutuvan
BRF Oldie
Posts: 9818
Joined: 20 Jun 2011 04:36

Re: BR Maths Corner-1

Postby Vayutuvan » 26 Jan 2015 02:24

AmberG, SaiK, and others:

A couple of days back I looked up the solution in one of the books I have on my book shelf (I cheated as I had some other things to do but could not sleep since I was curious about the solution to AmberG's problem). It is a worked out example in

Elements of Discrete Mathematics, C. L . Liu, McGraw-Hill International, 1986

As an aside, C.L. (Chung Laung) Liu is popularly known to his students and grand students as Dave Liu or simply Dave who is an excellent teacher of all things CS. One of his students, Andrew Yao, is a Turing Award winner.

The example is in section 3.6 Discrete Probability example number 3.26. Also the "Inclusion Exclusion Principle" for set cardinality is derived for general case using - what else - induction in the first chapter after example 1.13.

If people are looking for challenging discrete math problems which explain the general principles through very simply stated problems, and nothing beyond arithmetic, a little bit of logic, and some mathematical maturity this book is for you.

For example, Chapter 3 Permutations, Combinations, and Discrete Probability has 66 chapter end problems in addition to 34 worked out examples.

I highly recommend it though I am not sure whether the book is still in print.

AmberG: By the way the 6x6 defective board problem is a chapter end problem in Chapter 5 Graphs and Planar Graphs Problem 5.42. This chapter has about 47 problems and a few worked out examples. The original problem of tilings of a defective board is a worked out example. There are also other excellent tiling problems and some discussion regarding a game called "Instant Insanity" from Euler's theorem.

ArmenT: This same book has a gentle introduction to Group Theory as well.

His older book Introduction To Combinatorial Mathematics, McGraw-Hill, 1968, is also a classic. It covers many topics at an introductory level and would be quite useful for beginning CS students and as a reference for working Computer Scientists.. In first chapter itself, Stirling's formula - an approximation to factorials - is derived. Second chapter has a short discussion of Ferrer Graphs and a result Integer Partitions is derived. Just jog the memory of the gentle readers, Integer Partitions are one of the main areas in which Srinivasa Ramanujan had a great number of results (along with Rogers). This also forms a large part of Bruce Berendt's first volume of the three volume book called Lost Notebooks of Ramanujan.

Amber G.
BRF Oldie
Posts: 5829
Joined: 17 Dec 2002 12:31
Location: Ohio, USA

Re: BR Maths Corner-1

Postby Amber G. » 26 Jan 2015 03:55

Manjul Bhargava (Fields Medal winner - mentioned many times in brf dhaga) is getting Padma Bhushan on this Republic Day. Congrats.

Amber G.
BRF Oldie
Posts: 5829
Joined: 17 Dec 2002 12:31
Location: Ohio, USA

Re: BR Maths Corner-1

Postby Amber G. » 26 Jan 2015 22:55

Matrimc,
Thanks for post and reference for Liu's book.

Yes, as I said the problem is one of those which teaches something fundamental and you will find that example in virtually any good book which deals with such subjects. It illustrates "Inclusion Exclusion Principle" extremely well ..and how to "count". Also it is beautiful to see "e" coming in.

Let me add two good books in my recommendation ...

1 - Geometry and imagination - By Hilbert and Cohn-Vossen
2 - Challenging Mathematical Problems with Elementary solutions (Two volumes) by Yaglom & Yaglom

(Both are fun to read -- I have seen some very elegant solutions in these books. Yaglom's book, of course has the problem and an elegant solution for the problem I asked)

SaiK
BRF Oldie
Posts: 35358
Joined: 29 Oct 2003 12:31
Location: NowHere

Re: BR Maths Corner-1

Postby SaiK » 29 Jan 2015 17:14

Amber G. wrote:Manjul Bhargava (Fields Medal winner - mentioned many times in brf dhaga) is getting Padma Bhushan on this Republic Day. Congrats.


http://www.ndtv.com/video/player/india- ... ava/353375
India Questions Math Genius Professor Manjul Bhargava

SaiK
BRF Oldie
Posts: 35358
Joined: 29 Oct 2003 12:31
Location: NowHere

Re: BR Maths Corner-1

Postby SaiK » 01 Feb 2015 04:13

http://momath.org/rosenthal-prize/

calling mathrimc, arment, amberji, sunders and mazers et al

A_Gupta
BRF Oldie
Posts: 9790
Joined: 23 Oct 2001 11:31
Contact:

Re: BR Maths Corner-1

Postby A_Gupta » 08 Feb 2015 21:04

SaiK wrote:One hundred people board a 100-seat airplane. The first one has lost his boarding pass, so he sits in a random seat. Each subsequent passenger sits in his own seat if it’s available or takes a random unoccupied seat if it’s not.

What’s the probability that the 100th passenger finds his seat occupied?

http://www.futilitycloset.com/2012/02/29/all-aboard-5/


If there are N passengers, then the probability p(n,k) of the k-th passenger *not* sitting in its assigned seat is, I believe:
p(n,1) = 1/n
p(n,2) = (n-1)/n
p(n,k), where k>2 = 1/(n-k+2)
In particular, p(n,n) = 1/2.

ramana
Forum Moderator
Posts: 47896
Joined: 01 Jan 1970 05:30

Re: BR Maths Corner-1

Postby ramana » 08 Feb 2015 21:54

And the poor fellow thinks its 1/100 and occupies the wrong seat and gets called out. Same thing happens in cinema theaters!

Amber G.
BRF Oldie
Posts: 5829
Joined: 17 Dec 2002 12:31
Location: Ohio, USA

Re: BR Maths Corner-1

Postby Amber G. » 09 Feb 2015 02:46

A_Gupta wrote:
SaiK wrote:One hundred people board a 100-seat airplane. The first one has lost his boarding pass, so he sits in a random seat. Each subsequent passenger sits in his own seat if it’s available or takes a random unoccupied seat if it’s not.

What’s the probability that the 100th passenger finds his seat occupied?

http://www.futilitycloset.com/2012/02/29/all-aboard-5/


If there are N passengers, then the probability p(n,k) of the k-th passenger *not* sitting in its assigned seat is, I believe:
p(n,1) = 1/n
p(n,2) = (n-1)/n
p(n,k), where k>2 = 1/(n-k+2)
In particular, p(n,n) = 1/2.

Hello, I think you have a typo (or some sloppiness).. for example..

when n=1, p(n,1) according to your formula will give 1, the actual answer is ZERO of course, (If there is only 1 seat and 1 person, the person is going to sit in her seat.. ZERO probablity that she will *not* be sitting in its assigned seat.

(Other values are not correct either - for example, when n=100, p(100,1) is 99/100 and NOT 1/100)

Value of p(n,2) is wrong too. (The correct value is 1/n - as one can obviously see - Only way the second person is not sitting in her assigned seat is when the first person selects second person's seat -- etc..)
(The answer 1/2 for p(n,n) is, of course, correct and consistent with previous answers)

PS - It is much easier to see the probabilities, if one counts in the reverse direction from the last person, because it is simply ... 1/2,1/3,1/4 .....something very obvious, if one thinks about it)
(and you get the value 1/(n-k+2) for all positions except first)
Last edited by Amber G. on 09 Feb 2015 03:46, edited 1 time in total.

Amber G.
BRF Oldie
Posts: 5829
Joined: 17 Dec 2002 12:31
Location: Ohio, USA

Re: BR Maths Corner-1

Postby Amber G. » 09 Feb 2015 03:06

SaiK wrote:
Amber G. wrote:Manjul Bhargava (Fields Medal winner - mentioned many times in brf dhaga) is getting Padma Bhushan on this Republic Day. Congrats.


http://www.ndtv.com/video/player/india- ... ava/353375
India Questions Math Genius Professor Manjul Bhargava


Thanks for putting this.

One thing people may have noticed that Manjul's Hema chand series was discussed here in brf years ago.
Yours truly actually called them Hemchand's numbers (Fibonacci) and actually gave a very similar example using sanskrit sloka's.. (For example see http://forums.bharat-rakshak.com/viewtopic.php?p=1266447#p1266447


See this from 2009 about Hemachand's series 1,2,3,5,8,13...http://forums.bharat-rakshak.com/viewtopic.php?p=656248#p656248

Please do see this http://forums.bharat-rakshak.com/viewtopic.php?f=2&t=4201&p=1113960&hilit=hemachand%2A#p1113960
or quite a few posts...

One thing interesting is that Fibonacii himself admits that that work was not originally from him, and he certainly (as he said) had work/books of Indian Mathematician mathematician available to him.

***

Manjul's Q&A brought back good memories... When I was quite young.. I attended a public lecture titled "Beauty of Mathematics" which was given at the local university but I went even though I was much younger. Prof. Mehta, introduced these Fibonacci numbers in very beautiful way and I still remember the excitement of learning new things...I was hooked.

A_Gupta
BRF Oldie
Posts: 9790
Joined: 23 Oct 2001 11:31
Contact:

Re: BR Maths Corner-1

Postby A_Gupta » 09 Feb 2015 17:23

Amber G. wrote:
A_Gupta wrote:
If there are N passengers, then the probability p(n,k) of the k-th passenger *not* sitting in its assigned seat is, I believe:
p(n,1) = 1/n
p(n,2) = (n-1)/n
p(n,k), where k>2 = 1/(n-k+2)
In particular, p(n,n) = 1/2.

Hello, I think you have a typo (or some sloppiness).. for example..

when n=1, p(n,1) according to your formula will give 1, the actual answer is ZERO of course, (If there is only 1 seat and 1 person, the person is going to sit in her seat.. ZERO probablity that she will *not* be sitting in its assigned seat.

(Other values are not correct either - for example, when n=100, p(100,1) is 99/100 and NOT 1/100)

Value of p(n,2) is wrong too. (The correct value is 1/n - as one can obviously see - Only way the second person is not sitting in her assigned seat is when the first person selects second person's seat -- etc..)
(The answer 1/2 for p(n,n) is, of course, correct and consistent with previous answers)

PS - It is much easier to see the probabilities, if one counts in the reverse direction from the last person, because it is simply ... 1/2,1/3,1/4 .....something very obvious, if one thinks about it)
(and you get the value 1/(n-k+2) for all positions except first)


Yes, I typoed reversing the first two, and leaving out the '=' sign.
Sorry for the confusion. Corrected:

p(n,1) = (n-1)/n
p(n,2) = 1/n
p(n,k), where k>=2 = 1/(n-k+2)
In particular, p(n,n) = 1/2

BTW, the "something very obvious, if one thinks about it" is a little misleading, which you see if you examine the contribution to the probability from each branch of the seating decision tree. Fortunately for intuition it all works out.

Amber G.
BRF Oldie
Posts: 5829
Joined: 17 Dec 2002 12:31
Location: Ohio, USA

Re: BR Maths Corner-1

Postby Amber G. » 10 Feb 2015 00:10

A_Gupta wrote:....
Yes, I typoed reversing the first two .. { that's what I guessed, anyway it is now correct... thanks }
...
BTW, the "something very obvious, if one thinks about it" is a little misleading, which you see if you examine the contribution to the probability from each branch of the seating decision tree. Fortunately for intuition it all works out.


I don't think, it is misleading at all, just another way of looking which makes math fun and easy..
Just assume the person who sits last has a number "1" pinned behind him, and counting is done in reverse ways.. the probability from each branch of seating decision tree becomes easy..though counting forward is easy enough too. (Thinking about it as a permutation group in terms of n-cycle decompositions, makes the answer trivial too, if one is familiar with this sort of math).. it is just a matter of choice how you want to count. :)

Anyway - the logic is too consider, say 98th (we will generalize to kth) person (in your way of counting) who is about to sit. This seat could be assigned to either person 1, or 98 or 99 or 100 (It can not be assigned to any other person, say 3rd, because, if it were so, 3rd person will be sitting there)..
Now in only one case (when the seat was assigned to 1) the 98th person is not seating in his/her seat...
so the probability is 1/4 (=1/(100-98+2)) ... (In general case, this, as you said p(n,k) = 1/(n-k+2)) for any case except k=1)

(I hope one realizes that if I pinned numbers 1,2,3 in reverse order, so that 98th person would be (#3 in my counting, this answer comes a little more naturally)

ramana
Forum Moderator
Posts: 47896
Joined: 01 Jan 1970 05:30

Re: BR Maths Corner-1

Postby ramana » 11 Feb 2015 04:19

A-Gupta and AmberG, Thanks for that example. I used it in a crucial conversation and it served its purpose.

Amber G.
BRF Oldie
Posts: 5829
Joined: 17 Dec 2002 12:31
Location: Ohio, USA

Re: BR Maths Corner-1

Postby Amber G. » 12 Feb 2015 00:25

x-posting this in our regular math dhaga ..
ramana wrote:Amberg & Matrimc, Twitter @pickover has image of Bhaskara's formulation of a peacock chasing a snake problem. Its in Sanskrit.

Is this the Bernouli's brachistochrone problem?
Led to calculus of variation.


Hi Ramana,

I wished you put the message and the image with your post for convenience (and avoiding few extra mouse clicks on my part :) )

Anyway I think you are talking about :https://twitter.com/pickover
with this image:
Image

The problem is from Bhaskaracharya's Leelavati book. No it is not .. Bernouli's brachistochrone problem .. a relatively simple problem using what is more popularly known as Pythagorus theorem.

(BTW, this particular verse, and image you can see (among many other important work) in the book you (and I) mentioned several times in the math dhaga :... in Kim Plofker, "Mathematics in India"..

Anyway the problem says (Translation in modern English)

... The square of the pillar is divided by the distance between the snake and its hole; the result is subtracted from the distance between the snake and its hole. The place of meeting of the snake and the peacock is separated from the hole by a number of hastas equal to half that difference. ... There is a hole at the foot of a pillar nine hastas high, and a pet peacock standing on top of it. Seeing a snake returning to the hole at a distance from the pillar equal to three times its height, the peacock descends upon it slantwise. Say quickly, at how many hastas from the hole does the meeting of their two paths occur? (I think, if you want to solve the problem: assume here that the speed of the peacock and the snake are equal.)

Amber G.
BRF Oldie
Posts: 5829
Joined: 17 Dec 2002 12:31
Location: Ohio, USA

Re: BR Maths Corner-1

Postby Amber G. » 12 Feb 2015 03:55

Ramana and others ..

Problem is given <above>

Solution is below:
Enjoy!


ramana
Forum Moderator
Posts: 47896
Joined: 01 Jan 1970 05:30

Re: BR Maths Corner-1

Postby ramana » 12 Feb 2015 04:11

Thanks. So its geometry problem.

Since height of pillar is 9 units can't we use the Pythagorean ratio of 3:4:5 rand get the answer? That would fit the quickly aspect!


Something is bugging me. The word quickly.

Long ago on a book on Calculus of variations, I read the similar formulation of an eagle swooping down to catch a rabbit and to describe the path of the eagle to catch the rabbit in least time.

is quickly same as least time?

Vayutuvan
BRF Oldie
Posts: 9818
Joined: 20 Jun 2011 04:36

Re: BR Maths Corner-1

Postby Vayutuvan » 12 Feb 2015 05:24

AmberG ji: Nice animation.

ramana, AmberG garlu: ramana garu raises a valid point. Peacock is supposed to be a flightless bird. All it could do is jump and alter its path minimally while falling down under the force of gravity. If that is assumed then it is indeed same as the brachiostochrone problem. If not, pthogorus to the rescue of the peacock (or the snake :) ).

That said, my interpretation is that bhAskarAchArya was asking lIlAvati to gove the answer quickly.

Amber G.
BRF Oldie
Posts: 5829
Joined: 17 Dec 2002 12:31
Location: Ohio, USA

Re: BR Maths Corner-1

Postby Amber G. » 12 Feb 2015 06:17

ramana wrote:Something is bugging me. The word quickly.

Long ago on a book on Calculus of variations, I read the similar formulation of an eagle swooping down to catch a rabbit and to describe the path of the eagle to catch the rabbit in least time.

is quickly same as least time?


May be you are thinking of a very famous problem often used as an example while introducing calculus of variation. It is, as you said, known as Brachistochrone problem. ..The path which results in the shortest time for a falling object (on a frictionless curve - like skiing on a slope) to travel from point 1 to point 2... The answer is inverted cycloid (not a straight line). I have seen the demo in a science museum..

(But again, this may not be your problem, as path of an eagle is not the same as free fall on a frictionless curve. Brachistochrone as you said just means "shortest time".. so the name is for a class of problems)

Matrimc - As far as I know, peacock is NOT a flightless bird. I have seen them flying (short hops) and going up fairly high on a tree when chased. :).

Vayutuvan
BRF Oldie
Posts: 9818
Joined: 20 Jun 2011 04:36

Re: BR Maths Corner-1

Postby Vayutuvan » 13 Feb 2015 01:06

AmberG: Not a flightless bird as in penguins. It could have served as a model to Leonardo da Vinci :) Its body weight is far too much to support for the wing span (wing area).

Indeed ramana was thinking about Brachiostochrone problem which was first solved by a Japanese gentleman and a year later independently by Johann Bernoulli. I knew about the problem/and Bernoulli's solution before but Wikipedia gave the further information about the Japanese Mathematician doing so which was published post-humously a year before Bernoulli's paper.

ramana
Forum Moderator
Posts: 47896
Joined: 01 Jan 1970 05:30

Re: BR Maths Corner-1

Postby ramana » 13 Feb 2015 10:17

Yes I was thinking of the brachiostochrone problem. Took me back to my REC days when I was curious about advanced math.

BTW I used the passenger with lost seat number last week to drive home need to swap marginal parts to preclude sub par performance

ramana
Forum Moderator
Posts: 47896
Joined: 01 Jan 1970 05:30

Re: BR Maths Corner-1

Postby ramana » 13 Feb 2015 10:19

Also wasn't it really solved by Jacob Bernoulli and completely by Euler.

ramana
Forum Moderator
Posts: 47896
Joined: 01 Jan 1970 05:30

Re: BR Maths Corner-1

Postby ramana » 13 Feb 2015 10:22

AmberG if we ignore air resistance will it be similar problem?

Amber G.
BRF Oldie
Posts: 5829
Joined: 17 Dec 2002 12:31
Location: Ohio, USA

Re: BR Maths Corner-1

Postby Amber G. » 13 Feb 2015 20:07

ramana wrote:AmberG if we ignore air resistance will it be similar problem?

- In that case, the trajectory is simply a parabola.
(Besides, if we "ignore air".. it will be difficult for eagle to fly in an airless world :) )

Amber G.
BRF Oldie
Posts: 5829
Joined: 17 Dec 2002 12:31
Location: Ohio, USA

Re: BR Maths Corner-1

Postby Amber G. » 13 Feb 2015 20:30

ramana wrote:Also wasn't it really solved by Jacob Bernoulli and completely by Euler.

The problem/legend is VERY well popular..for example see for much more details
http://mathworld.wolfram.com/BrachistochroneProblem.html
or wiki: http://en.wikipedia.org/wiki/Brachistochrone_curve

The problem was tackled by Galileo (his answer was not correct), and was published as a problem by (Johann) Bernoulli. JB Knew the solution (having worked on it for weeks), the solution was published by a few (Newton, Jakob Bernoulli (Johann's brother), Leibniz, l'Hôpital.

Story about Newton (and his great power) is that, he mailed the solution right next morning after receiving it in the evening. That too discovering (and writing about it) a very elegant solution, a completely new branch of Calculus (of variation - which even now is taught only in a graduate level course)

Legend has it that he sent the solution "anonymously". The editors and JB knew right away the anonymous person was no one else but Newton - JB remarked something like: "one can recognize a lion simply by his paw prints " :!:
(Added later: See AT's post below:)
Bernouli is said to have quoted "tanquam ex ungue leonem" (i.e. "the lion is known by his claw" or "I recognize the lion by his claw").



***
matrimc wrote:... It could have served as a model to Leonardo da Vinci :)


Matrimc - Let us not discuss mores (peacocks) any more? :mrgreen: (Sorry if there are groans).

<a picture of a peacock :)>
Last edited by Amber G. on 14 Feb 2015 05:17, edited 4 times in total.

ArmenT
BR Mainsite Crew
Posts: 4239
Joined: 10 Sep 2007 05:57
Location: Loud, Proud, Ugly American

Re: BR Maths Corner-1

Postby ArmenT » 13 Feb 2015 21:06

Amber G. wrote:Legend has it that he sent the solution "anonymously". The editors and JB knew right away the anonymous person was no one else but Newton - JB remarked something like "one can recognize a lion simply by his paw prints" :!:

Bernouli is said to have quoted "tanquam ex ungue leonem" (i.e. "the lion is known by his claw" or "I recognize the lion by his claw").

Amber G.
BRF Oldie
Posts: 5829
Joined: 17 Dec 2002 12:31
Location: Ohio, USA

Re: BR Maths Corner-1

Postby Amber G. » 13 Feb 2015 21:34

^^^ Thanks.
***
xposting here because many will find it interesting:
Saral wrote:http://www.newyorker.com/magazine/2015/02/02/pursuit-beauty

Yitang Zhang, a solitary, part-time calculus teacher at the University of New Hampshire received several prizes, including a MacArthur award in September, for solving a problem that had been open for more than a hundred and fifty years.

Amber G.
BRF Oldie
Posts: 5829
Joined: 17 Dec 2002 12:31
Location: Ohio, USA

Re: BR Maths Corner-1

Postby Amber G. » 13 Feb 2015 23:42

Adding to ArmenT .. some may find this History part very interesting ....
Historical notes - The brachistochrone problem
(some excerpts - please read the original link if interested)
The brachistochrone problem was posed by Johann Bernoulli in Acta Eruditorum in June 1696. He introduced the problem as follows:-

I, Johann Bernoulli, address the most brilliant mathematicians in the world. Nothing is more attractive to intelligent people than an honest, challenging problem, whose possible solution will bestow fame and remain as a lasting monument. Following the example set by Pascal, Fermat, etc., I hope to gain the gratitude of the whole scientific community by placing before the finest mathematicians of our time a problem which will test their methods and the strength of their intellect. If someone communicates to me the solution of the proposed problem, I shall publicly declare him worthy of praise.
...
Given two points A and B in a vertical plane, what is the curve traced out by a point acted on only by gravity, which starts at A and reaches B in the shortest time.

Perhaps we are reading too much into Johann Bernoulli's references to Pascal and Fermat, but it interesting to note that Pascal's most famous challenge concerned the cycloid, which Johann Bernoulli knew at this stage to be the solution to the brachistochrone problem, and his method of solving the problem used ideas due to Fermat.

Johann Bernoulli was not the first to consider the brachistochrone problem. Galileo in 1638 had studied the problem in his famous work Discourse on two new sciences. ...
...
Although Galileo was perfectly correct in this, he then made an error when he next argued that the path of quickest descent from A to B would be an arc of a circle - an incorrect deduction.

Returning to Johann Bernoulli he stated the problem in Acta Eruditorum and, although knowing how to solve it himself, he challenged others to solve it. Leibniz persuaded Johann Bernoulli to allow a longer time for solutions to be produced than the six months he had originally intended so that foreign mathematicians would also have a chance to solve the problem. Five solutions were obtained, Newton, Jacob Bernoulli, Leibniz and de L'Hôpital solving the problem in addition to Johann Bernoulli.

Now Johann Bernoulli and Leibniz deliberately tempted Newton with this problem. It is not surprising, given the dispute over the calculus, that Johann Bernoulli had included these words in his challenge:-

...
there are fewer who are likely to solve our excellent problems, aye, fewer even among the very mathematicians who boast that [they]... have wonderfully extended its bounds by means of the golden theorems which (they thought) were known to no one, but which in fact had long previously been published by others.

According to Newton's biographer Conduitt, he solved the problem in an evening after returning home from the Royal Mint. Newton:-

..
. in the midst of the hurry of the great recoinage, did not come home till four (in the afternoon) from the Tower very much tired, but did not sleep till he had solved it, which was by four in the morning.

The Royal Society published Newton's solution anonymously in the Philosophical Transactions of the Royal Society in January 1697.


Vayutuvan
BRF Oldie
Posts: 9818
Joined: 20 Jun 2011 04:36

Re: BR Maths Corner-1

Postby Vayutuvan » 14 Feb 2015 03:05

matrimc wrote:AmberG: Not a flightless bird as in penguins. It could have served as a model to Leonardo da Vinci :) Its body weight is far too much to support for the wing span (wing area).

Indeed ramana was thinking about Brachiostochrone Brachistochrone problem which was first solved by a Japanese gentleman and a year later independently by Johann Bernoulli. I knew about the problem/and Bernoulli's solution before but Wikipedia gave the further information about the Japanese Mathematician doing so which was published post-humously a year before Bernoulli's paper. (Wikipedia doesn't say anything about that - I apologize to anybody interested in the history of the problem)


Explanation of the edit: Since I cannot edit my previous post anymore, I am editing my quoted post. I was looking at something else (while looking at Parititions, Ferrer Diagrams, Young's Tableau, Young's Lattice, Young-Fibonocci Lattice, and Differential Posets and some other topics on Points in General position, and related computational complexity classes) and mixed up things into the above post. That teaches me not drink coffee while chewing gum. While it spoils the taste of both the gum and coffee, there is the danger spilling coffee all over myself and innocent bystanders too. :)

All is not lost in my faux pas. The connection to representation of symmetric groups and Young's lattice i sinteresteing so is the fact that rank of a vertex in Young-Fobonocci Lattice being the Fibonocci number. If somebody is interested in Integer Partitions, it would be an interesting series of connections going from Partitions to Mathematical Physics.

bhalluka
BRFite -Trainee
Posts: 18
Joined: 11 Aug 2016 06:14

Solution to prisoners dilemma

Postby bhalluka » 16 Feb 2015 11:50

A very interesting breakthrough in game theory.

https://www.quantamagazine.org/20150212 ... -question/

A little sad to see Pakiness win in so many cases. Formal proofs for conditions in which Dharmicness thrives is enlightening.

Amber G.
BRF Oldie
Posts: 5829
Joined: 17 Dec 2002 12:31
Location: Ohio, USA

Re: BR Maths Corner-1

Postby Amber G. » 16 Feb 2015 22:06

^^^ Thanks. If time permits, and you are interested, can you write a small write up for audience here.

Amber G.
BRF Oldie
Posts: 5829
Joined: 17 Dec 2002 12:31
Location: Ohio, USA

Re: BR Maths Corner-1

Postby Amber G. » 19 Feb 2015 19:40

From other dhaga --
RamaY wrote:
Amber G. wrote:Problem:
>> Bhaskara said to Leelavati: Maya took the seventh power of a number (integer) and added seven and said that the result was a perfect square.

Can you guess/calculate Maya's number?

(Number 7 was considered very special in those days) <<


I used Excel and got 25, 52 as possible answers... and it works for any number where the sum of digits is 7.

Now how to prove this theorem?

As said before, Leelavati knew enough not to use Excel as Excel can misguide you. :)

Take 25 for example, it's seventh power (or any power for that matter) ends in 5 so the result after adding 7 ends in 2...
Now we all know a perfect square never ends in (as in last digit) 2.

So 25 will NOT work... which is obvious, if one is not misguided by Excel.... but you already know that now. :)

Yayavar
BRF Oldie
Posts: 4759
Joined: 06 Jun 2008 10:55

Re: BR Maths Corner-1

Postby Yayavar » 23 Feb 2015 03:22

AmberG: when will you be posting the answer.

x^7 - 7 = y^2 turns out doable; but you have asked x^7 + 7 = y^2....

disha
BR Mainsite Crew
Posts: 6076
Joined: 03 Dec 2006 04:17
Location: gaganaviharin

Re: BR Maths Corner-1

Postby disha » 24 Feb 2015 07:10

I do not think sqrt( x^7 + 7 ) has any real solution that is a perfect square. Another way is to just graph it for various values of x.

However it reminds me of the equation y^2 = x^3 + ax + b which is an elliptic curve and an excellent trapdoor function.

So the question I have for math gurus here is - can any of Brahmagupta's equation be used as trapdoors? Easy to calculate one way, hard to calculate the other way? It will be interesting to research it.

PS: Added later of course y^2/7 = (x^7 + 7^1)/7 may be an interesting approach. Or modulo operations itself can be tried (how?). But then modulo operations are again useful in Diffie-Helman exchange.

PPS: Did Bhaskara had a solution for which we are answering the problem now (soln: equations. problem: cryptography)?


Return to “Technology & Economic Forum”

Who is online

Users browsing this forum: No registered users and 11 guests