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.
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.
Great problem! Thanks for posting it. :)
Log in to reply
Thank you. I'm guessing you're the first person to get the correct answer :)
Nice problem and solution.
Amazing question. I guessed that the solution must be related to pi, but I can't find 3.14 anywhere :(
The cost of the item is a random variable X that is uniformly distributed over ( 0 , N ) , and we want the expectation of the change random variable C = N − ⌊ X N ⌋ X Thus E [ C ] = N 1 ∫ 0 N ( N − ⌊ x N ⌋ x ) d x = N − N 1 j = 1 ∑ ∞ ∫ j + 1 N j N ⌊ x N ⌋ x d x = N − N 1 j = 1 ∑ ∞ j ∫ j + 1 N j N x d x = N − 2 N 1 j = 1 ∑ ∞ j ( j 2 N 2 − ( j + 1 ) 2 N 2 ) = N − 2 N j = 1 ∑ ∞ ( j 1 − j + 1 1 + ( j + 1 ) 2 1 ) = N − 2 1 N ( 1 + ( ζ ( 2 ) − 1 ) ) = ( 1 − 1 2 1 π 2 ) N ≈ 0 . 1 7 7 5 N making the answer 0 . 1 7 8 N .
Problem Loading...
Note Loading...
Set Loading...
If the item costs between N / 2 and N dollars, then you can buy only one item. These extremes will produce remainders of N / 2 and 0 , respectively. The average amount of money left over in this region, which has length N ( 1 − 1 / 2 ) = N / 2 , is therefore N / 4 .
Likewise, if the item costs between N / 3 and N / 2 dollars, then you can buy only two items. These extremes will produce remainders of N / 3 and 0 , respectively. The average amount of money left over in this region, which has length N ( 1 / 2 − 1 / 3 ) = N / 6 , is therefore N / 6 .
Continuing in this manner, we see that if the item costs between N / ( n + 1 ) and N / n , then you can buy only n items. These extremes will produce remainders of N / ( n + 1 ) and 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 ) , is therefore N / 2 ( n + 1 ) .
The expected amount, M , of money left over is therefore:
M = n = 0 ∑ ∞ ( ( 1 / n − 1 / ( n + 1 ) ) × ( N / ( 2 ( n + 1 ) ) ) )
which equals N × ( 1 − ( π 2 / 1 2 ) ) = 0 . 1 8 N