باب اسفنجی ۳۵ همبرگر تهیه کرده است که تمامی آنها را میخواهد سرخ کند. سرخ شدن دو سمت هر همبرگر در مجموع ۱۴۰۴ ثانیه طول میکشد؛ یعنی اگر سمت زیرین همبرگر $i$ اُم به $t_i$ ثانیه برای سرخ شدن نیاز داشته باشد، سمت دیگر آن به $1404 - t_i$ ثانیه نیاز دارد. باب اسفنجی مقادیر $t_i$ را میداند و متوجه شده است که تمامی آنها عددی طبیعی و کوچکتر از ۱۴۰۴ هستند.
در ابتدا باب اسفنجی هرکدام از ۳۵ همبرگر را به طور همزمان از سمت دلخواه خود روی اجاق میگذارد و به شستن ظرفها میپردازد. همچنین باب اسفنجی نباید هیچ سمتی از همبرگرها را بسوزاند؛ برای همین میتواند هر زمانی که دلش میخواهد از ظرف شستن دست بکشد و یک زیرمجموعهی دلخواه از همبرگرها را انتخاب و در زمانی ناچیز برگرداند تا سمت دیگر آن به سرخ شدن ادامه دهد. حداقل تعداد بارهایی که او لازم دارد تا قبل از پختهشدن همبرگرها دست از ظرف شستن بردارد تا بتواند آنها را بدون سوزاندن حاضر کند چهقدر است؟
پاسخ
گزینهی ۳ درست است.
ابتدا یک روش با ۱۰ مرحله ارائه میدهیم و سپس اثبات میکنیم حالتی وجود دارد که با کمتر از ۱۰ مرحله نمیتوان از سوختن همبرگرها جلوگیری کرد. روش جلوگیری از سوختن همبرگرها به این شکل است که ابتدا تمامی همبرگرها را به سمتی که زمان بیشتری (یا مساوی) برای پختن نیاز دارد قرار میدهیم. سپس هنگامی که نصف زمان کل برای ما سپری شد، در قابلمه را باز کرده و هر همبرگر را به سمتی که بیشتر (یا مساوی) از زمان پختش باقیمانده است قرار میدهیم و همین کار را تا انتها ادامه میدهیم؛ یعنی هر بار بعد از سپری شدن سقف نصف زمان قبلی، در قابلمه را برداشته و همبرگرها را به سمتی که بیشتر (یا مساوی) از زمان پختشان باقی مانده قرار میدهیم.
برای اینکه اثبات کنیم که با کمتر از ۱۰ بار نمیتوان این کار را انجام داد، ابتدا به این نکته توجه کنید که اگر $k$ بار در قابلمه را برداشته باشیم کل بازهی زمانی ما به $k+1$ قسمت تقسیم میشود. حال هر همبرگر در بعضی از این بازهها به سمت پایین و در بعضی به سمت بالا قرار داشته است که یعنی باید جمع تعدادی از این بازهها برابر $t_i$ باشد. پس فرض کنید $\langle t_0, t_1, \cdots, t_{10}\rangle = \langle 2^0, 2^1, \cdots, 2^{10}\rangle$ باشند و باقی $t_i$ها مقدار دلخواهی داشته باشند. میدانیم برای ساختن اعداد $\langle 2^0, 2^1, \cdots, 2^{10}\rangle$ با جمع تعدادی عدد، به حداقل ۱۱ عدد نیاز داریم. پس برای اینکه حداقل ۱۱ بازه داشته باشیم باید حداقل ۱۰ بار در قابلمه را برداریم.