‎$2k+1$‎ درخت ریشه‌دار با عمق حداکثر ‎$k$‎ داریم. ریشه‌های این درخت‌ها را به هم وصل می‌کنیم؛ طوری که این ریشه‌ها تشکیل یک دور ‎$2k+1$‎ رأسی بدهند. به چنین گرافی، ‎«خورشید»‎ می‌گوییم. با یک تعریف دیگر، یک گرافِ ‎«خورشید»‎ از یک دور ‎$2k+1$‎ رأسی ساخته می‌شود که هر رأس آن، ریشه‌ی یک درخت با عمق حداکثر ‎$k$‎ است. دقّت کنید که یک درخت می‌تواند تنها شامل یک رأس باشد‎!‎

در ابتدا، روی بعضی از رئوس این گراف‎ که برگ نیستند، یک مگس قرار دارد‎!‎ هر مگس در ابتدای هر ثانیه (به دلیل گرمای زیاد سطح خورشید!)‎ رأس خود را ترک کرده و به یکی از رئوس مجاور آن می‌رود. اما در انتهای هر ثانیه، در هر رأس حداکثر یک مگس قرار دارد. به‌طور مثال، دو مگس مجاور می‌توانند در طی یک ثانیه، جایشان را باهم عوض کنند.

یک ‎«وضعیت»، یک نحوه‌ی قرارگیری مگس‌ها روی رئوس گراف است به‌طوری که روی هر رأسِ غیربرگ، حداکثر یک مگس و روی برگ‌ها صفر مگس باشد. دو وضعیت ‎$A$‎ و ‎$B$ (با تعداد برابری مگس) به ما داده شده‌است. می‌خواهیم طوری مگس‌ها را برنامه‌ریزی کنیم که پس از مدت محدودی، از وضعیت ‎$A$‎ به وضعیت ‎$B$‎ برسند. می‌دانیم این‌کار (برای شرایط خواسته‌شده) امکان‌پذیر است. برای این کار روشی ارائه داده و آن را اثبات کنید؛ اگر

1. بدانیم تعداد کلّ مگس‌ها حداکثر ‎$2k$‎ تا است.
2. برای تعداد کلّ مگس‌ها شرطی وجود نداشته باشد، ولی بدانیم در هر یک از وضعیت‌های ‎$A$‎ و ‎$B$‎، تعداد مگس‌های روی دورِ فرد، حداکثر ‎$k$‎ تا است.

• سوال بعد
• سوال قبل