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.
Rahul Mehta
BRF Oldie
Posts: 2577
Joined: 22 Nov 2001 12:31
Location: Ahmedabad, India --- Bring JurySys in India
Contact:

Re: BR Maths Corner-1

Postby Rahul Mehta » 11 Oct 2014 08:52

I am trying to make a simplified version of question. Is following correct?

1. A planet has rare creatures called dragon. All dragons are very good at logic. Dragon has green eyes or red eyes. If a dragon realizes that he has green eyes, then he will convert itself into a sparrow that midnight. But planet doesnt have mirrors and dragons never talk/ask each other about each others' eye colors.

2. There is a island where three dragons A, B and C land. Each had green eye. They started living together everyday and saw each other on everyday. On first day none became sparrow. On second day too none became sparrow. And on third and forth and later days too , none became sparrow. Why not?

3. You visited that island. And you said to all three dragons in a common gathering "one of you have green eyes". Well, they knew this already. So will any dragon become sparrow? When ? How many?
Last edited by Rahul Mehta on 11 Oct 2014 09:02, edited 1 time in total.

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

Postby ArmenT » 11 Oct 2014 08:55

Interesting article about Gaussian curvature and how it applies to real world issues (such as the best way to eat pizza and why corrugated roofs work)
http://io9.com/how-a-19th-century-math-genius-taught-us-the-best-way-t-1644752036

I always knew you could strengthen a paper by rolling it into a tube, but never really realized that there is a mathematical reasoning behind it.

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

Re: BR Maths Corner-1

Postby Amber G. » 11 Oct 2014 09:11

Few comments about Rahulji's dragon (and similar problem asked before)

1. This is NOT a trick problem and solution is logical, and not easy as such problems go.
2. The problem stated, is fairly accurately stated.
3. Generally one hears solutions of the type " the dragons did not know what "green" means" or some other wording problem.. but to be clear dragons do know what "green " means etc..

Good luck..

A version of this, I have asked ...is about 23 IIT engineers on a camping trip - some clown painted each of their faces in black color while they were sleeping... (same kind of problem)..

SriKumar
BRFite
Posts: 1381
Joined: 27 Feb 2006 07:22
Location: sarvatra

Re:

Postby SriKumar » 11 Oct 2014 20:24

ArmenT wrote:Interesting article about Gaussian curvature and how it applies to real world issues (such as the best way to eat pizza and why corrugated roofs work)
http://io9.com/how-a-19th-century-math-genius-taught-us-the-best-way-t-1644752036

I always knew you could strengthen a paper by rolling it into a tube, but never really realized that there is a mathematical reasoning behind it.
Interesting link and article to popularize math/science and make it more relateable to common experience (though the author did not spend too much time behind the physics of why a curved pizza is stiffer). One of the people acknowledged in the article (at the end) is Steven Strogatz, a prof at MIT (and now at Cornell?) http://www.stevenstrogatz.com/ who's written many books on predicting 'commonplace' phenomena via non-linear dynamics and systems. Such books are interesting because of the various systems that are modeled (physics, biology, chemistry etc.) and go a step beyond popular interest

http://www.valorebooks.com/textbooks/no ... e=10/11/14

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

Re: BR Maths Corner-1

Postby Dan Mazer » 12 Oct 2014 03:20

For the dragon puzzle...

Before the speech

Every dragon knew that at least 99 dragons have blue eyes
Every dragon knew that 99 dragons knew that at least 98 dragons had blue eyes
.....
Every dragon knew that 99 dragons knew that 98 dragons knew that ..... 2 dragons knew that there is at least one dragon with blue eyes


After the speech

Every dragon knows that Every dragon knows that Every dragon knows that ...... there is at least one dragon with blue eyes
Last edited by Dan Mazer on 12 Oct 2014 18:14, edited 1 time in total.

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

Re: BR Maths Corner-1

