Puzzle: A company keeps two corkboards in the lobby on which they pin Polaroids of new employees on their first day. The pictures are ordered by start date of the employee, putting the most senior employee in the upper-left of the first corkboard, filling it up, and then starting on the second corkboard. When employees quit, their pictures are removed and everyone else’s pictures shift over.
You just started at this company and desperately want to see your picture move onto the first corkboard, where you will get prestige as an old-timer. You estimate that one person starts per week and one person quits per week. There are 150 pictures per board. Both boards were full when you started. How long will you have to wait on average to get onto the first board?
(This puzzle was originally written by Grue.)
First Hint: Right after you start you will be moving at the rate of one spot per week, since everyone quitting will be in front of you. When you get to the half-way point, you’ll be moving one spot every two weeks, since half the people quitting will have started after you did and won’t affect your position. When you get to the first spot, you won’t move at all.
Second Hint: It’s almost an integral number of years.
Answer: 208 weeks (four years)
Solution: If you read the two hints, then one way to get the solution is to guess. At your initial rate you’ll get there after 150 weeks (one spot per week and there are 150 spots on the second board). At the rate of your target spot (just getting onto the first board) it’ll take you 300 weeks. The answer has to be somewhere in between those two numbers. The second hint said that it’ll take an integral number of years, so that can only be 156, 208, or 260. If the rate change were linear, it would take 225 weeks. But it’s not linear, it moves faster at first and slower at the end, putting you at the half-way point earlier. The answer must be 208 weeks, since that’s slightly less than 225.
If you prefer a more rigorous solution, then you need to use calculus. The rate of change is proportional to your distance from the first position:
dP/dt = −a·P
where dP/dt is your change in position per week, a is a constant, and P is your position (0–300). P starts at 300, where the rate is −1 spot per week, so we can derive that a = 1/300.
dP/dt = −P/300
This is a differential equation, an equation where the change in something depends on that something’s value. Rewrite as:
(1/P) dP = (−1/300) dt
and integrate both sides to get:
ln |P| = −t/300 + ln |C|
(I write ln |C| instead of C to make the following math easier. It’s an unknown constant so it doesn’t matter.) Convert to:
ln |P| − ln |C| = −t/300
and simplify to:
ln |P/C| = −t/300
At t = 0 we know that P = 300, so we need C = 300 so that P/C = 1 and ln 1 = 0.
ln |P/300| = −t/300
Solve for t:
t = −300·ln |P/300|
In order to get onto the first board you need P = 150, so plug that in and get:
t = 207.9 weeks
or just a few hours short of four years.