مساله ۶۱. برش کیک

ده نفر‌ میخوان یکی کیک را بین خودشون تقسیم کنن. هر نفر یک قسمتایی از کیک را دوست داره و یه قسمت‌هایی را دوست نداره. هدف اینه که با ۹ حرکت چاقو طوری کیک را تقسیم‌ کنیم که هر نفر حداقل یک دهم قسمتایی که دوست داره بهش برسه. چطوری کیک را برش بدیم؟

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

لینک مساله در توویتر: https://twitter.com/Riazi_Cafe/status/1752242456505290950

الگوریتم این مسئله با عنوان "الگوریتم چاقوی متحرک" شناخته شده است.

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

این الگوریتم به دلیل زیر همه خواسته های ما را برآورده می‌کند: هر بار که کیک را به صورت عمودی برش می‌دهیم، هر یک از افراد حداکثر 1/10 قسمتی از کیک را که دوست دارد از دست می‌دهد (در غیر این صورت چاقو را زودتر متوقف می‌کردیم). بنابراین، این الگوریتم قسمت‌های مورد نظر کیک را به هر 10 نفر اختصاص می‌دهد.