ปัญหารถจี๊ป [ 1 ^{] ปัญหา}การข้ามทะเลทราย^{[ 2 ]}หรือปัญหาการสำรวจ^{[ 3 ]}เป็นปัญหาทางคณิตศาสตร์ที่รถจี๊ป ต้องเดินทางให้ ^ได้ ระยะทางสูงสุดในทะเลทรายด้วยปริมาณเชื้อเพลิงที่กำหนด รถจี๊ปสามารถบรรทุกเชื้อเพลิงได้ในปริมาณที่จำกัดเท่านั้น แต่สามารถทิ้งเชื้อเพลิงและรับเชื้อเพลิงได้ที่จุดทิ้งเชื้อเพลิงใดๆ ในทะเลทราย

ปัญหาดังกล่าวปรากฏครั้งแรกในหนังสือรวมปัญหา Propositiones ad Acuendos Juvenes ( ปัญหาเพื่อพัฒนาเยาวชน ) ในศตวรรษที่ 9 ซึ่งเชื่อกันว่าเป็นผลงานของAlcuinโดยปริศนานั้นเกี่ยวกับอูฐที่เดินทางและกินเมล็ดพืช^{[ 4 ]} หนังสือDe viribus quantitatis (ประมาณปี 1500) ของLuca Pacioli ก็ได้กล่าวถึงปัญหานี้เช่นกัน NJ Fineได้นำเสนอวิธีแก้ปัญหาที่ทันสมัยในปี 1947 ^{[ 1 ]}

มี เชื้อเพลิงจำนวน nหน่วยเก็บไว้ที่ฐานคงที่ รถจี๊ปสามารถบรรทุกเชื้อเพลิงได้มากที่สุด 1 หน่วยในเวลาใดก็ตาม และสามารถเดินทางได้ 1 หน่วยระยะทางต่อเชื้อเพลิง 1 หน่วย (โดยสมมติว่าอัตราการสิ้นเปลืองเชื้อเพลิงของรถจี๊ปคงที่) ในระหว่างการเดินทาง รถจี๊ปอาจทิ้งเชื้อเพลิงจำนวนเท่าใดก็ได้ที่บรรทุกไว้ที่จุดทิ้งเชื้อเพลิง หรืออาจเติมเชื้อเพลิงจำนวนเท่าใดก็ได้ที่เหลืออยู่ที่จุดทิ้งเชื้อเพลิงในการเดินทางครั้งก่อน ตราบใดที่ปริมาณเชื้อเพลิงที่บรรทุกไม่เกิน 1 หน่วย ปัญหาดังกล่าวมีสองรูปแบบ:

• การสำรวจทะเลทราย  – รถจี๊ปต้องกลับไปยังฐานที่ตั้งเมื่อสิ้นสุดการเดินทางทุกครั้ง
• การเดินทางข้ามทะเลทราย  – รถจี๊ปต้องกลับไปยังฐานที่มั่นเมื่อสิ้นสุดการเดินทางทุกครั้ง ยกเว้นการเดินทางครั้งสุดท้าย ซึ่งรถจี๊ปจะเดินทางได้ไกลที่สุดเท่าที่จะทำได้ก่อนที่น้ำมันจะหมด

ไม่ว่าในกรณีใด เป้าหมายคือการเพิ่มระยะทางที่รถจี๊ปวิ่งได้มากที่สุดในการเดินทางครั้งสุดท้าย หรืออีกทางหนึ่ง เป้าหมายอาจเป็นการหาปริมาณเชื้อเพลิงที่น้อยที่สุดที่จำเป็นในการเดินทางครั้งสุดท้ายในระยะทางที่กำหนด

ในปัญหาคลาสสิก เชื้อเพลิงในรถจี๊ปและที่สถานีเติมเชื้อเพลิงถือเป็น ปริมาณ ต่อเนื่องมีการเสนอรูปแบบที่ซับซ้อนกว่าของปัญหานี้ โดยที่เชื้อเพลิงสามารถทิ้งหรือเก็บรวบรวมได้ในปริมาณที่ไม่ต่อเนื่องเท่านั้น^{[ 5 ]}