Postby Amber G. » 12 Oct 2014 06:56

^^^ Articulated extremely well.

Rahul Mehta
BRF Oldie
Posts: 2577
Joined: 22 Nov 2001 12:31
Location: Ahmedabad, India --- Bring JurySys in India
Contact:

Re: BR Maths Corner-1

Postby Rahul Mehta » 12 Oct 2014 21:33

Any proof using boolean algebra notations for dragon problem with EXACTLY 4 dragons? or exactly 3 dragons?

Trust me, it is hard to understand the proof even for 3, 4 dragon and even harder to explain

Also, it is hard to explain why 3 dragons can NEVER deduce it all by themselves even in 1000 days.

===

Say A, B , C are three dragons on island.

And no one tells them anything.

Then

A knows that B knows that at least one dragon namely C has green eyes

A knows that C knows that at least one dragon namely B has green eyes

B knows that A knows that at least one dragon namely C has green eyes

B knows that C knows that at least one dragon namely A has green eyes

C knows that A knows that at least one dragon namely B has green eyes

C knows that B knows that at least one dragon namely A has green eyes

How do we write above in boolean algeraic notations?

And then we need to show that it doesnt imply that A, B , C can conclude that they have green eyes.

And newcomer told A , B and C that "one of you have green eyes"?

How do we write the above statement in boolean algebraic notations?

And then show that above addition enables A, B C to conclude that all have green eyes?

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

Re: BR Maths Corner-1

Postby Amber G. » 12 Oct 2014 23:10

^^^ The problem is VERY old. I was given this (slight variation of this) problem when I was about 7 years old (It was for N=3 case, and there were people with black/white hats instead of dragon with green/red eyes - but the problem was isomorphic to the dragon problem) and was able to do it giving it a very clear solution - people realized that I was good in Math)

Easiest is method of induction.

For N=1 case, the solution is trivial. (If dragon A is told, at least one dragon has green eyes, A will deduce that it must be him/her.

For N=2, again, the problem is simple. (If dragon A sees a red eye (on dragon "B"), it must deduce that it's own eye must the green so .. at the end of day 1, dragon A must turn into a sparrow, it it does not, than B must have a green eye (and everyone knows that on the second day).. IOW (if there is no conversion to sparrow ==> BOTH A&B have to have green eyes. )

Easy to prove, if this is true for N, it is true for N+1 (that is, if among N dragons, no one turn into a sparrow for first N days, than all N dragon knows that all of them have green eyes etc)
QED.
Thus, (for example ) for N=3, On the third day, everyone knows, at least 2 of the dragons have green eyes (N=2 case Since no one turned into a sparrow) so if anyone sees a red eye, it will know that it's own eye is green.
So it will turn into a sparrow. If nothing happens, then everyone knows all three of them have to have green eyes.

===
If some one wants to take a look at nerdy proof one can see, for example Harvard solution to the students:
https://www.physics.harvard.edu/uploads/files/undergrad/probweek/sol2.pdf

===

Interesting part is, (for N=100 case), even if one dragon missed your goodbye message, the dragons will live happily :) as dragons....

Rahul Mehta
BRF Oldie
Posts: 2577
Joined: 22 Nov 2001 12:31
Location: Ahmedabad, India --- Bring JurySys in India
Contact:

Re: BR Maths Corner-1

Postby Rahul Mehta » 13 Oct 2014 12:32

Lets use simplest case of 3 dragons

Say there are three dragons A, B C . Say all have green eyes. Say they all land on island on day-1.

Lets say no human came on island and none said "one has green eyes"

Say all dragons have custom that they stand in a circle for 1 moment everyday and look into each other's eyes

Now each will see that 2 have green eyes on day-1 , day-2 as well as day-3.

So none made any statement, but their standing in circle is EQUIVALENT to making statement "at least 2 of us have green eyes".

So on 3rd day, all three will become sparrow.

How is above logic wrong?

OR , how is standing in a circle, and all looking into everyone's else's eyes, not equal to making statement that "at least one of you have green eyes?"

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

Re: BR Maths Corner-1

Postby Dan Mazer » 13 Oct 2014 13:19

I'll describe from A's perspective. Just by looking around

(1) A only knows only that: B knows that C has green eyes.

(2) Since he doesn't know the colour of his own eyes, A does not know: whether B knows if C knows that there is at least one dragon with green eyes. Remember A is modeling B's model of C's state of knowledge. So both A's eye colour and B's eye colour are unknowns in this model.

Rahul Mehta wrote:So none made any statement, but their standing in circle is EQUIVALENT to making statement "at least 2 of us have green eyes".


If all 3 assent to the above statement then A would know the extra piece of knowledge that:

B knows that C and A have green eyes (different from and adds to (1))

OR , how is standing in a circle, and all looking into everyone's else's eyes, not equal to making statement that "at least one of you have green eyes?"


If all 3 assent to the above statement then A would know the extra piece of knowledge that:

B knows that C knows that there is at least one dragon with green eyes. (different from and adds to (2))

Rahul Mehta
BRF Oldie
Posts: 2577
Joined: 22 Nov 2001 12:31
Location: Ahmedabad, India --- Bring JurySys in India
Contact:

Re: BR Maths Corner-1

Postby Rahul Mehta » 13 Oct 2014 18:31

Dan Mazer wrote:I'll describe from A's perspective. Just by looking around

(1) A only knows only that: B knows that C has green eyes.

(2) Since he doesn't know the colour of his own eyes, A does not know: whether B knows if C knows that there is at least one dragon with green eyes. Remember A is modeling B's model of C's state of knowledge. So both A's eye colour and B's eye colour are unknowns in this model.


beautiful :)

