[algogeeks] Re: crazy man in the airplane

[Geoffrey Summerhayes]

On Sep 11, 10:32 am, Karthik Singaram Lakshmanan
 wrote:
> The deal is that if anyone chooses seat 1 then everyone else will go
> to their proper places and person 100 will get seat 100
>
> The probability of passenger 1 choosing seat 1 is (1/100)
> Say, he chooses seat (a_1) where (1 < a_1 < 100), this also happens
> with prob. (1/100)
> We can ignore the case where he chooses seat (100) since that implies
> that passenger 100 is not going to get his seat anyways
>
> Now, passenger (a_1) can choose seat 1 with probability (1/(100-a_1+1))
> Say, he chooses seat (a_2) where (a_1 < a_2 < 100), this also happens
> with prob. (1/(100-a_1+1))
> We can ignore the case where he chooses seat (100) since that implies
> that passenger 100 is not going to get his seat anyways
>
> Now, passenger (a_2) can choose seat 1 with probability (1/(100-a_2+1))
> Say, he chooses seat (a_3) where (a_2 < a_3 < 100), this also happens
> with prob. (1/(100-a_3+1))
> We can ignore the case where he chooses seat (100) since that implies
> that passenger 100 is not going to get his seat anyways
>
> This continues
> Say F(x) = (1/(100-x+1)) for convenience
> Say Q(x) = F(x) + F(x)*SUM[x < r < 100] Q(r)
> Q(x) denotes the probability that either passenger x chooses seat 1 or
> one of the passengers coming after him (before passenger 100) chooses
> seat 1
>
> The solution to our problem is therefore Q(1)
> Q(99) = F(99) = (1/(100-99+1)) = (1/2)
> Q(98) = F(98) + F(98)*(Q(99)) = (1/3) + (1/3)*(1/2) = (1/3)*(3/2) = (1/2)
> Q(97) = F(97) + F(97)*(Q(98)+Q(99)) = (1/4) + (1/4)*(1/2+1/2) =
> (1/4)*(2) = (1/2)
> .
> Q(x) = F(x) + F(x)*SUM[x < r < 100] Q(r) =
> F(x){1+(100-x-1)/2}=(1/(100-x+1))*(100-x+1)/2 = (1/2)
> 
> Q(1) = (1/2)
>
> As with most probability problems, I am sure there is a much simpler
> (and intuitive) explanation, but I prefer this solution to make sure
> that I am not making arbit assumptions.

Doesn't matter how many passengers or seats there are,
as long as they are equal and larger than one. There are
only two seats that matter, the first passenger's seat and
the last passenger's seat.

The tricky part is convincing someone that the last boarder
must end up in one of those two seats.

Which means if anyone takes either of those seats, the
last boarder ends up in the other one. Every time someone
makes a random pick, if they pick one of those two seats
the probabilities for either are equal so it's a 50-50, if
they don't pick they just pass the ultimate decision on
to someone later in the line.

--
Geoff

--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---

[algogeeks] Re: find triangle in a graph

[ankur aggarwal]

@dufus
i read this ques from somewhere .
dont know wat the examiner is looking for...

i think it mite work,,

On Tue, Sep 8, 2009 at 8:38 PM, manish bhatia  wrote:

> how about finding all the connected-components and checking which all have
> 3 edges?
>
>  --
> *From:* ankur aggarwal 
> *To:* "i...@mca_2007" ;
> lets-talk-g...@googlegroups.com; algogeeks@googlegroups.com
> *Sent:* Sunday, 6 September, 2009 2:58:40 PM
> *Subject:* [algogeeks] find triangle in a graph
>
>  google question : find triangle in a graph Given an undirected graph,
> design a O(V+E) algo to detect whether there is a triangle in the graph ot
> not.
>
> --
> Looking for local information? Find it on Yahoo! 
> Local
>
> >
>

--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---

[algogeeks] Re: addition without using arithmetic operators

[ankur aggarwal]

