معمای هتل

یک معمای ریاضی

       پایتون ریاضیات 
✤    ۳ اسفند ۱۳۸۸ - آخرین به‌روزرسانی: ۱۴ تیر ۱۴۰۳

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

هتلی را با صد اتاق در بسته در نظر بگیرید که با شماره های یک تا صد مشخص شده‌اند. قرار است از این هتل صد نفر با شماره‌های یک تا صد بازدید کنند و هر کس با وارد شدن به ساختمان هتل، تمام در اتاق‌هایی را که شماره‌ی آن‌ها مضرب صحیحی از شماره‌ی خودشان باشد تغییر وضعیت می دهند! یعنی اگر در بسته باشد، باز کرده و اگر باز باشد می بندند. به عنوان مثال نفر شماره‌ی سه در اتاق‌های شماره‌ی سه، شش و مضارب بعدی سه را که کوچکتر یا مساوی صد هستند تغییر وضعیت می‌دهد. سوال این است که بعد از تمام شدن بازدید همه‌ی افراد، چه تعداد در باز وجود خواهد داشت؟ برای رسیدن به جواب مسئله، به جای عدد صد متغیر $n$ را فرض می گیریم و در صورتی که بتوانیم به نتیجه‌ی مطلوب برسیم، مسئله نه تنها برای صد اتاق که برای تمام اعداد طبیعی حل خواهد شد. در ادامه قطعه کد جواب الگوریتمی معما با زبان برنامه‌نویسی پایتون آمده است.

  

n = int(input())

doors = (n+1) * [0]

for person_number in range(1, n+1):

  for door_number in range(person_number, n+1, person_number):

    doors[door_number] = 1-doors[door_number]

print(doors.count(1))

  

حل این مسئله را با طرح یک سوال شروع می‌کنم: هر کدام از درها در چه شرایطی تغییر وضعیت می دهند؟ پاسخ به این سوال چندان هم سخت نیست. بر اساس صورت مسئله، هر شخص تنها درهایی را تغییر وضعیت می‌دهد که شماره اتاق مضرب صحیحی از شماره‌ی خودش باشد. پس هر در توسط افرادی تغییر وضعیت داده می‌شود که شماره‌ی اتاق بر شماره آنها قابل قسمت باشد. این عبارت در عالم ریاضیات معادل آن است که شماره‌ی شخص مقسوم‌علیه شماره‌ی اتاق باشد. یعنی هر در به تعداد مقسوم‌علیه‌های شماره‌ی اتاق تغییر وضعیت می دهند.

هر در تنها دو وضعیت باز یا بسته دارد و همه‌ی درها در ابتدا بسته هستند. تغییر وضعیت هم به صورت متناوب بین دو حالت انجام می‌شود. پس اگر به طور مثال دو بار تغییر وضعیت دهیم، در مجددا بسته می‌شود. پس می‌توان گفت درهایی باز می‌مانند که به تعداد فرد بار تغییر وضعیت داده باشند.

با ترکیب نتایج دو بند بالا می‌توان گفت درهایی در پایان بازدید باز می مانند که تعداد مقسوم‌علیه‌های شماره‌ی اتاقشان عدد فردی باشد. حال سوال این است که کدام اعداد طبیعی تعداد مقسوم‌علیه‌هایشان فرد است؟ می‌دانیم که هر عدد طبیعی دلخواه $n$ را می‌توان به صورت زیر نوشت که $p_j$ها اعداد اول هستند. چنین نمایشی - صرف نظر از ترتیب $p_j$ها - برای هر عدد طبیعی منحصر به فرد است.

\[n= \prod_{i=1}^{k} {p_j}^{\alpha_j} = {p_1}^{\alpha_1} {p_2}^{\alpha_2} {p_3}^{\alpha_3} \cdots {p_k}^{\alpha_k} \]

لم یک: فرض کنید عدد $n$ به صورت فوق نمایش داده شده باشد. در این صورت تعداد مقسوم‌علیه‌های از رابطه‌ی زیر محاسبه می‌شود.

\[(\alpha_1 + 1) (\alpha_2 + 1) (\alpha_3 + 1) \cdots (\alpha_k + 1) \]

لم دو: اگر a و b دو عدد صحیح باشند حاصلضرب آنها عددی فرد است اگر و فقط اگر هر دو عدد فرد باشند.

تا به اینجا نتیجه این بوده که باید سراغ اعداد با تعداد مقسوم‌علیه‌های فرد برویم و بر اساس لم یک ما دنبال اعدادی هستیم که برای آن‌ها حاصلضرب مذکور عدد فردی باشد. لم دو می‌گوید تنها زمانی این عبارت فرد خواهد بود که تک تک عبارتهای داخل پرانتز فرد باشند و این یعنی تک تک $\alpha_j$ها باید زوج باشند. در نتیجه می‌توان نوشت:

\[ \forall j \; \exists q_j \; s.t. \; \alpha_j = 2 \times q_j \;\;\; \implies \;\;\; n = \prod_{i=1}^{k} {p_j}^{\alpha_j} = \prod_{i=1}^{k} {p_j}^{2q_j} = \left( \prod_{i=1}^{k} {p_j}^{q_j} \right)^2\]

بنابراین عدد $n$ باید مربع کامل باشد. در صورتی که مسئله را به صورت دستی حل کنید، می بینید که درهای یک، چهار، نه، شانزده و ... تنها درهایی هستند که در پایان بازدید باز می‌مانند و تعداد چنین اعدادی در بازه‌ی یک تا $n$ برابر $\left[\sqrt{n}\right]$ است (چرا؟؟؟) که منظور از [ ] علامت جزء صحیح است.


این نوشته از وبلاگ ریاضیکده به الگوریتمستان منتقل شده است.

تا کنون ۰ امتیاز ثبت شده
نوشته لایک نداشت؟
 
به اشتراک گذاری نوشته

algs.ir/spue2v1

اشتراک‌گذاری در LinkedIn     اشتراک‌گذاری در Twitter     ارسال با Telegram

نام: *  
پست الکترونیک (محرمانه):
پیام: *  
• بابا سعيد
۵ اسفند ۱۳۸۸، ساعت ۱۰:۴۱

سلام

مطلب بسيارمفيد و شيريني شروع كرده ايد جرقه هاي رياضي را در اعماق مغزم  روشن فرموديد با اجازه ديشب تا صبح درخواب رياضي حل مي كردم اميدوارم سلامت وسعادتمند توانمند باشي06

مسعود اقدسی‌فام
۵ اسفند ۱۳۸۸، ساعت ۱۸:۰۵

سلام

بسیار خوشحالم که اینگونه شده است. 01

فقط مواظب باشید. اینطوری پیش بروید آخر و عاقبتتان مثل جان نش رحمت اله علیه می شود.05 03

• بابا سعيد
۹ اسفند ۱۳۸۸، ساعت ۲۰:۴۰

سلام آقا مسعود عزيز

ازخوشحاليتان خوشحالم اميدوارم انگيزه هاي مفيد وخوبموجب خوشحاليتان شوددر خصوص عاقبت نيز خدا مختار است افوض امري الي الله

من ملك بودم فردوس برين جايم بود  آدم آورد دراين دير خراب آبادم

باز هم از رياضي بنويس06

• احمد
۱۳ اسفند ۱۳۸۸، ساعت ۱۶:۴۷

سلام

ميلاد حضرت محمد (ص)وامام جعفرصادق (ع)را خدمت شما استاد گرانقدر تبريك عرض مكنم

• زهرا
۱۳ اسفند ۱۳۸۸، ساعت ۱۸:۴۹

هان؟!0405