Desert crossing problem
This puzzle and its many variants have been around for over a millenium and is known by many names “desert crossing problem”, “jeep problem” and “exploration problem” among others. The first known written version of the puzzle appeared in a collection of recreational math problems back in the 9th century (Wikipedia contributors 2022). Apparently puzzles have been used by masters and mentors to train the mind of the youngsters and inflame their intelect since the dawn of human civilization.
And so shall we.
Initially, I didn’t hold it in very high regard, thought I got the solution a couple of times only to realise later that these first attempts did not stand further scrutiny. At that instant I totally fell for it. And the resulting exertion led, in the end, to a high sense of satisfaction and pride when I came out of it.
Context & Rules
- 3 explorers are stranded in the middle of the desert
- They are 6 days march away from the nearest oasis
- At the starting base they have 21 units of supplies, enough to sustain themselves for 7 days
- Each explorer can carry at most 4 units of supplies.
- To not starve, each explorer must eat 1 unit of supplies every day (every 24 hours)
- The supplies can be left, collected, carried and consumed only in discrete amounts
- No help from others
- No other source of supplies but the oasis, where there are unlimited supplies
Clarifications about time
It took me a while to understand how the above rules define the time and the temporal relations between activities, so I share my conclusions here for your revision:
- Time spent in any other activity but travelling can be ignored (such as sleeping, eating, toileting, collecting…).
- In a sense, explorers’ motion is the clearest manifestation of the passage of time. Therefore to cover a distance of 1 day march, an entire day passes, and we know that the explorers must feed every single day.
- Let the above sink for a second, if the explorers are 1 day march from the oasis and have no supplies, at the end of the day they will reach the oasis and die, not dine. The very instant the explorer steps on the oasis, the clock ticks 1 day and she is dead of starvation. Eating and collecting supplies do not take time, but they cannot eat before reaching the oasis because they have no supplies, and they cannot collect supplies simply because they are not there yet.
How can they all survive?
Anything not stated above is at your own discretion! Stay creative.
Below I share the solution I found. Please let me know in the comments if you find any other or a flaw in mine.
Have fun and remember “No explorer is left behind”.