بیل گیتس و مسئله پنکیک‌ها

اما مسئله کیک‌ تابه‌ای اصلا چیست؟

این معمای فکری جالب از ما می‌خواهد کیک‌های تابه‌ای را به ترتیب اندازه‌ طوری روی هم بچینیم که بزرگ‌ترین کیک پایین‌تر از همه قرار بگیرد و در طبقات بالاتر کیک‌های کوچک‌تر جای داشته باشند. به‌این ترتیب، بزرگ‌ترین کیک در پایین و کوچک‌ترین کیک در بالای ستون کیک‌ها جای خواهندگرفت.  

سه بازی زیر را که از دل همین مسئله بیرون آمده است ببینید:

بازی اول با 3 کیک:

بازی دوم با 4 کیک:

بازی سوم با 7 کیک:

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

منظور از حرکت در مسئله پنکیک‌ها چیست؟

هر بار که کف‌گیر را در ستون کیک‌های روی هم چیده شده وارد می‌کنید، باید همه کیک‌های بالای کف‌گیر را با هم بر‌دارید و سپس کف‌گیر را سریع و ماهرانه با کیک‌هایش رو به پایین بر‌گردانید و روی ستون اصلی کیک‌ها بچینیدشان. همه این‌ کارها با هم یک حرکت محسوب می‌شود. (به شکل زیر توجه کنید)

نسخه اصلی مسئله پنکیک‌ها

برای کمک به حل معما، نسخه اصلی مسئله پنکیک‌ها را نیز که در سال 1975 مطرح شده بود، ذکر می‌کنیم. در این مسئله خدمت‌کاری به نام هری دی‌ویتر، چند پنکیک‌ در دست از آشپزخانه خارج می‌شود. حداکثر با چند حرکت می‌توان کیک‌ها را بر حسب اندازه‌‌شان مرتب کرد؟

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

اگر 3 پنکیک‌ داشته باشید، در بدترین حالت 3 حرکت لازم است تا کیک‌ها به ترتیب خواسته شده روی هم چیده شوند؛ اگر کیک‌ها 7 عدد شوند حداکثر 8 حرکت لازم خواهیدداشت؛ برای مرتب کردن 11 کیک به 13 حرکت نیاز دارید (در این‌جا برای محاسبه تعداد حرکات، کامپیوتر لازم است)؛ اگر کیک‌ها 19 عدد شوند 22 حرکت لازم دارید؛ و بالاخره اگر 20 کیک داشته باشید کسی نمی‌داند چند حرکت برای مرتب کردن آن‌ها لازم است! شاید 23 حرکت لازم باشد، یا 24 حرکت، یا شاید حتی 25 حرکت... محاسبه تمام جایگشت‌های کیک‌ها و راهبردهای لازم برای حرکت دادن آن‌ها، کار سختی است و با گذشت چهار دهه از انقلاب رایانش، یافتن راه‌حل آن حتی با قدرتمندترین کامپیوترهای امروزی نیز ممکن نیست. تنها چیزی که (تقریبا سریع) بدان دست یافتیم، حد بالای تعداد حرکات لازم برای مرتب‌سازی کیک‌ها بود.

روش گیتس در مواجهه با مسئله پنکیک یا کیک تابه‌ای

مطالعه‌ای که در سال 1979 صورت گرفت نشان داد که تعداد جابه‌جایی‌های لازم در ستونی متشکل از n کیک همیشه کمتر از 5n+5)/3) است. یعنی مثلا اگر 20 کیک با اندازه‌های متفاوت داشته باشید که تصادفی رو هم چیده شده‌اند، در بدترین حالت به بیش از 33 حرکت احتیاج نخواهیدداشت. این مقاله را کریستوس اچ. پاپادیمیترو و ویلیام اچ. گیتس نوشته بودند. بله، همان بیل گیتسی که مایکروسافت را تاسیس کرده است. تقریبا 30 سال پس از آن‌ها گروهی از محققان دانشگاه تگزاس دالاس در سال 2008 بر راه‌کار پاپادیمیترو و گیتس پیشی گرفتند. آن‌ها بالاترین حد را 18n/11 تعیین کردند.

بنابراین، تا به‌این‌جا اطمینان حاصل شده است که برای مرتب کردن 20 کیک طبق خواسته هری دی‌ویتر، 32 حرکت کافی است.  

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

در پایان، راه‌حل سه بازی مطرح شده در اوایل مقاله را مشاهده می‌کنید:

بازی اول: اگر 3 کیک داشته باشید در بدترین حالت با 3 حرکت می‌توانید آن‌ها را مرتب کنید. شکل زیر را ببینید:

بازی دوم: اگر 4 کیک داشته باشید در بدترین حالت با 4 حرکت می‌توانید آن‌ها را مرتب کنید. شکل زیر را ببینید:

بازی سوم: اگر 7 کیک داشته باشید در بدترین حالت با 8 حرکت می‌توانید آن‌ها را مرتب کنید. شکل زیر را ببینید: