یک میز چرخان مربع شکل را در نظر بگیرید که در هر یک از چهارگوشه‌ی آن‌ یک عدد لیوان قرار دارد. هر لیوان یا رو به بالا (U) است یا رو به پایین (∩). «محمد» که چشمانش بسته است، می‌خواهد با توجه به قواعد زیر با حداقل تعداد «حرکت» همه‌ی لیوان‌ها را یا رو به بالا کند و یا همه را رو به پایین. این کار زیر نظر یک داور انجام می‌شود. هر حرکت شامل همه‌ی مراحل زیر است که به ترتیب اجرا می‌شوند:

۱) داور میز را به‌دلخواه می‌چرخاند تا هر لیوانی که بخواهد در گوشه‌ی مورد نظرش قرار گیرد.

۲) محمد دو گوشه‌ی میز را انتخاب می‌کند. اگر این دو گوشه دو سر یک ضلع مربع باشند آن‌ها را گوشه‌های مجاور و اگر دو سر یک قطر باشند آن‌ها را گوشه‌های روبه‌رو می‌گوییم.

۳) محمد دو لیوان در گوشه‌های انتخابی را لمس می‌کند و می‌فهمد که هر یک رو به بالاست یا رو به پایین.

۴) محمد با برعکس کردن تعدادی (شاید هیچ کدام) از این دو لیوان آن دو را به هر صورتی که لازم ببیند درمی‌آورد.

۵) داور به محمد می‌گوید که آیا همه‌ی لیوان‌ها هم‌جهت هستند یا خیر. اگر هم‌جهت باشند که محمد موفق شده است و کار تمام است، وگرنه باید حرکت بعدی را انجام دهد.

آیا محمد می‌تواند با تعداد محدودی حرکت این کار را انجام دهد؟ در صورتی‌ که جواب شما منفی است آن را اثبات کنید. برای جواب مثبت، حداقل تعداد حرکت‌ها را به دست آورید و نشان دهید که آن تعداد حرکت کمینه است.

نکته‌ی مهم: برای بیان استدلال یا الگوریتم خود حتماً از نمادهای∩،Uو یا ?استفاده کنید و وضعیت لیوان‌ها را به‌صورت دنباله‌ی چهارتایی از این نمادها نشان دهید. مثلا در ابتدا وضعیت ????است، یعنی محمد نمی‌داند که لیوان‌ها در چه وضعی قرار دارند. اگر او در اولین حرکت دو لیوان مجاور را رو به پایین کند، وضعیت به‌صورت ??∩∩، ?∩∩?، ∩∩?? یا ∩??∩ درمی‌آید و اگر وضعیت مثلاً ?U∩? باشد و او دو لیوان روبه‌رو را به سمت بالا درآورد وضعیت به‌صورت ?U∩U یا UUU? درمی‌آید.

• سوال بعد