مسابقه شماره ۲۱۸
سوال
یک شرکت بشکه‌هایی از چهار ماده‌ی شیمیایی مختلف به نام‌ها A , B,C و D تولید و در انبارهای خود ذخیره می‌کند. این شرکت 4 انبار دارد که در هر انبار 4 بشکه از انواع A , B , C و D موجود است ( از هر ماده یک بشکه ). این مواد شیمیایی در صورتی که با هم مخلوط شوند , خطرناک هستند. به همین دلیل شرکت تصمیم دارد بشکه‌ها را بین این انبارها طوری جابجا کند که در نهایت هر انبار حاوی 4 بشکه از یک نوع ماده‌ی شیمیاییی باشد. برای این کار از یک کامیون استفاده می‌شود. این کامیون می‌تواند در هر بار جابجایی حداکثر 2 بشکه را از یک انبار به یکی دیگر از انبارهای شرکت انتقال دهد. حداقل با چند بار جابجایی می‌توان این کار را انجام داد؟
معلوم است که کامیون از انبار 1 که قرار است از حالت ABCD به حالت AAAA تبدیل شود, حداقل دوبار خارج و حداقل دوبار به آن انبار وارد خواهد شد. انبارهای 2, 3 و 4 نیز چنین وضعیتی را دارند. بنابراین حداقل جابجایی های لازم برابر 4+4+4+4 ÷ 2 یعنی 8 می‌باشد. اگر کامیون با الگوریتم زیر حرکت کند با 8 بار جابجایی می‌تواند به هدف برسد:
1.بشکه‌های BC را از انبار 1 به انبار 2 , منتقل کند.
2.بشکه‌های CC را از انبار 2 به انبار 3 , منتقل کند.
3.بشکه‌های BD را از انبار 3 به انبار 4 , منتقل کند.
4.بشکه‌های BB را از انبار 4 به انبار 2 , منتقل کند.
5.بشکه‌های AD را از انبار 2 به انبار 1 , منتقل کند.
6.بشکه‌های DD را از انبار 1 به انبار 4 , منتقل کند.
7.بشکه‌های AC را از انبار 4 به انبار 3 , منتقل کند.
8.بشکه‌های AA را از انبار 3 به انبار 1 , منتقل کند.