กลยุทธ์ที่ทำให้ได้ระยะทางเดินทางสูงสุดในทริปสุดท้ายสำหรับตัวเลือก "สำรวจทะเลทราย" มีดังนี้:

• รถจี๊ปคันนี้วิ่งได้nเที่ยว โดยในแต่ละเที่ยวจะเริ่มต้นจากฐานด้วยน้ำมัน 1 หน่วย
• ในการเดินทางครั้งแรก รถจี๊ปเดินทางเป็นระยะทาง 1/(2 n ) หน่วย และทิ้งเชื้อเพลิงไว้ที่จุดทิ้งเชื้อเพลิงจำนวน ( n  − 1)/ n หน่วย รถจี๊ปยังมีเชื้อเพลิงเหลืออยู่ 1/(2 n ) หน่วย ซึ่งเพียงพอที่จะกลับไปยังฐานได้
• ในการเดินทางครั้งถัดไปn  − 1 ครั้ง รถจี๊ปจะเก็บเชื้อเพลิง 1/(2 n ) หน่วยจากคลังเชื้อเพลิงแห่งแรกนี้ระหว่างขาไป เพื่อให้รถจี๊ปออกจากคลังเชื้อเพลิงโดยมีเชื้อเพลิง 1 หน่วย และในระหว่างขากลับ รถจี๊ปจะเก็บเชื้อเพลิง 1/(2 n ) หน่วยจากคลังเชื้อเพลิงแห่งแรกนี้เช่นกัน ซึ่งเป็นปริมาณเชื้อเพลิงที่เพียงพอสำหรับการกลับไปยังฐาน
• ในการเดินทางครั้งที่สอง รถจี๊ปเดินทางไปยังสถานีเติมน้ำมันแห่งแรกและเติมน้ำมัน จากนั้นเดินทางเป็นระยะทาง 1/(2 n  − 2) หน่วย และทิ้ง น้ำมัน ไว้ ( n  − 2)/( n − 1) หน่วยที่สถานีเติมน้ำมันแห่งที่สอง รถจี๊ปยังมีน้ำมันเหลืออยู่ 1/(2 n  − 2) หน่วย ซึ่งเพียงพอที่จะกลับไปยังสถานีเติมน้ำมันแห่งแรก ที่นี่รถจี๊ปจะเก็บน้ำมันได้ 1/(2 n ) หน่วย ซึ่งเพียงพอที่จะกลับไปยังฐาน
• ในการเดินทางครั้งต่อๆ ไปn  − 2 ครั้ง รถจี๊ปจะเก็บ เชื้อเพลิง 1/(2 n − 2) หน่วยจากคลังเชื้อเพลิงที่สองระหว่างทางออกไป ทำให้เมื่อออกจากคลังเชื้อเพลิงจะมีเชื้อเพลิงอยู่ 1 หน่วย และในระหว่างทางกลับ รถจี๊ปจะเก็บเชื้อเพลิง 1/(2 n  − 2) หน่วยจากคลังเชื้อเพลิงที่สองเช่นกัน ซึ่งเป็นปริมาณเชื้อเพลิงที่เพียงพอสำหรับการเดินทางกลับไปยังคลังเชื้อเพลิงแรก
• รถจี๊ปจะวิ่งต่อไปในลักษณะนี้ โดยในการเดินทางครั้งที่ kมันจะสร้างจุดเติมน้ำมันใหม่ ที่จุด k  ซึ่งอยู่ห่างจากจุดเติมน้ำมันก่อนหน้าเป็นระยะ 1/(2n −  2k + 2) หน่วย และทิ้งน้ำมันไว้ที่นั่นจำนวน ( n  −  k )/( n  −  k  + 1) หน่วย ในการเดินทางครั้งต่อๆ ไปอีกn  −  kครั้ง มันจะเก็บน้ำมันจำนวน 1/(2n −  2k +  2) หน่วยจาก จุดเติมน้ำมันที่จุด kระหว่างทางขาไป และเก็บอีก 1/(2n −  2k +  2) หน่วยระหว่างทางขากลับ