Dan Mazer wrote:
Rahul Mehta wrote:So none made any statement, but their standing in circle is EQUIVALENT to making statement "at least 2 of us have green eyes".


If all 3 assent to the above statement then A would know the extra piece of knowledge that:

B knows that C and A have green eyes (different from and adds to (1))

OR , how is standing in a circle, and all looking into everyone's else's eyes, not equal to making statement that "at least one of you have green eyes?"


If all 3 assent to the above statement then A would know the extra piece of knowledge that:

B knows that C knows that there is at least one dragon with green eyes. (different from and adds to (2))

saip
BRF Oldie
Posts: 3210
Joined: 17 Jan 2003 12:31
Location: USA

Re: BR Maths Corner-1

Postby saip » 17 Dec 2014 00:29

Some one sent me this puzzle.


Five men are sitting at a table playing cards:

Mr. Butcher
Mr. Potter
Mr. Carpenter
Mr. Coal-mechant
Mr. Sailor

The name of each of those men corresponds with a profession. However, the profession of each of
them does not correspond with their names.

Each person is taking only one action at a specific moment in time.

Mr. Butcher hands over the cards to the Sailor to distribute them while the coal-mrechant smokes
a pipe and Mr. Carpenter orders a beer; the fifth man, Mr. Potter smokes the cigar which was
given by the butcher.

What is the profession of each man?

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

Re: BR Maths Corner-1

Postby SaiK » 17 Dec 2014 06:37

aiyoo! i'll go back to nukkad :)

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

Re: BR Maths Corner-1

Postby Vayutuvan » 17 Dec 2014 09:23

^^ the solution is the same as the following problem - given a square 0-1 matrix, decide whether it is a permutation matrix. If it is a permutation matrix, derive the mapping that makes it into an identity matrix.

or in other words, if I place k rooks on a k x k chess board and ask whether all the squares are guarded. If yes, then shuffle the ranks and files of the chess board such that the rooks are all on the diagonal.

Things become interesting if one considers an m x n chess board, m <= n, and I place m rooks on the board. Do I have a m x m chess board whose squares all are guarded by these rooks?

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

