تقسیم کیک بین ۳ نفر

سوال این بود که می‌خواهیم یک کیک را بین ۳ نفر تقسیم کنیم و این کار را فقط با سه تا برش انجام بدهیم.

یک راه حل برای این بود که تعداد برشهایش نامتناهی بود. من فکر کردم روی مسأله و دیدم بهتر از این نمی‌شود چون به تابع علاقه‌ی افراد به قسمت‌های مختلف کیک بستگی دارد.

حل من:

اگر هر فردی که به مقدار ۱/۳ و ۲/۳ می‌رسد اعلام کند و نفر اولی که اعلام می‌کند با A و نفر دومی که اعلام می‌کند با B و فرد دیگر را با C نشان بدهیم، ترتیب‌های مختلف به صورت زیر است:

۱) یک حرف تکرار شود: در این صورت یک نفر ۲/۳ کیک را طی کرده است در حالی که بقیه به ۱/۳شان هم نرسیده‌اند. در این صورت قسمت مورد نظر این فرد را به او می‌دهیم. (شکل اول)

۲) یک حرف با یک فاصله تکرار شود. (شکل دوم). در این صورت یک دور به وجود می‌آید (چون حرف تکراری نداریم). مثلاً ABACBC. در این حالت باید مبدأ را عوض کنیم وگرنه هیچ برشی وجود ندارد و این عوض کردن مبدأ هم به تابع آن بستگی دارد.

۳) ABCABC: کیک را از روی اعلامهای B می‌بریم. فرد A قسمت اول، فرد C قسمت آخر و فرد B قسمت وسط را می‌گیرند.

این قسمت را غلط حل کردم! چون از نظر A قسمت اول از ۱/۳ بیشتر و قسمت آخر از ۱/۳ کمتر است، در نتیجه قسمت دوم می‌تواند از قسمت اول کمتر یا بیشتر باشد. از نظر نفر سوم برعکس است، یعنی قسمت آخر از ۱/۳ بیشتر، قسمت اول از ۱/۳ کمتر است و ممکن است قسمت دوم از همه بزرگتر باشد. در نتیجه در حالتی که A و C هر دو بگویند که قسمت وسط بیشتر از همه است به مشکل برمی‌خورد.

مرجع سوال: ارائه‌ی الگوریتم در مورد cake cutting