เมื่อรถจี๊ปเริ่มการเดินทางครั้งสุดท้าย จะมี จุดเติมน้ำมัน n  − 1 จุด จุดที่อยู่ไกลที่สุดมีน้ำมัน 1/2 หน่วย จุดที่อยู่ถัดไปมีน้ำมัน 1/3 หน่วย และเป็นเช่นนี้เรื่อยไป จนกระทั่งจุดที่ใกล้ที่สุดเหลือน้ำมันเพียง 1/ nหน่วย เมื่อรวมกับน้ำมัน 1 หน่วยที่เริ่มต้นจากฐานแล้ว รถจี๊ปจะสามารถเดินทางได้ระยะทางไปกลับรวมทั้งหมดเท่ากับ...

${\displaystyle 1+{\frac {1}{2}}+{\frac {1}{3}}+\cdots +{\frac {1}{n}}=\sum _{k=1}^{n}{\frac {1}{k}}\equiv 2\times \mathrm {explore} (n)}$

หน่วยในการเดินทางครั้งสุดท้าย (ระยะทางสูงสุดที่เดินทางเข้าไปในทะเลทรายคือครึ่งหนึ่งของจำนวนนี้) ^{[ 3 ]}มันเก็บเชื้อเพลิงที่เหลือครึ่งหนึ่งจากแต่ละจุดทิ้งเชื้อเพลิงระหว่างทาง ซึ่งจะเติมถังเชื้อเพลิง หลังจากออกจากจุดทิ้งเชื้อเพลิงที่ไกลที่สุด มันจะเดินทางเข้าไปในทะเลทรายอีก 1/2 หน่วย แล้วจึงกลับไปยังจุดทิ้งเชื้อเพลิงที่ไกลที่สุด มันเก็บเชื้อเพลิงที่เหลือจากแต่ละจุดทิ้งเชื้อเพลิงระหว่างทางกลับ ซึ่งมีปริมาณเพียงพอที่จะไปถึงจุดทิ้งเชื้อเพลิงถัดไป หรือในขั้นตอนสุดท้าย เพื่อกลับไปยังฐาน

ระยะทางที่เดินทางในการเดินทางครั้งสุดท้ายคือเลขฮาร์มอนิกที่n , Hn เนื่องจากเลขฮาร์มอนิกไม่มี _{ขอบเขต}จำกัด จึงเป็นไปได้ที่จะเดินทางเกินระยะทางที่กำหนดไว้ในการเดินทางครั้งสุดท้าย ตราบใดที่มีเชื้อเพลิงเพียงพอที่ฐาน อย่างไรก็ตาม ปริมาณเชื้อเพลิงที่ต้องการและจำนวนครั้งในการเติมเชื้อเพลิงจะเพิ่มขึ้นแบบทวีคูณตามระยะทางที่จะต้องเดินทาง

วิธีแก้ปัญหา "การข้ามทะเลทราย" นั้นใช้กลยุทธ์ที่คล้ายกัน ยกเว้นว่าตอนนี้ไม่จำเป็นต้องเติมน้ำมันระหว่างทางกลับในเที่ยวสุดท้าย ดังนั้นในเที่ยวที่kรถจี๊ปจะสร้างจุดเติมน้ำมันใหม่ ที่ kในระยะทาง 1/(2n −  2k +  1) หน่วยจากจุดเติมน้ำมันก่อนหน้า และทิ้งน้ำมันไว้ที่นั่นจำนวน (2n −  2k −  1)/(2n −  2k +  1) หน่วย ในแต่ละเที่ยวถัดไปn  −  k  − 1 เที่ยว มันจะเติมน้ำมัน 1/( 2n  − 2k  + 1) หน่วยจาก จุดเติมน้ำมัน ที่ kระหว่างทางไป และอีก 1/(2n −  2k +  1) หน่วยระหว่างทางกลับ