Re: BR Maths Corner-1

Postby ArmenT » 17 Dec 2014 12:45

saip wrote:Some one sent me this puzzle.


Five men are sitting at a table playing cards:

Mr. Butcher
Mr. Potter
Mr. Carpenter
Mr. Coal-mechant
Mr. Sailor

The name of each of those men corresponds with a profession. However, the profession of each of
them does not correspond with their names.

Each person is taking only one action at a specific moment in time.

Mr. Butcher hands over the cards to the Sailor to distribute them while the coal-mrechant smokes
a pipe and Mr. Carpenter orders a beer; the fifth man, Mr. Potter smokes the cigar which was
given by the butcher.

What is the profession of each man?


From the description of the actions of the different people (and we are told each one is performing a different action), three are named by name (Mr. Butcher, Mr. Carpenter and Mr. Potter) and two by profession (sailor and coal-merchant). The two people not named by name are Mr. Sailor and Mr. Coal-merchant. Since we are also told that no one's name corresponds to their profession, therefore Mr. Sailor is a coal-merchant and Mr. Coal-merchant is a sailor.

Now the remaining 3 are Mr. Butcher, Mr. Carpenter and Mr. Potter. Now we're told that Mr. Potter was handed a cigar given to him by the butcher. Clearly, the butcher cannot be Mr. Butcher as his name corresponds to his profession. Therefore, the butcher is Mr. Carpenter. Therefore, the potter is Mr. Butcher and carpenter is Mr. Potter. QED.

TLDR version:
Mr. Sailor: Coal merchant
Mr. Coal-merchant: sailor
Mr. Carpenter: butcher
Mr. Butcher: potter
Mr. Potter: carpenter


As Thalaiva once famously said, "jujubee!"

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

Re: BR Maths Corner-1

Postby SaiK » 19 Dec 2014 06:41

on the toeplitz matrix, is it necessary to be constant from left to right? can it be from right to left too?

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

Re: BR Maths Corner-1

Postby Vayutuvan » 30 Dec 2014 23:33

The following is of interest to understand history of Indian mathematics in a small way. I have been going through parts of the following book

Combinatorics: Ancient and Modern, Wilson and Wtakins (editors), 2013, OUP.

The "Introduction" is written by Prof. Donald E. Knuth. Some excerpts from his observations on combinatorics in India:

1. Indian Prosody (called chandas shAstra): Different poetic metres for chanting vEdic poems (or riks) have been codified by pingaLa who was a contemporary of pANini and yAska. The prosody is a study and categorization of poetic metre through the different combinations of short and long syllables. Taking short syllables to be 0s and long syllables to be 1s, it is a study of binary n-tuples. The mnemonic "yamAtArAjabhAnasalagam" is the earliest known "de Bruijn cycle". De Bruijn graphs are very interesting combinatorial objects.

For completeness here is a link to Wikipedia page on de Bruijn Sequence. I suppose one can study higher dimensional de Bruijn torii which can be represented by higher order 0-1 tensors (with a wrap around property). Another interesting study area I think would be in connection with and linear algebraic operations (representation theoretic) on these objects.
Small excerpt follows:

Wikipedia wrote:De Bruijn torus
Main article: De Bruijn torus

A De Bruijn torus is a toroidal array with the property that every k-ary m-by-n matrix occurs exactly once. (It is not necessary that the array be expressed toroidally; the array can be mapped into a 2-dimensional array. Because it is toroidal it "wraps around" on all 4 sides.)

Such a pattern can be used for two-dimensional positional encoding in a fashion analogous to that described above for rotary encoding. Position can be determined by examining the m-by-n matrix directly adjacent to the sensor, and calculating its position on the De Bruijn torus.
De Bruijn decoding

