Probability to get all 3 right = 1/6 Probability to get only 1 right = 3/6 Probability to get none right = 2/6
If you get all 3 right, then it took only 1 try If you get 1 right, then you have 2 left .. hope you agree that on an avg, it will take 2 more tries [E(2) = 2] on an avg to solve this. Hence, total 3 tries If you get none right, on an avg, you will take E(3) more tries to solve this in an avg. So total tries = 1+E(3). So, E(3) = (1/6)*1 + (3/6)*3 + (2/6)*(1+E(3)) = 1/6 + 9/6 + 2/6 + 2/6*E(3) 4/6 E(3) = 12/6 E(3) = 12/4 = 3 On 9 May 2011 12:13, Eagle <[email protected]> wrote: > @Bharath, No it should require 6 hits in your case, if you extend the > following logic- > > For the three unsorted numbers 3 1 2, the sample set of arrangements > is- > > 1 2 3 > 1 3 2 > 2 1 3 > 2 3 1 - Not even one in correct position > 3 1 2 - Not even one in correct position > 3 2 1 > The probability of at least one number being at its sorted position is > 2/3, while the probability of not getting even one number in its > correct position is 1/3. So, how come, all of a sudden, the > probability of getting at least one number in its correct position is > becoming 1.0? If at all, average hits are to be calculated (being > average, it can be non-integer real number), then it would be > reciprocal of 2/3, that is, 3/2, that is 1.5 and not 1. > Also, while calculating total probability of dependent events, you > MULTIPLY the individual probabilities, and NOT add them. > In the present example, the P(exactly one element in correct position) > is 3/6 = 1/2. After that event is realized, Goro will hold that > number, and only two unsorted numbers are there. This time, the > P(correct sorting) is 1/2. So, the combined probability is 1/2 x 1/2 = > 1/4. Thus, total 4 hits would be required on average. > (If my analysis is correct, I will have the life-time joy of catching > Google employees making logical error! Ha ha ha!!) > > Eagle > > On May 9, 7:45 am, Bharath Raghavendran <[email protected]> wrote: >> The 4 steps for sorting are not definite. Its just that Goro has to >> follow the following steps : >> * Hold down any element that is in its place >> * Bang table to re-arrange other elements. >> >> Repeat this step till all elements are sorted. As elements get in >> place, include them into the held down elements. >> >> If Goro is lucky, all elements get sorted in a single step. >> If Goro is unlucky, it can take indefinitely long to sort. >> On an average, you will see that the above method will get the >> elements sorted in 4 shots. >> >> On 9 May 2011 06:32, WL Teng <[email protected]> wrote: >> >> > Could anyone show me what are the four steps in sorting 4 1 2 3? >> >> > Sorry for the repost, if any, because my old post did not show up. >> >> > -- >> > You received this message because you are subscribed to the Google Groups >> > "google-codejam" group. >> > To post to this group, send email to [email protected]. >> > To unsubscribe from this group, send email to >> > [email protected]. >> > For more options, visit this group >> > athttp://groups.google.com/group/google-code?hl=en. > > -- > You received this message because you are subscribed to the Google Groups > "google-codejam" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]. > For more options, visit this group at > http://groups.google.com/group/google-code?hl=en. > > -- You received this message because you are subscribed to the Google Groups "google-codejam" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/google-code?hl=en.