เมื่อรถจี๊ปเริ่มการเดินทางครั้งสุดท้าย จะมี จุดเติมน้ำมัน n  − 1 จุด จุดที่อยู่ไกลที่สุดมีน้ำมัน 1/3 หน่วย จุดที่อยู่ถัดไปมีน้ำมัน 1/5 หน่วย และเป็นเช่นนี้เรื่อยไป จนกระทั่งจุดที่ใกล้ที่สุดเหลือน้ำมันเพียง 1/(2 n  − 1) หน่วย เมื่อรวมกับน้ำมัน 1 หน่วยที่เริ่มต้นจากฐาน รถจี๊ปจะสามารถเดินทางได้เป็นระยะทางรวมทั้งหมด

${\displaystyle 1+{\frac {1}{3}}+{\frac {1}{5}}+\cdots +{\frac {1}{2n-1}}=\sum _{k=1}^{n}{\frac {1}{2k-1}}=H_{2n-1}-{\frac {1}{2}}H_{n-1}\equiv \mathrm {cross} (n)}$

หน่วยในการเดินทางครั้งสุดท้าย^{[ 1 ] [ 3 ]}มันเก็บเชื้อเพลิงที่เหลือทั้งหมดที่จุดทิ้งเชื้อเพลิงแต่ละแห่งระหว่างทาง ซึ่งจะเติมถังเชื้อเพลิง หลังจากออกจากจุดทิ้งเชื้อเพลิงที่ไกลที่สุด มันจะเดินทางต่อไปอีก 1 หน่วย

เนื่องจาก

${\displaystyle \mathrm {cross} (n)=\sum _{k=1}^{n}{\frac {1}{2k-1}}>\sum _{k=1}^{n}{\frac {1}{2k}}={\frac {1}{2}}H_{n}=\mathrm {explore} (n)}$,

ในทางทฤษฎีแล้ว เป็นไปได้ที่จะข้ามทะเลทรายขนาดใดก็ได้ หากมีเชื้อเพลิงเพียงพอที่ฐาน เช่นเดียวกับที่กล่าวมาแล้ว ปริมาณเชื้อเพลิงที่ต้องการและจำนวนจุดเติมเชื้อเพลิงจะเพิ่มขึ้นแบบทวีคูณตามระยะทางที่จะเดินทาง

โดยสรุป ระยะทางสูงสุดที่รถจี๊ป (ที่มีความจุเชื้อเพลิงสำหรับระยะทาง 1 หน่วย ณ เวลาใดเวลาหนึ่ง) สามารถวิ่งได้ในnเที่ยว (โดยมี การเติมเชื้อเพลิงกลางทาง n-1 ครั้ง และใช้ เชื้อเพลิง ทั้งหมดn หน่วย) คือ

• ${\displaystyle \mathrm {explore} (n)={\frac {1}{2}}H_{n}={\frac {1}{2}}+{\frac {1}{4}}+{\frac {1}{6}}+\cdots +{\frac {1}{2n}}}$สำหรับการสำรวจทะเลทราย ซึ่งรถจี๊ปจะต้องกลับไปยังฐานที่มั่นเมื่อสิ้นสุดการเดินทางทุกครั้ง
• ${\displaystyle \mathrm {cross} (n)=H_{2n-1}-{\frac {1}{2}}H_{n-1}=1+{\frac {1}{3}}+{\frac {1}{5}}+\cdots +{\frac {1}{2n-1}}}$สำหรับการเดินทางข้ามทะเลทราย ซึ่งรถจี๊ปจะต้องกลับไปยังฐานที่มั่นเมื่อสิ้นสุดการเดินทางทุกครั้ง ยกเว้นการเดินทางครั้งสุดท้าย ที่รถจี๊ปจะเดินทางได้ไกลที่สุดเท่าที่จะทำได้ก่อนที่น้ำมันจะหมด

นี่คือเลขฮาร์มอนิกที่ n${\displaystyle H_{n}=1+{\frac {1}{2}}+{\frac {1}{3}}+\cdots +{\frac {1}{n}}}$

