My 12 year old nephew asked me a hypothetical question that asks if I would be willing to take a bet about puzzling a 1000 piece blank jigzaw puzzle in a month's time. If I succeed I win a large sum of money, if I lose I have to pay the sum. For example 1000000 Icelandic krona (isk).
That got me thinking about how the best way would be to achieve it and if it was realistically possible within a month's time.
The method I propose is a greedy one. You simply take one piece at a time, try it with all the pieces you have successfully put together, if it does not fit you put it in a 'does not fit pile', and then repeat until finished.
If we say that each piece takes 5 seconds + 1 second for each piece in the successfully placed pieces then how long would it take?
Best Answer
Suppose we find the pieces in reading order $-$ we start in the top left corner, move along that row, then drop a row and continue, and so on for $1000$ iterations.
We might have to try all $1000$ pieces to find the top left corner.
For the next piece there are only $999$ left to try. The worst case scenario is we have to try all of them. So the running total is $1000+999$ tries.
For the next piece there are only $998$ left to try. The worst case scenario is we have to try all of them. S0 the running total is $1000+999+ 998$ tries.
And so on so forth we might have to try $1000+999 + 998 + \ldots + 2 + 1$ times.
Everyone knows the sum of the numbers from $1$ to $1000$ is $500,500$ tries.
$1$ try per $5$ seconds means $720$ tries per hour.
So it could take up to $500500/720 = 695$ hours to brute-force the jigsaw.
A 30-day month is 720 hours long. So you would expect to do the jigsaw in that time. But you are not allowed to sleep or do anything else for that month.
Keep in mind this is an upper estimate. The average time it would take is exactly half the upper estimate: It takes $500$ tries on average to find the first piece and so on. . . So it's 50/50 whether you could brute force the jigsaw with 12 hours work per day.