Jeep problem
জিপ সমস্যা, মরুভূমি পারাপারের সমস্যা বা অন্বেষণ সমস্যা হল একটি গাণিতিক সমস্যা যেখানে একটি জিপকে অবশ্যই একটি নির্দিষ্ট পরিমাণ জ্বালানী নিয়ে মরুভূমিতে ভ্রমণ করতে পারে এমন দূরত্ব সর্বাধিক করতে হবে। জিপ শুধুমাত্র একটি নির্দিষ্ট এবং সীমিত পরিমাণে জ্বালানী বহন করতে পারে, তবে এটি মরুভূমির যে কোনও জায়গায় জ্বালানী রেখে জ্বালানী সংগ্রহ করতে পারে। সমস্যাটি প্রথম আবির্ভূত হয় 9ম শতাব্দীর প্রপোসিসেস অ্যাড অ্যাকুয়েন্ডোস জুভেনেস (প্রোবলেমস টু শার্প দ্য ইয়ং) সংকলনে, যা অ্যালকুইনকে দায়ী করে, যেখানে ধাঁধাটি একটি ভ্রমণকারী উটের শস্য খাওয়ার বিষয়ে ছিল। লুকা প্যাসিওলির ডি ভিরিবাস কোয়ান্টিটাটিস (আনুমানিক 1500)-এও এই সমস্যা নিয়ে আলোচনা করা হয়েছে। এন. জে একটি আধুনিক চিকিৎসা দিয়েছিলেন। ঠিক আছে, 1947 সালে। সমস্যার পার্থক্যগুলি হল উট এবং কলার সমস্যা যেখানে একজন বণিককে কলাকে খাওয়ানো উট ব্যবহার করে বাজারে পরিবাহিত কলার সংখ্যা সর্বাধিক করতে হবে, মরুভূমির সমস্যা জুড়ে ভ্রমণকারীরা যেখানে বেশ কয়েকজন ভ্রমণকারীকে অবশ্যই একটি গন্তব্যে পৌঁছাতে হবে এবং সেগুলি ছেড়ে যাওয়ার পরিবর্তে কেবল সরবরাহ বিনিময় করতে পারে, এবং মরুভূমির সমস্যা জুড়ে গাড়িগুলি যা আবার তাদের জ্বালানী বিনিময় করতে পারে, কিন্তু যেখানে খালি গাড়িগুলি পরিত্যাগ করা যেতে পারে। এই চূড়ান্ত সমস্যার বহু-পর্যায়ের রকেট পরিচালনার সাথে মিল রয়েছে। সমস্যা একটি নির্দিষ্ট বেসে জ্বালানির এন ইউনিট সংরক্ষণ করা হয়। জিপটি যে কোনও সময় সর্বাধিক 1 ইউনিট জ্বালানী বহন করতে পারে এবং 1 ইউনিট জ্বালানীতে 1 ইউনিট দূরত্ব অতিক্রম করতে পারে (জিপের জ্বালানী খরচ ধ্রুবক বলে মনে করা হয়)। যাত্রার যে কোনও সময়ে জিপটি জ্বালানির ডাম্পে যে পরিমাণ জ্বালানি বহন করছে তা রেখে যেতে পারে, অথবা আগের ট্রিপের সময় জ্বালানির ডাম্পে যে পরিমাণ জ্বালানি অবশিষ্ট ছিল তা সংগ্রহ করতে পারে, যতক্ষণ না তার জ্বালানির লোড 1 ইউনিটের বেশি হয়। সমস্যার দুটি রূপ রয়েছেঃ মরুভূমি অন্বেষণ করার সময় জিপটিকে প্রতিটি ভ্রমণের শেষে ঘাঁটিতে ফিরে আসতে হবে। মরুভূমি অতিক্রম করার সময় জিপটি জ্বালানি শেষ হয়ে যাওয়ার আগে যতদূর সম্ভব ভ্রমণ করলে, শেষ যাত্রা ব্যতীত প্রতিটি যাত্রার শেষে জিপটিকে অবশ্যই ঘাঁটিতে ফিরে আসতে হবে। উভয় ক্ষেত্রেই উদ্দেশ্য হল জিপটি তার চূড়ান্ত যাত্রায় যে দূরত্ব অতিক্রম করেছে তা সর্বাধিক করা। বিকল্পভাবে, উদ্দেশ্য হতে পারে একটি নির্দিষ্ট দূরত্বের চূড়ান্ত যাত্রার জন্য প্রয়োজনীয় ন্যূনতম পরিমাণ জ্বালানি খুঁজে বের করা। বৈচিত্র্য ক্লাসিক সমস্যায় জিপে এবং জ্বালানির ডাম্পে জ্বালানীকে অবিচ্ছিন্ন পরিমাণ হিসাবে বিবেচনা করা হয়। সমস্যাটির আরও জটিল বৈচিত্র্য প্রস্তাব করা হয়েছে যেখানে জ্বালানী শুধুমাত্র বিচ্ছিন্ন পরিমাণে রেখে দেওয়া বা সংগ্রহ করা যেতে পারে। উট এবং কলার সমস্যায়, বণিকদের কাছে কলার এন ইউনিট রয়েছে। উট যে কোনও সময় সর্বাধিক 1 ইউনিট কলা বহন করতে পারে এবং 1 ইউনিট কলায় 1 ইউনিট দূরত্ব অতিক্রম করতে পারে। বাজারটি মিটার ইউনিট দূরে অবস্থিত। ভ্রমণের যে কোনও সময়ে উট ক্যাম্প পোস্টে যে পরিমাণ কলা বহন করছে তা রেখে যেতে পারে, অথবা আগের ভ্রমণে ক্যাম্প পোস্টে যে পরিমাণ কলা অবশিষ্ট ছিল তা সংগ্রহ করতে পারে, যতক্ষণ না তার কলার বোঝা 1 ইউনিটের বেশি হয়। সমস্যাটি কলার সর্বাধিক ইউনিটের জন্য জিজ্ঞাসা করে যা বাজারে পরিবহন করা যেতে পারে। মরুভূমি সমস্যা জুড়ে ভ্রমণকারীদের মধ্যে, প্রারম্ভিক ঘাঁটিতে সরবরাহের সীমাহীন ইউনিট রয়েছে। প্রতিটি ভ্রমণকারী যে কোনও সময় সর্বাধিক 1 ইউনিট সরবরাহ বহন করতে পারে এবং 1 ইউনিট সরবরাহে 1 ইউনিট দূরত্ব ভ্রমণ করতে পারে। অন্য বেসটি দূরত্বের মিটার একক দূরে অবস্থিত। আগের দুটি সমস্যার বিপরীতে, ভ্রমণকারীরা মরুভূমিতে সরবরাহ রেখে যেতে পারে না; তবে, ভ্রমণের যে কোনও সময়ে, সহযাত্রীরা নিজেদের মধ্যে সরবরাহ স্থানান্তর করতে পারে, যতক্ষণ না প্রতিটি ভ্রমণকারী কখনও 1 ইউনিটের বেশি সরবরাহ বহন করে। ফিরে আসা প্রতিটি ভ্রমণকারীকে অবশ্যই ফেরার পথে পর্যাপ্ত সরবরাহ রাখতে হবে। সমস্যাটি অন্য ঘাঁটিতে পৌঁছানোর জন্য প্রয়োজনীয় ন্যূনতম সহযাত্রীদের সংখ্যা জিজ্ঞাসা করে। এই সমস্যার একটি বৈকল্পিক উপলব্ধ ভ্রমণকারীদের মোট সংখ্যা দেয় এবং পৌঁছানো যেতে পারে এমন সর্বাধিক দূরত্বের জন্য জিজ্ঞাসা করে। মরুভূমির সমস্যা জুড়ে গাড়িগুলিতে, প্রারম্ভিক বেসে জ্বালানির সীমাহীন ইউনিট রয়েছে। প্রতিটি গাড়ি যে কোনও সময় সর্বাধিক 1 ইউনিট সরবরাহ বহন করতে পারে এবং 1 ইউনিট জ্বালানীতে 1 ইউনিট দূরত্ব অতিক্রম করতে পারে। অন্য বেসটি দূরত্বের মিটার একক দূরে অবস্থিত। গাড়িগুলি মরুভূমিতে জ্বালানি রেখে যেতে পারে না; তবে, ভ্রমণের যে কোনও সময়ে, সহগামী গাড়িগুলি নিজেদের মধ্যে জ্বালানি স্থানান্তর করতে পারে, যতক্ষণ না প্রতিটি গাড়ি কখনও 1 ইউনিটের বেশি জ্বালানি বহন করে। জ্বালানি ছাড়া খালি গাড়িগুলি মরুভূমিতে ফেলে দেওয়া হয়। সমস্যাটি অন্য ঘাঁটিতে পৌঁছানোর জন্য প্রয়োজনীয় ন্যূনতম গাড়ির সংখ্যা জিজ্ঞাসা করে। এই সমস্যার একটি বৈকল্পিক উপলব্ধ গাড়ির মোট সংখ্যা দেয় এবং পৌঁছানো যেতে পারে এমন সর্বাধিক দূরত্বের জন্য জিজ্ঞাসা করে। সমাধান একটি কৌশল যা "মরুভূমি অন্বেষণ" বৈকল্পিকের জন্য চূড়ান্ত ভ্রমণে ভ্রমণ করা দূরত্বকে সর্বাধিক করে তোলে তা নিম্নরূপঃ জিপটি এন ট্রিপ করে। প্রতিটি যাত্রায় এটি 1 ইউনিট জ্বালানী দিয়ে বেস থেকে শুরু হয়। প্রথম যাত্রায় জিপটি 1/(2এন) ইউনিট দূরত্ব অতিক্রম করে এবং একটি জ্বালানি ডাম্পে (এন-1)/এন ইউনিট জ্বালানি ছেড়ে দেয়। জিপটিতে এখনও 1/(2এন) ইউনিট জ্বালানী রয়েছে-যা ঘাঁটিতে ফিরে আসার জন্য যথেষ্ট। পরবর্তী প্রতিটি এন-1 যাত্রায় জিপটি বের হওয়ার পথে এই প্রথম জ্বালানী ডাম্প থেকে 1/(2এন) ইউনিট জ্বালানী সংগ্রহ করে, যাতে এটি 1 ইউনিট জ্বালানী বহনকারী জ্বালানী ডাম্প ছেড়ে যায়। এটি ফেরার পথে এই প্রথম জ্বালানি ডাম্প থেকে 1/(2n) ইউনিট জ্বালানী সংগ্রহ করে, যা ঘাঁটিতে ফিরে আসার জন্য যথেষ্ট জ্বালানী। দ্বিতীয় যাত্রায় জিপটি প্রথম জ্বালানি ডাম্প এবং রিফুয়েলগুলিতে যায়। এরপরে এটি 1/(2n−2) ইউনিট দূরত্ব অতিক্রম করে এবং দ্বিতীয় জ্বালানী ডাম্পে (n−2)/(n−1) ইউনিট জ্বালানী ছেড়ে দেয়। জিপটিতে এখনও 1/(2n−2) ইউনিট জ্বালানী রয়েছে, যা প্রথম জ্বালানী ডাম্পে ফিরে আসার জন্য যথেষ্ট। এখানে এটি 1/(2n) ইউনিট জ্বালানী সংগ্রহ করে, যা গোড়ায় ফিরে আসার জন্য যথেষ্ট জ্বালানী। পরবর্তী প্রতিটি এন-2 যাত্রায় জিপটি বের হওয়ার পথে এই দ্বিতীয় জ্বালানী ডাম্প থেকে 1/(2এন-2) ইউনিট জ্বালানী সংগ্রহ করে, যাতে এটি 1 ইউনিট জ্বালানী বহনকারী জ্বালানী ডাম্প ছেড়ে যায়। এটি ফেরার পথে দ্বিতীয় জ্বালানী ডাম্প থেকে 1/(2n−2) ইউনিট জ্বালানী সংগ্রহ করে, যা প্রথম জ্বালানী ডাম্পে ফিরে আসার জন্য যথেষ্ট জ্বালানী। জিপটি এইভাবে চলতে থাকে, যাতে ট্রিপ কে-তে এটি পূর্ববর্তী জ্বালানী ডাম্প থেকে 1/(2n−2k + 2) ইউনিট দূরত্বে একটি নতুন কে-তম জ্বালানী ডাম্প স্থাপন করে এবং সেখানে (n−k)/(n−k + 1) ইউনিট জ্বালানী ছেড়ে দেয়। পরবর্তী প্রতিটি n−k যাত্রায় এটি বের হওয়ার পথে kth ডাম্প থেকে 1/(2n−2k + 2) ইউনিট জ্বালানী এবং ফেরার পথে আরও 1/(2n−2k + 2) ইউনিট জ্বালানী সংগ্রহ করে। জিপটি যখন তার চূড়ান্ত যাত্রা শুরু করে, তখন সেখানে এন-1 জ্বালানির ডাম্প থাকে। সবচেয়ে দূরত্বে এক ইউনিট জ্বালানির এক-তৃতীয়াংশ থাকে, পরের দূরত্বে এক ইউনিট জ্বালানির এক-তৃতীয়াংশ থাকে, এবং নিকটতম জ্বালানির ডাম্পে মাত্র এক ইউনিট জ্বালানি অবশিষ্ট থাকে। বেস থেকে শুরু হওয়া 1 ইউনিট জ্বালানির সাথে, এর অর্থ হল জিপটি তার চূড়ান্ত যাত্রায় মোট রাউন্ড ট্রিপ দূরত্ব অতিক্রম করতে পারে (মরুভূমিতে ভ্রমণ করা সর্বোচ্চ দূরত্ব এর অর্ধেক)। এটি বের হওয়ার পথে প্রতিটি ডাম্পে অবশিষ্ট জ্বালানির অর্ধেক সংগ্রহ করে, যা তার ট্যাঙ্কটি পূরণ করে। সবচেয়ে দূরবর্তী জ্বালানি ডাম্প ছেড়ে যাওয়ার পরে এটি মরুভূমিতে এক ইউনিটের এক-তৃতীয়াংশ অতিক্রম করে এবং তারপর সবচেয়ে দূরবর্তী জ্বালানি ডাম্পে ফিরে আসে। এটি ফেরার পথে প্রতিটি জ্বালানির ডাম্প থেকে অবশিষ্ট জ্বালানি সংগ্রহ করে, যা পরবর্তী জ্বালানির ডাম্পে পৌঁছানোর জন্য বা চূড়ান্ত ধাপে, বেসে ফিরে আসার জন্য যথেষ্ট। শেষ যাত্রায় যে দূরত্ব অতিক্রম করা হয়েছে তা হল নবম সুরেলা সংখ্যা, এইচএন। যেহেতু সুরেলা সংখ্যা সীমাহীন, তাই চূড়ান্ত যাত্রায় যে কোনও নির্দিষ্ট দূরত্ব অতিক্রম করা সম্ভব, কারণ গোড়ায় পর্যাপ্ত জ্বালানি পাওয়া যায়। যাইহোক, প্রয়োজনীয় জ্বালানির পরিমাণ এবং জ্বালানি ডাম্পের সংখ্যা উভয়ই ভ্রমণের দূরত্বের সাথে তাত্পর্যপূর্ণভাবে বৃদ্ধি পায়। "ক্রসিং দ্য ডেজার্ট" বৈকল্পিকটি একই কৌশলের মাধ্যমে সমাধান করা যেতে পারে, তবে চূড়ান্ত যাত্রায় ফেরার পথে জ্বালানি সংগ্রহের কোনও প্রয়োজন নেই। সুতরাং ট্রিপ কে-তে জিপটি পূর্ববর্তী জ্বালানী ডাম্প থেকে 1/(2n−2k + 1) ইউনিট দূরত্বে একটি নতুন kth জ্বালানী ডাম্প স্থাপন করে এবং সেখানে (2n−2k−1)/(2n−2k + 1) ইউনিট জ্বালানী ছেড়ে দেয়। পরবর্তী প্রতিটি n−k−1 ভ্রমণে এটি বের হওয়ার পথে kth ডাম্প থেকে 1/(2n−2k + 1) ইউনিট জ্বালানী সংগ্রহ করে এবং ফেরার পথে আরও 1/(2n−2k + 1) ইউনিট জ্বালানী সংগ্রহ করে। এখন যখন জিপটি তার চূড়ান্ত যাত্রা শুরু করে, তখন সেখানে এন-1 জ্বালানির ডাম্প থাকে। সবচেয়ে দূরত্বে এক ইউনিট জ্বালানির এক তৃতীয়াংশ থাকে, পরের দূরত্বে এক ইউনিট জ্বালানির এক পঞ্চমাংশ থাকে এবং নিকটতম জ্বালানির ডাম্পে মাত্র এক ইউনিট জ্বালানি অবশিষ্ট থাকে। বেস থেকে শুরু হওয়া 1 ইউনিট জ্বালানির সাথে, এর অর্থ হল জিপটি তার চূড়ান্ত যাত্রায় মোট এক ইউনিট দূরত্ব অতিক্রম করতে পারে। এটি বের হওয়ার পথে প্রতিটি ডাম্পে অবশিষ্ট সমস্ত জ্বালানী সংগ্রহ করে, যা তার ট্যাঙ্কটি পূরণ করে। সবচেয়ে দূরবর্তী জ্বালানির ডাম্প ছেড়ে যাওয়ার পরে এটি আরও 1 ইউনিট দূরত্ব অতিক্রম করে। লক্ষ্য করুন যে, তত্ত্বগতভাবে যে কোনও আকারের মরুভূমি অতিক্রম করা সম্ভব, যদি এর গোড়ায় পর্যাপ্ত জ্বালানি থাকে। আগের মতোই, প্রয়োজনীয় জ্বালানির পরিমাণ এবং জ্বালানি ডাম্পের সংখ্যা উভয়ই ভ্রমণের দূরত্বের সাথে তাত্পর্যপূর্ণভাবে বৃদ্ধি পায়। সংক্ষেপে, এন ট্রিপগুলিতে (এন-1 মাঝামাঝি জ্বালানী ডাম্প সহ এবং মোট এন ইউনিট জ্বালানী খরচ করে) জিপ দ্বারা পৌঁছানো সর্বাধিক দূরত্ব হল, মরুভূমি অন্বেষণের জন্য যেখানে প্রতিটি ট্রিপের শেষে জিপকে অবশ্যই গোড়ায় ফিরে আসতে হবে; মরুভূমি অতিক্রম করার জন্য যেখানে শেষ ট্রিপ ব্যতীত প্রতিটি ট্রিপের শেষে জিপকে ঘাঁটিতে ফিরে আসতে হবে, যখন জিপ জ্বালানী শেষ হওয়ার আগে যতদূর সম্ভব ভ্রমণ করে। এখানে n তম সুরেলা সংখ্যাটি রয়েছে। জ্বালানির অবিচ্ছিন্ন পরিমাণ গোড়ায় উপলব্ধ জ্বালানি ইউনিটের সংখ্যা একটি পূর্ণসংখ্যা হতে হবে না। সাধারণ ক্ষেত্রে, জ্বালানির ইউনিটগুলির সাথে "মরুভূমি অন্বেষণ" সমস্যার জন্য সর্বাধিক দূরত্ব অর্জনযোগ্য হল প্রথম জ্বালানী ডাম্পটি প্রারম্ভিক বেস থেকে দূরত্বের এককগুলিতে অবস্থিত, দ্বিতীয়টি প্রথম জ্বালানী ডাম্প থেকে দূরত্বের এককগুলিতে, তৃতীয়টি দ্বিতীয় জ্বালানী ডাম্প থেকে দূরত্বের এককগুলিতে, এবং আরও অনেক কিছু। এখানে এর ভগ্নাংশ অংশ। জ্বালানির ইউনিটগুলির সাথে "মরুভূমি অতিক্রম" সমস্যার জন্য সর্বাধিক দূরত্ব অর্জনযোগ্য হল প্রথম জ্বালানী ডাম্পটি প্রারম্ভিক বেস থেকে দূরত্বের এককগুলিতে অবস্থিত, দ্বিতীয়টি প্রথম জ্বালানী ডাম্প থেকে দূরত্বের এককগুলিতে, তৃতীয়টি দ্বিতীয় জ্বালানী ডাম্প থেকে দূরত্বের এককগুলিতে, এবং আরও অনেক কিছু। এখানে এর ভগ্নাংশ অংশ। সমস্যাটির অন্যান্য রূপগুলি উট ও কলার সমস্যায়, ধরে নেওয়া যায় যে, ব্যবসায়ীর কাছে শুরুর গোড়ায় মোট এন = 7/3 ইউনিট কলা রয়েছে এবং বাজারটি মিটার ইউনিট দূরে রয়েছেঃ যদি এই সমস্যার কোনও সমাধান না থাকে; পরিবহনের জন্য কোনও মিডওয়ে ক্যাম্প পোস্টের প্রয়োজন না হয় এবং উটের দ্বারা দূরত্বটি বার বার করা হয়, তবে বাজারে সর্বাধিক পরিমাণে কলা পাঠানো হয়; যদি, সর্বাধিক পরিমাণে কলা পরিবহনের জন্য কিছু মিডওয়ে ক্যাম্প পোস্টের প্রয়োজন হয়ঃ মিটার = 1/4 <(1/3+1 15) এর জন্য, প্রারম্ভিক ঘাঁটি থেকে দূরে 1/15 ইউনিটের দূরত্বে কেবল একটি মিডওয়ে ক্যাম্প পোস্টের প্রয়োজন হয়, যেখানে মোট 2 ইউনিট কলা রয়েছে। ক্যাম্প পোস্ট থেকে বাজার পর্যন্ত দূরত্ব হল (1/4-1 15), যা উট দ্বারা 3 বার পুনরাবৃত্তি করা হবে, এবং বাজারে পরিবহন করা সর্বাধিক পরিমাণ কলা হল 2-(1/4-1 15) * 3 = 1.45 ইউনিট; এম = 1/2> (1/3+1 15)-এর জন্য, প্রথম ক্যাম্প পোস্ট থেকে 1/3 ইউনিট দূরত্বে আরেকটি মিডওয়ে ক্যাম্প পোস্ট প্রয়োজন, যেখানে মোট 1 ইউনিট কলা জমা হবে। দ্বিতীয় ক্যাম্প পোস্ট থেকে বাজারের দূরত্ব হল [1/2 (1/3+1 15)], যা উটের মাধ্যমে শুধুমাত্র একবার ভ্রমণ করা হবে, এবং বাজারে পরিবহন করা কলার সর্বোচ্চ পরিমাণ হল 1-[1/2 (1/3+1 15)] * 1 = 0.9 ইউনিট। যদি উটটিকে শেষ পর্যন্ত প্রারম্ভিক ঘাঁটিতে ফিরে যেতে হয়, তবে ফাংশনটি প্রযোজ্য হয় (এখনও n = 7/3 ধরে নেওয়া হচ্ছে): যদি এই সমস্যার কোনও সমাধান বিদ্যমান না থাকে; যদি পরিবহনের জন্য কোনও মিডওয়ে ক্যাম্প পোস্টের প্রয়োজন না হয়, এবং দূরত্ব m উট দ্বারা বার বার পুনরাবৃত্তি করা হবে, তাই বাজারে সর্বাধিক পরিমাণে কলা পরিবহন করা হয়; যদি, সর্বাধিক পরিমাণে কলা পরিবহনের জন্য কিছু মিডওয়ে ক্যাম্প পোস্টের প্রয়োজন হয়ঃ m = 1/4 <(1/4+1 18) এর জন্য, প্রারম্ভিক ঘাঁটি থেকে 1/18 ইউনিট দূরে কেবল একটি মিডওয়ে ক্যাম্প পোস্ট প্রয়োজন, যেখানে উটের চূড়ান্ত প্রত্যাবর্তনের জন্য মোট 2 ইউনিট কলা (যোগ 1/18 ইউনিট) প্রয়োজন। ক্যাম্প পোস্ট থেকে বাজারের দূরত্ব হল (1/4-1 18), যা উট দ্বারা 4 বার পুনরাবৃত্তি করা হবে, এবং বাজারে পরিবহন করা কলার সর্বাধিক পরিমাণ হল 2-(1/4-1 18) * 4 = 1.22 ইউনিট; এম = 1/2> (1/4+1 18)-এর জন্য, প্রথম ক্যাম্প পোস্ট থেকে 1/4 ইউনিটের দূরত্বে আরেকটি মিডওয়ে ক্যাম্প পোস্ট প্রয়োজন, যেখানে মোট 1 ইউনিট কলা (উটের চূড়ান্ত প্রত্যাবর্তনের জন্য 1/4 ইউনিট যোগ) জমা হবে। দ্বিতীয় ক্যাম্প পোস্ট থেকে বাজারের দূরত্ব হল [1/2 (1/4+1 18)], যা উট দ্বারা দুবার পুনরাবৃত্তি করা হবে, এবং বাজারে পাঠানো কলার সর্বোচ্চ পরিমাণ হল 1-[1/2 (1/4+1 18)] * 2 = 0.61 ইউনিট। মরুভূমি সমস্যা জুড়ে ভ্রমণকারীদের মধ্যে, ধরে নিন যে n ভ্রমণকারীরা সরবরাহের n ইউনিট নিয়ে প্রারম্ভিক ঘাঁটি থেকে যাত্রা শুরু করে। 1/(এন + 1) ইউনিট দূরত্বের পরে, তারা ইতিমধ্যে এন/(এন + 1) ইউনিট সরবরাহ গ্রহণ করত; এই মুহুর্তে, ভ্রমণকারীদের মধ্যে একজনকে 1/(এন + 1) ইউনিট সরবরাহ নিয়ে ফিরে আসতে হবে, গোষ্ঠীটিকে ঠিক (এন-1) ইউনিট সরবরাহ রেখে যাতে প্রতিটি অবশিষ্ট ভ্রমণকারী ঠিক একটি ইউনিট সরবরাহ বহন করে। এরপরে দলটি আরও 1/(এন + 1) ইউনিট দূরত্ব অতিক্রম করে, (এন-1)/(এন + 1) ইউনিট সরবরাহ গ্রহণ করে; এই মুহুর্তে, অবশিষ্ট ভ্রমণকারীদের মধ্যে একজনকে 2/(এন + 1) ইউনিট সরবরাহ নিয়ে নিরাপদে প্রারম্ভিক ঘাঁটিতে ফিরে যেতে হবে, ঠিক (এন-2) ইউনিট সরবরাহ রেখে। দলটি 1/(এন + 1) ইউনিট দূরত্ব সরাতে থাকে এবং একজন ভ্রমণকারীকে কমিয়ে দেয়, যতক্ষণ না কেবল একজন ভ্রমণকারী ঠিক একটি ইউনিট সরবরাহ বহন করে। পরিশেষে, এই ভ্রমণকারী দূরতম বিন্দুতে পৌঁছানোর জন্য এক ইউনিট দূরত্ব অতিক্রম করতে পারেন। মোট, n ভ্রমণকারীরা পৌঁছতে পারে এমন দীর্ঘতম দূরত্ব হল এটাকে m-এর সমতুল্য করা, দূরত্বের m একক ভ্রমণের জন্য প্রয়োজনীয় ন্যূনতম সংখ্যক ভ্রমণকারীর জন্য সমাধান করা যেতে পারে। লক্ষ্য করুন যে সমাধানগুলি শুধুমাত্র m <2-এর জন্য বিদ্যমান। যদি শেষ এবং চূড়ান্ত ভ্রমণকারীকেও প্রারম্ভিক ঘাঁটিতে ফিরে যেতে হয়, তবে সে কেবল 1/(এন + 1) ইউনিট একা ভ্রমণ করবে যাতে তার ফিরে আসার জন্য এন/(এন + 1) ইউনিট সরবরাহ থাকে, তাই দীর্ঘতম দূরত্ব n ভ্রমণকারীরা পৌঁছতে পারে এটি এম এর সমতুল্য, দূরত্বের এম ইউনিট ভ্রমণের জন্য প্রয়োজনীয় ন্যূনতম সংখ্যক ভ্রমণকারীর জন্য সমাধান করা যেতে পারে। লক্ষ্য করুন যে সমাধানগুলি শুধুমাত্র m <1-এর জন্য বিদ্যমান। মরুভূমির সমস্যা জুড়ে গাড়িগুলিতে, ধরে নিন যে n গাড়িগুলি জ্বালানির n ইউনিট নিয়ে প্রারম্ভিক বেস থেকে যাত্রা শুরু করে। 1/এন ইউনিট দূরত্বের পরে, দলটি ইতিমধ্যে ঠিক এক ইউনিট জ্বালানী খরচ করত; এই মুহুর্তে, তাদের মধ্যে জ্বালানী স্থানান্তর করা উচিত, একটি খালি গাড়ি রেখে দেওয়া উচিত এবং (এন-1) গাড়ির মধ্যে (এন-1) ইউনিট জ্বালানী বহন করা উচিত। আরও 1/(এন-1) ইউনিট দূরত্বের পরে, দলটি আরও একটি ইউনিট জ্বালানী খরচ করত; আবার, তাদের জ্বালানী স্থানান্তর করা উচিত, একটি খালি গাড়ি পিছনে রেখে দেওয়া উচিত এবং (এন-2) গাড়ির মধ্যে (এন-2) ইউনিট জ্বালানী বহন করা উচিত। দলটি চলতে থাকে এবং একটি গাড়ি কমাতে থাকে, যতক্ষণ না ঠিক একটি ইউনিট জ্বালানী বহনকারী একটি গাড়ি অবশিষ্ট থাকে। পরিশেষে, এই গাড়িটি এক ইউনিট দূরত্ব অতিক্রম করে সবচেয়ে দূরবর্তী স্থানে পৌঁছতে পারে। মোট, n গাড়ি পৌঁছতে পারে এমন দীর্ঘতম দূরত্ব হল n তম সুরেলা সংখ্যাঃ এটিকে m এর সমতুল্য করলে, দূরত্বের m ইউনিট ভ্রমণের জন্য প্রয়োজনীয় ন্যূনতম সংখ্যক গাড়ির জন্য সমাধান করা যেতে পারে। অর্ডারের স্বাধীনতা মনে রাখবেন যে জিপের যাত্রার ক্রম নির্দিষ্ট নয়। উদাহরণস্বরূপ, সমস্যার "মরুভূমি অন্বেষণ" সংস্করণে, জিপটি বেস এবং প্রথম জ্বালানী ডাম্পের মধ্যে রাউন্ড-ট্রিপ করতে পারে, প্রতিবার জ্বালানী ডাম্পে জ্বালানির ইউনিটগুলি রেখে দেয় এবং তারপরে প্রথম জ্বালানী ডাম্পের দিকে একমুখী ট্রিপ করে, এইভাবে মোট ইউনিট জ্বালানী সহ সেখানে পৌঁছায়। ইউনিটগুলি একেবারে শেষে ঘাঁটিতে ফিরে যাওয়ার জন্য সংরক্ষণ করা হয় এবং জ্বালানির অন্যান্য ইউনিটগুলি প্রথম এবং দ্বিতীয় জ্বালানী ডাম্পের মধ্যে জ্বালানী সরানোর জন্য ব্যবহার করা হয়, রাউন্ড-ট্রিপ ব্যবহার করে এবং তারপর দ্বিতীয় জ্বালানী ডাম্পে একমুখী ট্রিপ ব্যবহার করে। এবং ইত্যাদি। ব্যবহারিক প্রয়োগ সমস্যাটি যুদ্ধকালীন পরিস্থিতিতে ব্যবহারিক প্রয়োগ হতে পারে, বিশেষ করে জ্বালানি দক্ষতার ক্ষেত্রে। দ্বিতীয় বিশ্বযুদ্ধে বি-29-এর দ্বারা জাপানে বোমা হামলার প্রসঙ্গে, রবার্ট ম্যাকনামারা দ্য ফগ অফ ওয়ার ছবিতে বলেছেন যে, সামনের ঘাঁটিতে জ্বালানি পরিবহনের কারণে সৃষ্ট জ্বালানি দক্ষতার সমস্যা বোঝা মূল কারণ ছিল যে মূল ভূখণ্ড চীন থেকে বোমা হামলা চালানোর কৌশলটি দ্বীপ হপিং কৌশলের পক্ষে পরিত্যাগ করা হয়েছিলঃ (দ্বিতীয় বিশ্বযুদ্ধের শেষে পারমাণবিক বোমা হামলা মিশনগুলি উত্তর মারিয়ানা দ্বীপপুঞ্জের প্রশান্ত মহাসাগরীয় দ্বীপ টিনিয়ান থেকে বি-29 সুপারফোর্ট্রেস ব্যবহার করে উড়েছিল।) এই ধারণাগুলির প্রয়োগের জন্য অপারেশন ব্ল্যাক বাক দেখুন। ফকল্যান্ড যুদ্ধের সময় পরিচালিত এই মিশনগুলিতে, রয়্যাল এয়ার ফোর্স অ্যাসেনশন দ্বীপপুঞ্জ ভিত্তিক ভলকান বোমারু বিমানগুলিকে ফকল্যান্ড দ্বীপপুঞ্জের লক্ষ্যবস্তুতে বোমাবর্ষণ করতে সক্ষম করার জন্য ট্যাঙ্কার স্থাপন করে বাতাসে জ্বালানি ভরার জন্য ব্যবহার করেছিল। আরও দেখুন হারমোনিক সিরিজ (গণিত) অপ্টিমাইজেশন (গণিত) রেফারেন্স গাণিতিক অপ্টিমাইজেশন বিনোদনমূলক গণিত