จำนวนหน่วยเชื้อเพลิงที่มีอยู่ ณ ฐานไม่จำเป็นต้องเป็นจำนวนเต็ม ในกรณีทั่วไป ระยะทางสูงสุดที่สามารถเดินทางได้สำหรับปัญหา "สำรวจทะเลทราย" โดยใช้ เชื้อเพลิง nหน่วย คือ

${\displaystyle \mathrm {สำรวจ} (n)=\int _{0}^{n}{\frac {\mathrm {d} f}{2\lceil nf\rceil }}}$

โดยจุดเติมเชื้อเพลิงจุดแรกอยู่ห่างจากฐานเริ่มต้นเป็นระยะทาง หน่วย จุดที่สองอยู่ห่างจากจุดเติมเชื้อเพลิงจุดแรกเป็นระยะทาง หน่วย จุดที่สามอยู่ห่างจากจุดเติมเชื้อเพลิงจุดที่สองเป็นระยะ ทาง หน่วย และเป็นเช่นนี้เรื่อยไป นี่คือส่วนที่เป็นเศษส่วนของn${\displaystyle \{n\}/(2\lceil n\rceil )}$${\displaystyle 1/(2\lceil n\rceil -2)}$${\displaystyle 1/(2\lceil n\rceil -4)}$${\displaystyle \{n\}=n-\lfloor n\rfloor }$

ระยะทางสูงสุดที่สามารถเดินทางได้ในปัญหา "ข้ามทะเลทราย" โดยใช้ เชื้อเพลิง nหน่วย คือ

${\displaystyle \mathrm {cross} (n)=\int _{0}^{n}{\frac {\mathrm {d} f}{2\lceil nf\rceil -1}}}$

โดยจุดเติมเชื้อเพลิงจุดแรกอยู่ห่างจากฐานเริ่มต้นเป็นระยะทาง หน่วย จุดที่สองอยู่ห่างจากจุดเติมเชื้อเพลิงจุดแรกเป็นระยะทาง หน่วย จุดที่สามอยู่ห่างจากจุดเติมเชื้อเพลิงจุดที่สองเป็นระยะ ทาง หน่วย และเป็นเช่นนี้เรื่อยไป นี่คือส่วนที่เป็นเศษส่วนของn${\displaystyle \{n\}/(2\lceil n\rceil -1)}$${\displaystyle 1/(2\lceil n\rceil -3)}$${\displaystyle 1/(2\lceil n\rceil -5)}$${\displaystyle \{n\}=n-\lfloor n\rfloor }$

ลำดับการเดินทางของรถจี๊ปไม่ได้ตายตัว ตัวอย่างเช่น ในเวอร์ชัน "การสำรวจทะเลทราย" ของปัญหา รถจี๊ปอาจวิ่งไป-กลับระหว่างฐานและจุดเติมน้ำมันแห่งแรกn − 1 ครั้ง โดยทิ้งน้ำมันไว้ที่จุดเติมน้ำมันแต่ละครั้งจำนวน ( n − 1) / nหน่วย จากนั้นจึงวิ่งเที่ยวเดียวไปยังจุดเติมน้ำมันแห่งแรกเป็นครั้งที่ n ทำให้ไปถึงที่นั่นโดยมีน้ำมันเหลืออยู่ทั้งหมด( n − 1) + 1/(2n )หน่วยน้ำมัน1/(2n )หน่วยจะถูกเก็บไว้สำหรับการเดินทางกลับฐานในตอนท้าย และน้ำมันอีกn − 1หน่วยจะถูกใช้ในการขนส่งน้ำมันระหว่างจุดเติมน้ำมันแห่งแรกและแห่งที่สอง โดยใช้ การวิ่งไป-กลับ n − 2ครั้ง จากนั้นจึงวิ่งเที่ยวเดียวไปยังจุดเติมน้ำมันแห่งที่สองเป็นครั้งที่ ( n − 1) และเป็นเช่นนี้เรื่อยไป

