المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۹:تئوری:سوال ۸

برج هانوی رنگی

سه برج $B،A$ و $C$ داریم. $n$ دیسک با اندازه‌های متفاوت در برج $A$ قرار دارد که هر یک رنگ مشخصی دارد و از هر رنگ، حداکثر دو دیسک به آن رنگ وجود دارند. در ابتدا هیچ دو دیسک مجاوری هم‌رنگ نیستند و هر دیسک روی دیسک بزرگ‌تر از خود قرار دارد. می‌خواهیم با توجه به قواعد زیر این $n$ دیسک را به برج $C$‌منتقل کنیم (با استفاده از برج $B$):

  • هیچ‌گاه نباید دیسک با اندازه‌ی بزرگ‌تر روی دیسک با اندازه‌ی کوچک‌تر قرار بگیرد.
  • هیچ‌گاه نباید یک دیسک روی دیسک هم‌رنگ خود قرار بگیرد.

آیا با هر نوع آرایش اولیه‌ی رنگ‌ها، این کار امکان‌پذیراست؟


ابزار صفحه