@all

 int main() {

  int a,b;
  cin>>a>>b;

  char *ptr = (char *) a;
  char *ptr2 = &ptr[b];
  cout<< (int) ptr2 

[algogeeks] Re: find minimum number of races

[ankur aggarwal]

7

On Fri, Sep 11, 2009 at 8:14 PM, Dave  wrote:

>
> Answered recently: see
> http://groups.google.com/group/algogeeks/msg/077bdb6a282a1184
>
> Dave
>
> On Sep 11, 9:32 am, dinesh bansal  wrote:
> > Hi All,
> >
> > I got a question:
> > I have 25 horses and I need to find the 1st, 2nd and 3rd fastest among
> all.
> > I have a race course of 5 tracks. That means I can run 5 horses at a
> time.
> > What are the minimum number of races required for this.
> >
> > Thanks,
> >
> > --
> > Dinesh Bansal
> > The Law of Win says, "Let's not do it your way or my way; let's do it the
> > best way."
> >
>

--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---

[algogeeks] Un-sort

[Neeraj Kr.]

There are numbers list starting from 1 to n,placed randomly.
To sort these numbers an algorithm is used.
Starting from the left, one by one; move a number in left direction
until there is no greater number to the left of the number.
Input:
The left moves requires for each position to sort are given
Output:
unsorted list

Ex.
Input:
0 0 1 0 3
Output:
1 4 3 5 2

Input:
0 1 2 3 4
Output:
5 4 3 2 1

How can use tree to solve this question ?

--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---

[algogeeks] Re: nth number of k bits

[ashish gupta]

unsigned next_number( unsigned x)
{
unsigned smallest, ripple, one;
(1)smallest = x & (-x);
(2)ripple = x + smallest ;
(3)one = ripple^x;
(4)one = (one>>2)/smallest;
(5) return ripple | one ;
}

let x is a given number in which (let say ) k bits are set. Now our aim to
find next big number while keeping no. of set bits equal to k.
Explanation:- let say here we take a  x = aaa0   as an example. a
may be anything which is previously in the given number. Now result of the
next_number function should be
x = aaa1  0111
(1) smallest = x& (-x) ; smallest contains the rightmost set bit, any other
bit is 0.
 smallest = aaa0 0001 
(2) ripple = x  + smallest ;  ripple = aaa1   ( now one bit of the
result is in the ripple. we have to bring remaining 3 bit somehow in the
right adjusted position.
(3)one = ripple^x; // one  = 0001  
(4) one= one/smallest ; one =  0001 
( dividing one by smallest will generate all the 1's bit at the right most
position . but this number will keep two 1's more than required. hence right
shift one by 2 position .
one = one>>2;
( 5) now OR this number with ripple and you will get the answer.

Hope this explanation should work.

On Fri, Sep 11, 2009 at 7:14 PM, amarnath .  wrote:

> can u please explain me the logic behind finding  the next number?
>
>
> On Fri, Sep 11, 2009 at 1:42 AM, ashish gupta wrote:
>
>> I think this should be easy to understand.
>>
>> #include
>> using namespace std;
>> // this function generated next big number of the list having k bit set.
>> unsigned next_number( unsigned x)
>> {
>> unsigned smallest, ripple, one;
>> smallest = x & (-x);
>> ripple = x + smallest ;
>> one = ripple^x;
>> one = (one>>2)/smallest;
>> return ripple | one ;
>> }
>>
>> // this function first set the initial to the first element of the list
>> and then call next_number function //(n-1) times to get nth element of the
>> list.
>> unsigned int nth_number_of_k_setbit(unsigned int k, unsigned n)
>> {
>> unsigned initial = 1,i ;
>> for (i = 0; i < (k-1); i += 1)
>> initial = (initial<<1) | (1);
>> for (i = 0; i < n-1; i += 1)
>> initial =  next_number( initial);
>> return initial;
>> }
>>
>> int main()
>> {
>> cout<<"enter the value of k"<> unsigned k;
>> cin>>k;
>> cout<<"enter the value of n"<> unsigned n;
>> cin>>n;
>> cout.setf(ios::hex, ios::basefield);
>> cout<<"nth number of the increasing order of k-bit set list
>> is:"<> cout<>
>> return 0;
>> }
>>
>> hope this should help you.
>>
>>
>> --
>> Ashish Gupta
>> Ph. no. +91 9795 531 047
>>
>>
>> On Thu, Aug 27, 2009 at 10:35 PM, ankur aggarwal <
>> ankur.mast@gmail.com> wrote:
>>
>>> @shishir
>>>
>>>  plz give an example..
>>> its bit tough to understand for me atleast..
>>>
>>>
>>> On Thu, Aug 27, 2009 at 6:10 PM, Shishir Mittal 
>>> <1987.shis...@gmail.com>wrote:
>>>
 Its a bit similar to finding the rank of the word "COMPUTER" in the
 dictionary among the words formed from C,O,M,P,U,T,E,R.

 Find maximum r such that (k+r)C(r) < n.
 This represents the total number of numbers formed from 'r' 0 bits and
 'k' 1 bits. Since n is greater, it implies it has an extra 1 bit in its
 representation.
 The problem reduces to finding [n - (m+r)C(r)] smallest number than can
 be formed with (k-1) 1 bits.

 here is a recursive function to obtain the result.
 int rec(int curr, int n, int k){
int r,j,comb,tmp;
   if(n==1)
 return curr+((1<>>> */
   for(r =1,comb = 1; ; r++)
   {
 tmp = (comb*(k+r))/r;  /* k+rCr = (k+r-1)C(r-1) x (k+r)/r*/
 if(tmp == n)
   return curr + (1<<(k+r)) - (1<>>> should be 1 and rest 0  */
 else if(tmp > n)
   return rec(curr+(1<<(k+r-1)), n-comb,k-1);
 comb= tmp;
   }
 }

 Call rec(0,n,k) to get the nth number of the series with 'k' bits set.

 On Thu, Aug 27, 2009 at 12:28 PM, ankur aggarwal <
 ankur.mast@gmail.com> wrote:

>
> Nth number with K set bits
> We are given with k number of set bits (bit=1). We have to find the Nth
> number which has k set bits.
>
> for example
>
> k=3
>
> the numbers with k set bits are as follows:
>
> 000111 = 7
> 001011 = 11
> 001101 = 13
> 001110 = 14
> 010011 = 19
> 010101 = 21
> 010110 = 22
> 011001 = 25
> 011010 = 26
> 011100 = 28
> 
> and so on
>
> we have to find the Nth number in this series...
>
> suggest some method
>
>
>


 --
 Shishir Mittal
 Ph: +91 9936 180 121



>>>
>>>
>>>
>>
>>
>>
>
> >
>

--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups

[algogeeks] Mapping problem

[Geoffrey Summerhayes]

Here's what I'm working on now...

Given a rectangular map m by n projected from a place on earth
determine the xy coords on the map given a list latitude and
longitude.

Now the tricky part, don't know the type of projection beforehand
except
that the map has no holes, missing corners or tears and any contiguous
points on the map are contiguous on the planet, can query any point on
the map for it's latitude and longitude before processing the list,
but not
during.

Reason for the first is to accomodate different mapping software, now
and
in the future, the no holes will be a requirement for the mapping
software,
and the last is due to threading issues, when it comes time to display
the map the software may be generating a different image.

Can anyone come up with an algorithm that uses a minimum # of points
and can calculate points minimizes the amount of error?
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---

[algogeeks] Re: find minimum number of races

[sharad kumar]

7

On Fri, Sep 11, 2009 at 8:02 PM, dinesh bansal  wrote:

> Hi All,
>
> I got a question:
> I have 25 horses and I need to find the 1st, 2nd and 3rd fastest among all.
> I have a race course of 5 tracks. That means I can run 5 horses at a time.
> What are the minimum number of races required for this.
>
> Thanks,
>
> --
> Dinesh Bansal
> The Law of Win says, "Let's not do it your way or my way; let's do it the
> best way."
>
> >
>

--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---

[algogeeks] Re: find minimum number of races

[Dave]

Answered recently: see 
http://groups.google.com/group/algogeeks/msg/077bdb6a282a1184

Dave

On Sep 11, 9:32 am, dinesh bansal  wrote:
> Hi All,
>
> I got a question:
> I have 25 horses and I need to find the 1st, 2nd and 3rd fastest among all.
> I have a race course of 5 tracks. That means I can run 5 horses at a time.
> What are the minimum number of races required for this.
>
> Thanks,
>
> --
> Dinesh Bansal
> The Law of Win says, "Let's not do it your way or my way; let's do it the
> best way."
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---

[algogeeks] Re: find minimum number of races

[sharad kumar]

boss search the forums related t o soring million nummbers in finite
memory.i have given the result and explained i

On Fri, Sep 11, 2009 at 8:10 PM, sharad kumar wrote:

> 7
>
> On Fri, Sep 11, 2009 at 8:02 PM, dinesh bansal wrote:
>
>> Hi All,
>>
>> I got a question:
>> I have 25 horses and I need to find the 1st, 2nd and 3rd fastest among
>> all. I have a race course of 5 tracks. That means I can run 5 horses at a
>> time. What are the minimum number of races required for this.
>>
>> Thanks,
>>
>> --
>> Dinesh Bansal
>> The Law of Win says, "Let's not do it your way or my way; let's do it the
>> best way."
>>
>> >>
>>
>

--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---

[algogeeks] find minimum number of races

[dinesh bansal]

Hi All,

I got a question:
I have 25 horses and I need to find the 1st, 2nd and 3rd fastest among all.
I have a race course of 5 tracks. That means I can run 5 horses at a time.
What are the minimum number of races required for this.

Thanks,

-- 
Dinesh Bansal
The Law of Win says, "Let's not do it your way or my way; let's do it the
best way."

--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---

[algogeeks] Re: crazy man in the airplane

[Karthik Singaram Lakshmanan]

The deal is that if anyone chooses seat 1 then everyone else will go
to their proper places and person 100 will get seat 100

The probability of passenger 1 choosing seat 1 is (1/100)
Say, he chooses seat (a_1) where (1 < a_1 < 100), this also happens
with prob. (1/100)
We can ignore the case where he chooses seat (100) since that implies
that passenger 100 is not going to get his seat anyways

Now, passenger (a_1) can choose seat 1 with probability (1/(100-a_1+1))
Say, he chooses seat (a_2) where (a_1 < a_2 < 100), this also happens
with prob. (1/(100-a_1+1))
We can ignore the case where he chooses seat (100) since that implies
that passenger 100 is not going to get his seat anyways


Now, passenger (a_2) can choose seat 1 with probability (1/(100-a_2+1))
Say, he chooses seat (a_3) where (a_2 < a_3 < 100), this also happens
with prob. (1/(100-a_3+1))
We can ignore the case where he chooses seat (100) since that implies
that passenger 100 is not going to get his seat anyways


This continues
Say F(x) = (1/(100-x+1)) for convenience
Say Q(x) = F(x) + F(x)*SUM[x < r < 100] Q(r)
Q(x) denotes the probability that either passenger x chooses seat 1 or
one of the passengers coming after him (before passenger 100) chooses
seat 1

The solution to our problem is therefore Q(1)
Q(99) = F(99) = (1/(100-99+1)) = (1/2)
Q(98) = F(98) + F(98)*(Q(99)) = (1/3) + (1/3)*(1/2) = (1/3)*(3/2) = (1/2)
Q(97) = F(97) + F(97)*(Q(98)+Q(99)) = (1/4) + (1/4)*(1/2+1/2) =
(1/4)*(2) = (1/2)
.
Q(x) = F(x) + F(x)*SUM[x < r < 100] Q(r) =
F(x){1+(100-x-1)/2}=(1/(100-x+1))*(100-x+1)/2 = (1/2)

Q(1) = (1/2)

As with most probability problems, I am sure there is a much simpler
(and intuitive) explanation, but I prefer this solution to make sure
that I am not making arbit assumptions.

Cheers,
Karthik

--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---

[algogeeks] Re: nth number of k bits

[amarnath .....]

can u please explain me the logic behind finding  the next number?

On Fri, Sep 11, 2009 at 1:42 AM, ashish gupta wrote:

> I think this should be easy to understand.
>
> #include
> using namespace std;
> // this function generated next big number of the list having k bit set.
> unsigned next_number( unsigned x)
> {
> unsigned smallest, ripple, one;
> smallest = x & (-x);
> ripple = x + smallest ;
> one = ripple^x;
> one = (one>>2)/smallest;
> return ripple | one ;
> }
>
> // this function first set the initial to the first element of the list and
> then call next_number function //(n-1) times to get nth element of the list.
> unsigned int nth_number_of_k_setbit(unsigned int k, unsigned n)
> {
> unsigned initial = 1,i ;
> for (i = 0; i < (k-1); i += 1)
> initial = (initial<<1) | (1);
> for (i = 0; i < n-1; i += 1)
> initial =  next_number( initial);
> return initial;
> }
>
> int main()
> {
> cout<<"enter the value of k"< unsigned k;
> cin>>k;
> cout<<"enter the value of n"< unsigned n;
> cin>>n;
> cout.setf(ios::hex, ios::basefield);
> cout<<"nth number of the increasing order of k-bit set list
> is:"< cout<
> return 0;
> }
>
> hope this should help you.
>
>
> --
> Ashish Gupta
> Ph. no. +91 9795 531 047
>
>
> On Thu, Aug 27, 2009 at 10:35 PM, ankur aggarwal  > wrote:
>
>> @shishir
>>
>>  plz give an example..
>> its bit tough to understand for me atleast..
>>
>>
>> On Thu, Aug 27, 2009 at 6:10 PM, Shishir Mittal 
>> <1987.shis...@gmail.com>wrote:
>>
>>> Its a bit similar to finding the rank of the word "COMPUTER" in the
>>> dictionary among the words formed from C,O,M,P,U,T,E,R.
>>>
>>> Find maximum r such that (k+r)C(r) < n.
>>> This represents the total number of numbers formed from 'r' 0 bits and
>>> 'k' 1 bits. Since n is greater, it implies it has an extra 1 bit in its
>>> representation.
>>> The problem reduces to finding [n - (m+r)C(r)] smallest number than can
>>> be formed with (k-1) 1 bits.
>>>
>>> here is a recursive function to obtain the result.
>>> int rec(int curr, int n, int k){
>>>int r,j,comb,tmp;
>>>   if(n==1)
>>> return curr+((1<>> */
>>>   for(r =1,comb = 1; ; r++)
>>>   {
>>> tmp = (comb*(k+r))/r;  /* k+rCr = (k+r-1)C(r-1) x (k+r)/r*/
>>> if(tmp == n)
>>>   return curr + (1<<(k+r)) - (1<>> should be 1 and rest 0  */
>>> else if(tmp > n)
>>>   return rec(curr+(1<<(k+r-1)), n-comb,k-1);
>>> comb= tmp;
>>>   }
>>> }
>>>
>>> Call rec(0,n,k) to get the nth number of the series with 'k' bits set.
>>>
>>> On Thu, Aug 27, 2009 at 12:28 PM, ankur aggarwal <
>>> ankur.mast@gmail.com> wrote:
>>>

 Nth number with K set bits
 We are given with k number of set bits (bit=1). We have to find the Nth
 number which has k set bits.

 for example

 k=3

 the numbers with k set bits are as follows:

 000111 = 7
 001011 = 11
 001101 = 13
 001110 = 14
 010011 = 19
 010101 = 21
 010110 = 22
 011001 = 25
 011010 = 26
 011100 = 28
 
 and so on

 we have to find the Nth number in this series...

 suggest some method



>>>
>>>
>>> --
>>> Shishir Mittal
>>> Ph: +91 9936 180 121
>>>
>>>
>>>
>>
>>
>>
>
> >
>

--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---

[algogeeks] Re: crazy man in the airplane

[Dhruva Sagar]

This is what I have :There are 100 seats and are to be occupied by 99 people
(excluding the 100th one).
There are 100 ways of doing this arrangement in all, irrespective of their
order.
Hence the probability of the 100th person sitting in the right seat should
then be 1/100.

Thanks & Regards,
Dhruva Sagar.


Stephen 
Leacock
- "I detest life-insurance agents: they always argue that I shall some
day
die, which is not so."

On Fri, Sep 11, 2009 at 7:30 AM, ganesa thandavam wrote:

>
> whence this question was asked to me... i was doing a lot of
> calculations ... but the body language of the person who questioned me
> suggested that there is some trick in it...
>
> so i answered 1/2...
>
>  and it proved to be right ...and i somehow convinced him of the way i
> found out the answer
>
> but i dont have an explanation...now i tried to build up an
> explanation but could nt come up with a convincing one...
>
> so looking forward to some of the best explanations :)
>
> On Sep 10, 10:21 pm, ankur aggarwal  wrote:
> >  crazy man in the airplane A line of 100 airline passengers is waiting to
> > board a plane. they each hold a ticket to one of the 100 seats on that
> > flight. (for convenience, let's say that the nth passenger in line has a
> > ticket for the seat number n.)
> >
> > Unfortunately, the first person in line is crazy, and will ignore the
> seat
> > number on their ticket, picking a random seat to occupy. all of the other
> > passengers are quite normal, and will go to their proper seat unless it
> is
> > already occupied. if it is occupied, they will then find a free seat to
> sit
> > in, at random.
> > What is the probability that the last (100th) person to board the plane
> will
> > sit in his proper seat (#100)?
>
> >
>

--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---

[algogeeks] Re: crazy man in the airplane

[ganesa thandavam]

whence this question was asked to me... i was doing a lot of
calculations ... but the body language of the person who questioned me
suggested that there is some trick in it...

so i answered 1/2...

 and it proved to be right ...and i somehow convinced him of the way i
found out the answer

but i dont have an explanation...now i tried to build up an
explanation but could nt come up with a convincing one...

so looking forward to some of the best explanations :)

On Sep 10, 10:21 pm, ankur aggarwal  wrote:
>  crazy man in the airplane A line of 100 airline passengers is waiting to
> board a plane. they each hold a ticket to one of the 100 seats on that
> flight. (for convenience, let's say that the nth passenger in line has a
> ticket for the seat number n.)
>
> Unfortunately, the first person in line is crazy, and will ignore the seat
> number on their ticket, picking a random seat to occupy. all of the other
> passengers are quite normal, and will go to their proper seat unless it is
> already occupied. if it is occupied, they will then find a free seat to sit
> in, at random.
> What is the probability that the last (100th) person to board the plane will
> sit in his proper seat (#100)?

--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---

[algogeeks] Re: crazy man in the airplane

[Nagendra Kumar]

1/2


On Thu, Sep 10, 2009 at 10:51 PM, ankur aggarwal
 wrote:
> crazy man in the airplane
>
> A line of 100 airline passengers is waiting to board a plane. they each hold
> a ticket to one of the 100 seats on that flight. (for convenience, let's say
> that the nth passenger in line has a ticket for the seat number n.)
>
> Unfortunately, the first person in line is crazy, and will ignore the seat
> number on their ticket, picking a random seat to occupy. all of the other
> passengers are quite normal, and will go to their proper seat unless it is
> already occupied. if it is occupied, they will then find a free seat to sit
> in, at random.
> What is the probability that the last (100th) person to board the plane will
> sit in his proper seat (#100)?
> >
>

--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---