Computing the position of a particular unique tuple or matrix in a De Bruijn sequence or torus is known as the De Bruijn Decoding Problem. Efficient O(n log n) decoding algorithms exists for special, recursively constructed sequences[17] and extend to the two dimensional case.[18] De Bruijn decoding is of interest, e.g., in cases where large sequences or tori are used for positional encoding.


2. There is a small section on Lilavati by Bhaskara on lists of combinations.

3. The work of nArAyaNa pandita's gaNitakaumudi (Lotus Delight of Calculation) written in 1356 has been mentioned. Knuth says that "Chapter 13 anka pAsha (concatenation of numbers)" (I would rather translate it as lassos of numbers), the author gives 97 cryptic sUtrA for systematic combinatorial generation. Knuth himself has continued the systematic generation of combinatorial objects in his 4th volume "the art of computer programming" series. Nefor ethe book was published Knuth released the chpaters as facsicles which can be found even today at his website at Stanford.

In the first chapter written by Kusuba and Ploffker - both names were mentioned by AmberG before in this very same thread - the mELakarta ragas are discussed/. They are 72 in number.

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

Re: BR Maths Corner-1

Postby SaiK » 31 Dec 2014 00:52

Mathematics of Melakartha Ragas in Carnatic Music
http://home.comcast.net/~venkatarama.kr ... 0Music.pdf

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

Re: BR Maths Corner-1

Postby SaiK » 17 Jan 2015 04:03

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/

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

Re: BR Maths Corner-1

Postby Vayutuvan » 18 Jan 2015 23:19

Saik: 0.99 any one of the first 99 could have taken his seat.
Or the other way to look at is that any one if the 100 occupying the seat is the total probability with probability 1. the outcome that 100 th passenger can occupy his seat is 1 out of 100. So she not occupying her assigned seat is 1 - 1/100.

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

Re: BR Maths Corner-1

Postby SaiK » 19 Jan 2015 09:45

that was easy.. why did i link it here? mm

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

Re: BR Maths Corner-1

Postby Amber G. » 19 Jan 2015 11:30

matrimc wrote:Saik: 0.99 any one of the first 99 could have taken his seat.
Or the other way to look at is that any one if the 100 occupying the seat is the total probability with probability 1. the outcome that 100 th passenger can occupy his seat is 1 out of 100. So she not occupying her assigned seat is 1 - 1/100.


No, If you think, (the problem is not very hard, in fact fairly easy if you think the right way).. the answer is 50%..
(Does not depend on total number of seats..) Try our for 2 or 3 or 4 people where one can easily count.

original Q:
[quote="SaiK"]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? [
/quote]

.

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

Re: BR Maths Corner-1

Postby Vayutuvan » 19 Jan 2015 11:37

Yes. Either the last person's seat is occupied by somebody else or it is left for the last person to occupy. It us counter intuitive in that the chance is even and doesn't depend on the number of seats/people (or does it?). I am still not completely convinced by my own argument.

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

Re: BR Maths Corner-1

Postby Amber G. » 20 Jan 2015 05:46

Yes, straight forward analysis is quite easy, but it becomes even more intuitive if we go by "seat" (and whom it is assigned to) rather than the person.

