Summing some random numbers from 1 to n

We had a fun discussion at dinner about a maths problem that Sid knew: given the numbers 1 to n, on average how many of them do we need to pick at random so that the sum is greater than n. The answer is that as n gets large the expected number of draws tends to ‘e’ (i.e. 2.718…).

We couldn’t work this out for ourselves at the table but fortunately there was a mathematician near by. James typed up his proof :It tends to ‘e’. (The proof makes use of Markov Chains which are not covered until the second year course Mathematical Methods for Computer Science.)