My replies inline On 9 May 2011 19:33, Eagle <[email protected]> wrote: > As I understand the probability, it goes something like this- If > you toss a coin 100 times, it is 'expected' (actual result may be > different) that 50 times you will get 'Heads' & 50 times 'Tails'. In > present problem also, you have to answer the 'expected' number of hits > by Goro to sort the numbers. This is also confirmed by the explanation > given for a case at the end of the problem statement D.
Your understanding of expected value is correct. Note that if p(n) is the probability to get n heads in 100 tosses, then the expected number of heads is 0.p(0) + 1.p(1) + 2.p(2) + ... + 99.p(99) + 100.p(100). This is how the expected value is calculated. If you put actual numbers here, you will see that this comes to 50. > > If three numbers are to be sorted, then the 'chance' or > probability of all three falling in correct place is 1/6. This means > that on an 'average', Goro will have to hit the table 6 times to sort > those numbers. But, there is a better strategy, and this number of > hits can be reduced. It goes like this- This is true if the result is either success or failure. However, you can have a partial success where 1 of the elements come to the right place and you can change the strategy accordingly. If Goro were forced to keep hitting the same 3 tiles till all were in place, then you are right - its avg 6 times. But that's not the case. > The chance/probability of getting exactly one number in correct > position and the remaining two in wrong positions is 3/6 or 1/2. So, > on an 'average' if Goro makes two hits, he can 'expect' that one > number will be sorted. The hit counter is 2 by now. After this, he > holds the sorted number, and his requirement is to sort the remaining > two numbers. For these two numbers, as explained in the problem > statement itself, the probability of sorting is 1/2, and on 'average' > two hits would be required. The hit counter now becomes 2 + 2 = 4. > Mathematically, P(first event) = 1/2 and P(second event) = 1/2; so, > combined probability is 1/2 x 1/2 = 1/4, and reciprocal of that is 4, > which is average hits (the required answer). You say that probability is 1/2 for getting one number correct. What happens to the other 1/2? Is it always a failure and repeat from start? No. If it were so, then its true that 4 is the average hits. But, there is a possibility that you can get all 3 in place and you don't have to proceed any further. That needs to be put into the calculation too. > > Goro can use one more strategy, which again gives same answer. If > [3, 1, 2] are to be sorted, Goro will hold '3' and make on an > 'average' two hits to bring '2' in correct position. Then, he would > release '3', hold the sorted '2', and make two more 'average' hits to > bring '1' & '3' in their respective correct positions. > This strategy gives average hits of 4 (You are doing for 2 numbers twice). But, since the other strategy gives average hits of 3, its better to not choose this strategy. > @Bharath and @Pedro Osorio, I hope my explanation is not > frustrating to understand. If we come from different backgrounds, it > is normal that there is communication gap. > > Eagle > > > On May 9, 12:07 pm, Bharath Raghavendran <[email protected]> wrote: >> 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 >> > 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.
