You have how much left?

You are out shopping one day with $N, and you find an item whose price has a random value between $0 and $N. You buy as many of these items as you can with your $N. What is the expected value of the money you have left over? (You may assume that $N is large compared to a penny, so that the distribution of prices is essentially continuous.)

Express your answer in terms of N, to two decimal places.

0.19N 0.18N 0.17N 0.20N 0.16N

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

2 solutions

Denton Young
Jun 6, 2017

If the item costs between N / 2 N/2 and N N dollars, then you can buy only one item. These extremes will produce remainders of N / 2 N/2 and 0 0 , respectively. The average amount of money left over in this region, which has length N ( 1 1 / 2 ) = N / 2 N(1 - 1/2) = N/2 , is therefore N / 4. N/4.

Likewise, if the item costs between N / 3 N/3 and N / 2 N/2 dollars, then you can buy only two items. These extremes will produce remainders of N / 3 N/3 and 0 0 , respectively. The average amount of money left over in this region, which has length N ( 1 / 2 1 / 3 ) = N / 6 N(1/2 - 1/3) = N/6 , is therefore N / 6 N/6 .

Continuing in this manner, we see that if the item costs between N / ( n + 1 ) N/(n + 1) and N / n N/n , then you can buy only n n items. These extremes will produce remainders of N / ( n + 1 ) N/(n+ 1) and 0 0 , respectively. The average amount of money left over in this region, which has length N ( 1 / n 1 / ( n + 1 ) ) = N / n ( n + 1 ) N(1/n - 1/(n + 1)) = N/n(n + 1) , is therefore N / 2 ( n + 1 ) N/2(n + 1) .

The expected amount, M M , of money left over is therefore:

M = n = 0 ( ( 1 / n 1 / ( n + 1 ) ) × ( N / ( 2 ( n + 1 ) ) ) ) M = \displaystyle\sum_{n=0}^\infty((1/n - 1/(n+1)) \times (N/(2(n+1))))

which equals N × ( 1 ( π 2 / 12 ) ) = 0.18 N N \times (1 - (\pi^2/12)) = 0.18N

Great problem! Thanks for posting it. :)

Brian Charlesworth - 4 years ago

Log in to reply

Thank you. I'm guessing you're the first person to get the correct answer :)

Denton Young - 4 years ago

Log in to reply

Haha Yes, guilty as charged. :)

Brian Charlesworth - 4 years ago

Nice problem and solution.

Hana Wehbi - 4 years ago

Amazing question. I guessed that the solution must be related to pi, but I can't find 3.14 anywhere :(

William Nathanael Supriadi - 3 years, 12 months ago
Mark Hennings
Jun 13, 2017

The cost of the item is a random variable X X that is uniformly distributed over ( 0 , N ) (0,N) , and we want the expectation of the change random variable C = N N X X C \; = \; N - \left\lfloor \tfrac{N}{X}\right\rfloor X Thus E [ C ] = 1 N 0 N ( N N x x ) d x = N 1 N j = 1 N j + 1 N j N x x d x = N 1 N j = 1 j N j + 1 N j x d x = N 1 2 N j = 1 j ( N 2 j 2 N 2 ( j + 1 ) 2 ) = N N 2 j = 1 ( 1 j 1 j + 1 + 1 ( j + 1 ) 2 ) = N 1 2 N ( 1 + ( ζ ( 2 ) 1 ) ) = ( 1 1 12 π 2 ) N 0.1775 N \begin{aligned} \mathbb{E}[C] & = \frac{1}{N}\int_0^N \left(N - \left\lfloor \tfrac{N}{x}\right\rfloor x\right)\,dx \; = \; N - \tfrac{1}{N} \sum_{j=1}^\infty \int_{\frac{N}{j+1}}^{\frac{N}{j}} \left\lfloor \tfrac{N}{x}\right\rfloor x\,dx \\ & = N - \frac{1}{N} \sum_{j=1}^\infty j \int_{\frac{N}{j+1}}^{\frac{N}{j}} x\,dx \; = \; N - \frac{1}{2N} \sum_{j=1}^\infty j\left(\frac{N^2}{j^2} - \frac{N^2}{(j+1)^2}\right) \\ & = N - \frac{N}{2}\sum_{j=1}^\infty\left(\frac{1}{j} - \frac{1}{j+1} + \frac{1}{(j+1)^2}\right) \; = \; N - \tfrac12N\big(1 + (\zeta(2)-1)\big) \\ & = \big(1- \frac{1}{12}\pi^2\big)N \; \approx \; 0.1775N \end{aligned} making the answer 0.178 N \boxed{0.178N} .

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...