BrainDen.com - Brain Teasers

## Question

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?

## Recommended Posts

• 0

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 Np

Np = (1/p)*(1+Np-1) +(1/p)*(1+Np-2)..... (1/p)*(1+N1) + (1/p)*(1+N0)

Clearly N0 and N1 are 0 and 1, respectively.

Hence,

Np = (1/p)*(p+Np-1+Np-2+...N1) = 1+ (1/p)(Np-1+Np-2+...N1) = 1 + (1/p)(1+(1/(p-1))(Np-2+...N1) + (Np-2+...N1)) = 1 + 1/p + (1/(p-1))(Np-2+...N1)

Hence, Np = 1/p+1/(p-1)+1/(p-2)+...+1/3+1/2+1

## Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account. ×   Pasted as rich text.   Paste as plain text instead

Only 75 emoji are allowed.

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.