ปัญหาดังกล่าวสามารถนำไปประยุกต์ใช้ได้จริงในสถานการณ์สงคราม โดยเฉพาะอย่างยิ่งในเรื่องประสิทธิภาพ การใช้เชื้อเพลิง ในบริบทของการทิ้งระเบิดญี่ปุ่นในสงครามโลกครั้งที่ 2โดย เครื่องบิน B-29โรเบิร์ต แม็คนามารากล่าวในภาพยนตร์เรื่องThe Fog of Warว่าการเข้าใจปัญหาประสิทธิภาพการใช้เชื้อเพลิงที่เกิดจากการต้องขนส่งเชื้อเพลิงไปยังฐานทัพแนวหน้าเป็นเหตุผลหลักที่ทำให้กลยุทธ์การโจมตีทางอากาศจากแผ่นดินใหญ่ของจีนถูกยกเลิกและหันมาใช้กลยุทธ์การยึดเกาะ แทน ^{[ 6 ]}

เราต้องบินเครื่องบินเหล่านั้นจากฐานทัพในแคนซัสไปยังอินเดีย จากนั้นเราต้องบินขนเชื้อเพลิงข้ามเทือกเขาไปยังประเทศจีน [...] เราได้รับมอบหมายให้ใช้ เครื่องบิน B-29 เหล่านี้ —เนื่องจากไม่มีเครื่องบินเติมเชื้อเพลิงอยู่ที่นั่น เราต้องเติมเชื้อเพลิงให้เต็ม บินจากอินเดียไปยังเฉิงตูขนถ่ายเชื้อเพลิง บินกลับไปยังอินเดีย ทำภารกิจให้เพียงพอเพื่อสะสมเชื้อเพลิงในเฉิงตู บินไปยังยาวาตะประเทศญี่ปุ่นทิ้งระเบิดโรงงานเหล็กและกลับไปยังอินเดีย

เราได้รับการฝึกฝนน้อยมากเกี่ยวกับปัญหาการเพิ่มประสิทธิภาพ [เชื้อเพลิง] ให้สูงสุด ที่จริงแล้วเราพบว่าในการนำเครื่องบิน B-29 บางลำกลับมา แทนที่จะขนถ่ายเชื้อเพลิง พวกเขาต้องรับเชื้อเพลิงนั้นไว้เอง พูดให้สั้นก็คือ มันไม่คุ้มค่าเลย และเป็นเลอเมย์นี่เองที่ได้ข้อสรุปนั้น และนำเหล่าผู้บัญชาการย้ายทุกอย่างไปที่หมู่เกาะมาเรียนาสซึ่งสร้างความเสียหายอย่างหนักให้กับญี่ปุ่น

( ภารกิจทิ้งระเบิดปรมาณูในช่วงปลายสงครามโลกครั้งที่สอง ดำเนินการโดยใช้เครื่องบินทิ้งระเบิด B-29 Superfortressจากเกาะทิเนียน ใน มหาสมุทรแปซิฟิกซึ่งอยู่ในหมู่เกาะมาเรียนาสเหนือ )

• โปรดอ่านปฏิบัติการแบล็กบัคเพื่อความเข้าใจที่ดียิ่งขึ้นเกี่ยวกับการประยุกต์ใช้แนวคิดเหล่านี้ ในภารกิจเหล่านี้ซึ่งดำเนินการในช่วงสงครามฟอล์คแลนด์กองทัพอากาศอังกฤษได้ใช้การเติมเชื้อเพลิงกลางอากาศโดยการจัดเครื่องบินเติมเชื้อเพลิงเพื่อช่วยให้เครื่องบิน ทิ้งระเบิด วัลแคนซึ่งประจำการอยู่ที่เกาะแอสเซนชันสามารถทิ้งระเบิดเป้าหมายในหมู่เกาะฟอล์คแลนด์ได้
• อนุกรมฮาร์มอนิก (คณิตศาสตร์)
• การหาค่าเหมาะสมที่สุด (คณิตศาสตร์)