حسین نوشته ها ...

این مسئله رو در این پست توضیح دادیم و اینجا قراره حلش کنیم .

یکی از مرسوم ترین کارهایی که برای حل این سوالات میتونیم انجام بدیم الگویابی هست . به عبارتی بیایم خودمون دستی جواب مسئله رو برای ورودی های مختلف حساب کنیم و ببینیم آیا الگوی خاصی بین ورودی مسئله و جوابی که بدست میاد در مجموعه داده ها هست که ما بتونیم ازش استفاده کنیم یا نه .

ورودی این مسئله تعداد نفرات بود که با n نشون میدیم و خروجی مسئله هم شماره اون شخصیه که در نهایت بعد از خودکشی دست جمعی زنده میمونه . 

من اومدم به صورت دستی روی برگه این سوال رو برای ورودی های ۱ تا 16 حساب کردم که به صورت زیر درومد . در هر مدخل مقدار n (تعداد نفرات) و جواب مسئله به ازای اون تعداد نفرات (شماره شخصی که زنده میمونه) مشخص شده :

اگر دقت کنیم متوجه یه نکته جالبی میشیم . برای n هایی که توانی از ۲ هستند جواب مسئله همیشه ۱ شده ! . یعنی همیشه نفر یکم زنده میمونده . این موارد رو من برجسته کردم در تصویر زیر :

حالا میخوام توجه شما رو به n های بین توان های دو جلب کنم . یعنی مثلا جواب های مسئله رو برای n های بین ۲ تا ۸ که هر دو توان های دو هستند در نظر بگیرید . طبق الگویی که بالا دیدیم قاعدتا خود n=2 و n=8 جواب مسئله ۱ میشه ولی n های بینشون رو دقت کنید چه الگویی دارن :

جالبه که این جواب مسئله برای این اعداد یعنی از n=2 تا قبل از n=8 از ۱ شروع شدن و در هر مرحله ۲ واحد به اونا اضافه شده عملا چنین الگویی رو تشکیل دادن :

1 , 3 , 5 , 7 , 9 , ....

اگر دقت کنید و خودتون بررسی کنیم میبینید این الگو برای تمام n های بین دو توان متوالی ۲ وجود داره . مثلا n=32 و n=64 هر دو توان هایی متوالی از دو هستند (2⁵ و 2⁶) اگر جواب های این مسئله رو از n=32 تا n=63 در بیاریم میبینیم همین الگوی عددی رو تشکیل میدن :

  1 , 3 , 5 , 7 , 9 , ....

وقتی n=64 میشه باز دوباره جواب مسئله ۱ میشه و دوباره اون الگو از اول تکرار میشه چون 64 توانی از ۲ هست و دیدیم که تمام n هایی که توان ۲ هستند جواب ۱ رو میگیرن .

با این اوصاف هر n که داشته باشیم میتونیم بگیم جواب اون مسئله چقدر میشه . برای مثال فرض کنید به ما n=41 رو بدن . میایم میبینیم نزدیک ترین توان ۲ قبل از ۴۱ چه عددی هست که عدد ۳۲ هست (2⁵) . میدونیم که برای n های بزرگتر از ۳۲ اعداد از الگوی 1,3,5,7, .. .پیروی میکنن . پس به صورتی دستی این الگو رو میریم جلو تا برسیم به عدد n=41 :

n=32 --> 1

n=33 --> 3

n=34 --> 5

n=35 --> 7

n=36 --> 9

n=37 --> 11

n=38 --> 13

n=39 --> 15

n=40 --> 17

n=41 --> 19

این روش دستی جواب میده ولی خب بیاید یک فرمول ریاضیاتی براش بدست بیاریم که راحت تر بتونیم حساب کنیم .

از ریاضیات دبیرستان میدونیم که به دنباله ای از اعداد که با یک مقدار ثابت دائما زیاد یا کم میشن میگیم دنباله خطی . مثل دنباله های زیر :