Let us consider the time where all except the last (#100th) passenger has seated.

At this point all seats (except the last seat) is occupied by some person.

So consider the last seat (which was occupied last).. whom it was assigned to?



It can not be, say person number 77, because passenger number 77 is already seated, and as this seat was unoccupied then, #77 would have sat here instead of where he is sitting now.

Same is true for all other cases ---- EXCEPT 1 and 100.

Rest is easy... and you get the answer 1/2.
***

A more popular version (and one which uses a little higher math is the case where all 100 passenger sits "randomly".

What is the probability that AT LEAST ONE person is sitting in his/her own assigned seat?

***
Last edited by Amber G. on 20 Jan 2015 06:08, edited 1 time in total.

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

Re: BR Maths Corner-1

Postby Vayutuvan » 20 Jan 2015 05:59

I got that. Another question is

What is the probability everybody else got her assigned seat? In that case how many got their assigned seats?

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

Re: BR Maths Corner-1

Postby Amber G. » 20 Jan 2015 22:53

matrimc wrote:...Another question is

What is the probability everybody else got her assigned seat? In that case how many got their assigned seats?

It is not at all clear, what do you mean.."every body else got her assign seat" will happen if and only if 1st person chooses her own seat (p=1/100), so it does not remain interesting..

The side problem I asked (repeating again in next post) is really very interesting although it requires, may be just a little more math than average High school..

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

Re: BR Maths Corner-1

Postby Amber G. » 20 Jan 2015 23:21

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)

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

Re: BR Maths Corner-1

Postby SaiK » 21 Jan 2015 00:27

I think the probability of each person sitting in his own assigned seat is zero if he gets to his seat much before the other person comes who is not assigned a middle seat. i hate middle seats.. /fun onlee /no math here. :mrgreen:

this is interesting though.

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

Re: BR Maths Corner-1

Postby Vayutuvan » 21 Jan 2015 01:11

Amber G. wrote:
matrimc wrote:...Another question is

What is the probability everybody else got her assigned seat? In that case how many got their assigned seats?

It is not at all clear, what do you mean.."every body else got her assign seat" will happen if and only if 1st person chooses her own seat (p=1/100), so it does not remain interesting..

No it is interesting in the following sense. Since first person did not sit in his assigned seat, one other person also would not get his assigned seat. So, assuming the rest 99 are seating randomly, one is definitely not going to sit in her assigned seat. The probability that remaining 98 people getting their assigned seats is 1/factorial(98), right?

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

Re: BR Maths Corner-1

Postby Amber G. » 21 Jan 2015 08:17

Only answering the above.. if there is not enough interest, please ignore as it is only covering the specific question raised.

matrimc wrote:
Amber G. wrote:>>>...Another question is

What is the probability everybody else got her assigned seat? In that case how many got their assigned seats? <<<<

It is not at all clear, what do you mean.."every body else got her assign seat" will happen if and only if 1st person chooses her own seat (p=1/100), so it does not remain interesting..

No it is interesting in the following sense. Since first person did not sit in his assigned seat, one other person also would not get his assigned seat. So, assuming the rest 99 are seating randomly, one is definitely not going to sit in her assigned seat. The probability that remaining 98 people getting their assigned seats is 1/factorial(98), right?

As you said ..if the first person did not sit in her assigned seat.. than probability is ZERO that all other 99 will be seating correctly.. There is at least one more person who will be seated in other person's seat. But as you said, 98 is possible.

But probability of that (remaining 98 people getting their assigned seats) is not 1/fatorial(98). It is much much higher (about .05). (98!, BTW is VERY large number - more than the number of atoms in the universe)... Hint: (The number .05 should give the logic/method to calculate the number, if one is really interested)... Hope it helps.

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

Re: BR Maths Corner-1

Postby Vayutuvan » 21 Jan 2015 10:04

Sire, is it that high? Looks like I have to revisit the question tomorrow. Too late right now.

Prem
BRF Oldie
Posts: 19899
Joined: 01 Jul 1999 11:31
Location: Weighing and Waiting 8T Yconomy

Re: BR Maths Corner-1

Postby Prem » 22 Jan 2015 06:04

India Questions Math Genius Professor Manjul Bhargava:
http://www.ndtv.com/article/india/india ... 4#Comments
Watch The Video
arded a prize, which I consider even greater than the Nobel Prize. Prof. Bhargava has recently won the Fields Medal in Mathematics. Why do I say its possibly even greater than the Nobel Prize,


rof Bhargava: Mathematics should be thought of as an art. Sometimes we don't see that when we do mathematics in grade school, but just like any art, music, painting, mathematics is a creative subject. Coming up to the theorems is an art, finding the way to understand why that theorem is true is an art, everyone comes up with a different answer to the same question and the reason is that there are different ways of understanding and ways of expressing yourselves, just like in any art. Mathematics is very much like that and one reason why I teach my course through poetry, through magic, these are all arts, through music, through games, because these are all different kinds of arts and mathematics closely connects to all of them. It should really be taught that way. Mathematics is often taught like a science but a lot of people don't know that its origins, especially in India, is in the arts, and we shouldn't forget that interesting aspect. We should be using both sides of the brain to understand mathematical problems.
NDTV: There is some mathematical basis to music as well., tabla, what is the connection? This is very tough for me to understand, maybe others do, but what are, what is the connection?
Prof Bhargava: Tabla. Tabla is all about rhythms, time cycles, trying to fit various pieces into a rhythm cycle and so, the arrangements that one practices as a tabla player uses a lot of mathematics. One example that I always start with in the class that I teach, just to get people to realise that mathematics is connected with poetry and music, is an example of Hemachandra. That is always one that I start with because it brings in tabla and poetry and mathematics right away. So, in Sanskrit poetry, there are two kinds of syllables, there is a notion of laghu syllable and guru syllable, how many people of heard of laghu and guru before?

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

Re: BR Maths Corner-1

Postby Tuvaluan » 22 Jan 2015 07:10

ArmenT -- I think if you tabulate the information you can't make that logical leap that Sailor and Coal Merchant map to the opposite trade just because their names are not mentioned. If you tabulate the
information about Actions -- Name -- Trade, considering that shuffling the card is a future action and the gave the cigar is a past action so you have the following mapping. ?? means unknown. and (X, Y, Z) means allowed choices given that names and trades cannot match, along with other provided info.

Action====Name=====Trade
??? ==== Mr. S=== (P, B, C, CM)
??? ==== Mr. CM === (P, B, C, S)
hands over cards == Mr. B == (P, C, S)
orders beer == Mr. C == (P, B, S)
smokes a pipe == (Mr.B, Mr.S, Mr.C,Mr.P) — CM
smokes cigar == Mr.P — (B, S, C)

The action ??? could match to "smokes a pipe" which would lead to "Smokes a pipe - Mr. S - CM"
Since There is no information given about Mr. CM, "??? - Mr. CM - S" is a possible option. There may be more, I did not do this too thorougly, so there maybe more than 2 possible solutions.

So we have
Action====Name=====Trade
hands over cards == Mr. B == (P, C)
orders beer == Mr. C == (P, B)
smokes a pipe == Mr.S == CM
smokes cigar == Mr.P — (B, C)
??? == Mr. CM == S

Which gives rise to two possible solutions:


Mr. B - P, Mr. C - B, Mr.P - C Mr. S - CM, Mr. CM - S

and

Mr. B - C, Mr. C - P, Mr.P - B Mr. S - CM, Mr. CM - S

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

Re: BR Maths Corner-1

Postby A_Gupta » 22 Jan 2015 20:38

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 you don't like the argument by symmetry, I have a neat proof by induction.

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

Re: BR Maths Corner-1

Postby Amber G. » 22 Jan 2015 20:49

Tuvaluan wrote:<..Mr. B - C, Mr. C - P, Mr.P - B Mr. S - CM, Mr. CM - S


The solution is not right, .. if nothing else Mr P is not B because:

Mr. Potter smokes the cigar which was given by the butcher.



In fact we know Mr. Carpenter is butcher..
The fact is very trivial -
We have five distinct people doing five different things - (#1- Mr Butcher, #2-Sailor, #3-Coal Miner, #4-Mr Carpenter, and #5-Mr. Potter (who is not a butcher)
So who is butcher ? Not #1 (Because he is called Mr. Butcher), not #2, not#3, not#5 etc,,,
So only person left it #4 . He is Mr. Carpenter.

Rest is easy.

(Equally trivial logic -- ask who is potter, the answer is again easy #1 (Mr. Carpenter)
And now ask is carpenter - #5 etc..)

(ArmenT's solution, is quite correct and very logical)
Last edited by Amber G. on 22 Jan 2015 21:30, edited 1 time in total.

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

Re: BR Maths Corner-1

Postby Amber G. » 22 Jan 2015 21:14

A_Gupta wrote:
If you don't like the argument by symmetry, I have a neat proof by induction.


I have also seen neat, Induction method for the problem I asked above...like to see if some one produces that (or similar) method.
http://forums.bharat-rakshak.com/viewtopic.php?p=1782804#p1782804

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

Re: BR Maths Corner-1

Postby Tuvaluan » 22 Jan 2015 22:34

The solution is not right, .. if nothing else Mr P is not B because:

Quote:
Mr. Potter smokes the cigar which was given by the butcher.


Yes, true, did not encode that fact in table. so the reduced table would have been

Action====Name=====Trade
hands over cards == Mr. B == (P, C)
orders beer == Mr. C == (P, B)
smokes a pipe == Mr.S == CM
smokes cigar == Mr.P — (C)
??? == Mr. CM == S

which leads to the only solution: (since we can eliminate C for Mr. B and thus P for Mr.C)

Action====Name=====Trade
hands over cards == Mr. B == (P)
orders beer == Mr. C == (B)
smokes a pipe == Mr.S == CM
smokes cigar == Mr.P — (C)
??? == Mr. CM == S

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. Of course, my "alternative" solution is clearly wrong...teaches me to double check the answer like in school.

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.

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

Re: BR Maths Corner-1

Postby Amber G. » 23 Jan 2015 00:05

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. Of course, my "alternative" solution is clearly wrong..


If ArmenT does not mind, let me add here.. I am using your table, and ArmenT's logic -- but replaced #1, #2.. etc for actions instead of whole description. (Assume one pinned #1,#2,..#5 behind each person's back according to what they were doing)

I am using:
Mr. Butcher hands over the cards to the Sailor to distribute them while the coal-mrechant smokes a pipe and Mr. Carpenter orders a beer; the fifth man, Mr. Potter smokes the cigar which was
given by the butcher.



Action====Name=====Trade
hands over cards (#1) == Mr. B == ?
Receives cards (#2) == ? == Sailor
Smoke pipe (#3) == ? == CM
(Beer) #4 == Mr C == ?
(cigar) #5 == Mr P == ? (but not butcher)

So easiest to see is to ask: what # is Mr. S and Mr CM ? - the only people not referred by name, (who can not have #1,4,5)? They have to be #2 or #3 (That is , #2 ->Mr CM and #3 -> Mr. Sailor)... And then rest is just too easy. (Now you have left with a case for only 3 people, which is is indeed trivial (rereading AT's post can also make it very clear)

Of course, your table also arrives at the same result, but I still hope this helps.

(Another way is to ask " What Mr. Sailor doing?" , Easy to deduce that he must be smoking Pipe, and hence he is CM -- Ask the same Q for Mr. CM)

(Those who have studied group theory and its representation - using permutation group.. can see right-away the permutation consist of a 3-cycle, and 2-cycle group..)

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

Re: BR Maths Corner-1

Postby Tuvaluan » 23 Jan 2015 02:26

Thanks, Amber G for explaining.

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

Re: BR Maths Corner-1

Postby A_Gupta » 23 Jan 2015 03:45

Amber G. wrote:
A_Gupta wrote:
If you don't like the argument by symmetry, I have a neat proof by induction.


I have also seen neat, Induction method for the problem I asked above...like to see if some one produces that (or similar) method.
http://forums.bharat-rakshak.com/viewtopic.php?p=1782804#p1782804


Should I write up my solution is the question then.


Return to “Technology & Economic Forum”

Who is online

Users browsing this forum: No registered users and 6 guests