یک جایگشت از اعداد ۱ تا $n$ یک لیست از اعداد ۱ تا $n$ است که هر عدد $\underline{ دقیقا}$ یک بار در آن ظاهر شده است. برای مثال <۱٬۵٬۳٬۴٬۲> یک جایگشت از اعداد ۱ تا ۵ است.
رنگ آمیزی معتبر برای یک جایگشت٬ رنگآمیزی است که شرایط زیر را داشته باشد:
عدد رنگی یک جایگشت برابر است با حداقل تعداد رنگ های متفاوتی که برای رنگ آمیزی معتبر اعداد آن جایگشت لازم است.
با توجه به توضیحات بالا به ۳ سوال زیر پاسخ دهید:
عدد رنگی جایگشت <۱٫۵٫۲٫۴٫۶٫۳> چند است؟
در میان تمام جایگشت های اعداد ۱ تا ۶ عدد رنگی چند جایگشت برابر با ۲ است؟
پاسخ
گزینهی ۵ درست است.
در صورتی عدد رنگی جایگشت ۲ خواهد بود که اعداد زوج به یک رنگ و اعداد فرد به رنگ دیگر باشند. در این صورت باید در جایگاههای زوج و در جایگاههای فرد رنگهای متمایزی باشند. در نتیجه اعداد زوج در یکی از این جایگاهها و اعداد فرد در جایگاه دیگر باشند. پس تعداد این حالات برابر خواهد بود با:
$$2×(3!)^2=72$$
بیشترین عدد رنگی بین همه جایگشت های اعداد ۱ تا ۷ چند است؟
پاسخ
گزینهی ۴ درست است.
اگر به ترتیب از ابتدای جایگشت رنگآمیزی کنیم، هر عدد یک همسایه قبل از خود دارد و دو عدد که با آن حداکثر یک واحد اختلاف دارند. پس اگر ۴ رنگ داشته باشیم، همواره میتوان اعداد را رنگ کرد.
برای مثال زیر نیز حداقل ۴ رنگ مورد نیاز است:
$$<2,4,1,3,5,6,7>$$