1 , 3 , 5 , 7 , 9 , ....   (d = 2)

1 , 2 , 3 , 4 , 5 , 6 , ... (d = 1)

100, 95, 90, 85, ....   (d = -5)

هر سه خط بالا مثالی از یک دنباله خطی بودن . خط اول یک دنباله خطی با تغییرات ۲ هست چون هر مرحله ۲ واحد به مقدار قبلی اضافه شده . این مقدار اضافه شده یا کم شده رو با حرف d نشون دادیم . برای دو مثال دیگر هم به همین صورته فقط مقدار d یا اون مقدار ثابتی که در هر مرحله تغییر میکنه متفاوته . به اینجور دنباله ها که مقدار تغییرشون (d) در هر مرحله یک عدد ثابته دنباله خطی میگیم .

در ریاضیات دبیرستان به ما یک فرمولی گفتن که میتونیم توسط اون جمله n ام یک دنباله خطی دلخواه رو حساب کنیم . جمله n ام منظور n امین عدد در دنباله مذکوره . مثلا همین دنباله 1,3,5,7,9,... رو در نظر بگیرید ، جمله اول برابر ۱ هست . جمله سوم برابر ۵ هست و جمله چهارم برابر 7 هست . این مفهوم جمله n ام هستش .جمله nام را با T_n نشون میدیم . جمله n ام یک دنباله خطی توسط فرمول زیر میتونه بدست بیاد :

در فرمول بالا d برابر همون مقدار ثابت تغییر در دنباله هست که در بالا دیدیم . a1 هم برابر جمله ابتدایی دنباله هست یعنی اون عددی که دنباله با اون شروع میشه .

برگردیم به مسئله ژوزفوس . دیدیم که بین n ها با توان های متوالی ۲ ، جواب های مسئله دنباله خطی زیر رو تشکیل میدن :

1 , 3 , 5 , 7 , 9 , ...

طبق تعریف فرمول میدونیم که در اینجا d=2 هست و a1=1 هست . بنابراین :

پس جمله n ام این دنباله از طریق عبارت 2n-1 بدست میاد (دقت کنید این n با ورودی مسئله ژوزفوس فرق داره . اون n مشخص کننده تعداد سربازانه ولی تو بحث دنباله این n مشخص کننده شماره جمله در دنباله هست) . کار تمومه . با همین فرمول میتونید جواب مسئله ژوزفوس کبیر رو بدست بیاریم .

مثلا هون n=41 یا به عبارتی مسئله با ۴۱ سرباز . اول میایم نزدیک ترین توان ۲ که قبل از 41 هست رو پیدا میکنیم که اینجا میشه ۳۲ . چرا اینکارو میکنیم ؟ چون میخوایم بشماریم ۴۱ چندتا بعد از ۳۲ هست و در نتیجه جمله چندم اون دنباله خطی 1,3,5,7, .. .رو باید بدست بیاریم (شروع دنباله از n=32 هست که برابر ۱ میشه و وقتی بریم بالا برسیم به 41 میبنم عدد 41 در اصل متناظر با جمله دهم اون دنباله خطی 1,3,5,7 هستش) . به عبارتی میتونیم از طریق تفریق زیر شماره جمله در دنباله رو بدست بیاریم  :

41 - 32 + 1 = 10

دقت کنید یک بار به علاوه ۱ میکنیم چون خود n=32 هم جزو دنباله 1,3,5,7, ... هست و درواقع اولین جمله دنباله هست که جوابش ۱ میشه . پس باید جمله دهم دنباله خطی رو بدست بیاریم . فرمول 2n-1 که بدست آوردیم رو برای n=10 حساب میکنیم تا جمله دهم دنباله بدست بیاد :

T_n = 2n-1

=> T₉ = 2(10) - 1 = 19

پس اگر در مسئله ژوزفوس ما ۴۱ نفر داشته باشیم که خودکشی دست جمعی انجام بدن نفر ۱۹ ام زنده میمونه در آخر . 

۱ ۰