Путешественник собирается пересечь пустыню пешком. На это требуется шесть дней, но он может взять продовольствия и воды только на четыре дня. К счастью, местная деревня готова снабжать его носильщиками (каждый из которых обладает такой же грузоподъёмностью и потребляет такое же количество провизии, что и сам путешественник). Какое наименьшее количество носильщиков нужно путешественнику, чтобы пересечь пустыню? (Оставлять носильщиков на верную смерть в пустыне без еды и воды нельзя.)
Путешественнику потребуется только 2 носильщика. Первого из них надо отпустить домой на второй день, а второго — на третий день путешествия:
- Путешественник и два носильщика выходят из деревни, неся в совокупности запаса провианта на 12 дней.
- В течение первого дня они тратят трёхдневный запас, и однодневный запас остаётся первому носильщику, который сразу же отправляется домой. Таким образом, к началу второго дня у путешественника и второго носильщика остаётся провизии на 8 дней.
- В течение второго дня они тратят двухдневный запас провианта, и двухдневный запас остаётся второму носильщику, который сразу же отправляется домой. Таким образом, к началу третьего дня путешественник остаётся в одиночестве, но оставшегося запаса провизии ему хватит как раз на четырёхдневный переход через пустыню.