BR Maths Corner1

 BRF Oldie
 Posts: 2577
 Joined: 22 Nov 2001 12:31
 Location: Ahmedabad, India  Bring JurySys in India
 Contact:
Re: BR Maths Corner1
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?
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.
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/howa19thcenturymathgeniustaughtusthebestwayt1644752036
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.
http://io9.com/howa19thcenturymathgeniustaughtusthebestwayt1644752036
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.
Re: BR Maths Corner1
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)..
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)..
Re:
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 nonlinear 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 interestArmenT 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/howa19thcenturymathgeniustaughtusthebestwayt1644752036
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.
http://www.valorebooks.com/textbooks/no ... e=10/11/14
Re: BR Maths Corner1
For the dragon puzzle...
Before the speech
After the speech
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.
Re: BR Maths Corner1
^^^ Articulated extremely well.

 BRF Oldie
 Posts: 2577
 Joined: 22 Nov 2001 12:31
 Location: Ahmedabad, India  Bring JurySys in India
 Contact:
Re: BR Maths Corner1
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?
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?
Re: BR Maths Corner1
^^^ 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....
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....

 BRF Oldie
 Posts: 2577
 Joined: 22 Nov 2001 12:31
 Location: Ahmedabad, India  Bring JurySys in India
 Contact:
Re: BR Maths Corner1
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 day1.
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 day1 , day2 as well as day3.
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?"
Say there are three dragons A, B C . Say all have green eyes. Say they all land on island on day1.
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 day1 , day2 as well as day3.
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?"
Re: BR Maths Corner1
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.
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))
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))
(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))

 BRF Oldie
 Posts: 2577
 Joined: 22 Nov 2001 12:31
 Location: Ahmedabad, India  Bring JurySys in India
 Contact:
Re: BR Maths Corner1
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))
Re: BR Maths Corner1
Some one sent me this puzzle.
Five men are sitting at a table playing cards:
Mr. Butcher
Mr. Potter
Mr. Carpenter
Mr. Coalmechant
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 coalmrechant 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?
Five men are sitting at a table playing cards:
Mr. Butcher
Mr. Potter
Mr. Carpenter
Mr. Coalmechant
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 coalmrechant 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?
Re: BR Maths Corner1
aiyoo! i'll go back to nukkad
Re: BR Maths Corner1
^^ the solution is the same as the following problem  given a square 01 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?
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?
Re: BR Maths Corner1
saip wrote:Some one sent me this puzzle.
Five men are sitting at a table playing cards:
Mr. Butcher
Mr. Potter
Mr. Carpenter
Mr. Coalmechant
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 coalmrechant 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 coalmerchant). The two people not named by name are Mr. Sailor and Mr. Coalmerchant. Since we are also told that no one's name corresponds to their profession, therefore Mr. Sailor is a coalmerchant and Mr. Coalmerchant 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. Coalmerchant: sailor
Mr. Carpenter: butcher
Mr. Butcher: potter
Mr. Potter: carpenter
As Thalaiva once famously said, "jujubee!"
Re: BR Maths Corner1
on the toeplitz matrix, is it necessary to be constant from left to right? can it be from right to left too?
Re: BR Maths Corner1
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 ntuples. 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 01 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:
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.
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 ntuples. 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 01 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 kary mbyn matrix occurs exactly once. (It is not necessary that the array be expressed toroidally; the array can be mapped into a 2dimensional array. Because it is toroidal it "wraps around" on all 4 sides.)
Such a pattern can be used for twodimensional positional encoding in a fashion analogous to that described above for rotary encoding. Position can be determined by examining the mbyn 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.
Re: BR Maths Corner1
Mathematics of Melakartha Ragas in Carnatic Music
http://home.comcast.net/~venkatarama.kr ... 0Music.pdf
http://home.comcast.net/~venkatarama.kr ... 0Music.pdf
Re: BR Maths Corner1
One hundred people board a 100seat 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/allaboard5/
What’s the probability that the 100th passenger finds his seat occupied?
http://www.futilitycloset.com/2012/02/29/allaboard5/
Re: BR Maths Corner1
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.
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.
Re: BR Maths Corner1
that was easy.. why did i link it here? mm
Re: BR Maths Corner1
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 100seat 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]
.
Re: BR Maths Corner1
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.
Re: BR Maths Corner1
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?
***
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.
Re: BR Maths Corner1
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?
What is the probability everybody else got her assigned seat? In that case how many got their assigned seats?
Re: BR Maths Corner1
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..
Re: BR Maths Corner1
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)
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)
Re: BR Maths Corner1
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.
this is interesting though.
this is interesting though.
Re: BR Maths Corner1
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?
Re: BR Maths Corner1
Only answering the above.. if there is not enough interest, please ignore as it is only covering the specific question raised.
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.
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.
Re: BR Maths Corner1
Sire, is it that high? Looks like I have to revisit the question tomorrow. Too late right now.
Re: BR Maths Corner1
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?
Re: BR Maths Corner1
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
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
Re: BR Maths Corner1
SaiK wrote:One hundred people board a 100seat 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/allaboard5/
If you don't like the argument by symmetry, I have a neat proof by induction.
Re: BR Maths Corner1
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, #2Sailor, #3Coal Miner, #4Mr Carpenter, and #5Mr. 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.
Re: BR Maths Corner1
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.bharatrakshak.com/viewtopic.php?p=1782804#p1782804
Re: BR Maths Corner1
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.
Re: BR Maths Corner1
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 coalmrechant 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 rightaway the permutation consist of a 3cycle, and 2cycle group..)
Re: BR Maths Corner1
Thanks, Amber G for explaining.
Re: BR Maths Corner1
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.bharatrakshak.com/viewtopic.php?p=1782804#p1782804
Should I write up my solution is the question then.