bonanova 76 Report post Posted May 2, 2014 From the set of integers {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} I randomly choose an element, say 3. I subtact 3 from 10, getting 7. Now I have the set {1, 2, 3, 4, 5, 6, 7}. I choose another element at random, say 5. I subtract 5 from 7, getting 2. Now I have the set {1, 2}. I randomly choose one of these elements, say 1. I subtract 1 from 2, getting 1. Now I have the set {1}. I randomly choose one of these elements. It turns out to be 1. I subtract 1 from 1, getting 0. Now I have the empty set. Each step took away a nibble, leaving a smaller set. This example nibbled a set of 10 elements down to zero in four steps. Starting with a set of p elements, what is the expected number n of nibbles required to empty the set? Share this post Link to post Share on other sites

0 m00li 1 Report post Posted May 2, 2014 From {1,2,3,...k,...,p-1,p}, kth element can be chosen with 1/p probability. If k is chosen, then p-k elements remain to be nibbled. So expected number of nibbles in this case become = 1 + expected number of nibbling p-k elements. (here 1 is added as 1 step is consumed in selecting the kth element). Let the number required to nibble p elements be denoted by N_{p} N_{p} = (1/p)*(1+N_{p-1}) +(1/p)*(1+N_{p-2})..... (1/p)*(1+N_{1}) + (1/p)*(1+N_{0}) Clearly N_{0 }and N_{1 }are 0 and 1, respectively. Hence, N_{p }= (1/p)*(p+N_{p-1}+N_{p-2}+...N_{1}) = 1+ (1/p)(N_{p-1}+N_{p-2}+...N_{1) }= 1 + (1/p)(1+(1/(p-1))(N_{p-2}+...N_{1}) + (N_{p-2}+...N_{1})) = 1 + 1/p + (1/(p-1))(N_{p-2}+...N_{1}) Hence, N_{p} = 1/p+1/(p-1)+1/(p-2)+...+1/3+1/2+1 Share this post Link to post Share on other sites

From the set of integers {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} I randomly choose an element, say 3. I subtact 3 from 10, getting 7.

Now I have the set {1, 2, 3, 4, 5, 6, 7}. I choose another element at random, say 5. I subtract 5 from 7, getting 2.

Now I have the set {1, 2}. I randomly choose one of these elements, say 1. I subtract 1 from 2, getting 1.

Now I have the set {1}. I randomly choose one of these elements. It turns out to be 1. I subtract 1 from 1, getting 0.

Now I have the empty set.

Each step took away a nibble, leaving a smaller set.

This example nibbled a set of 10 elements down to zero in four steps.

Starting with a set of

elements, what is the expected numberpof nibbles required to empty the set?n## Share this post

## Link to post

## Share on other sites