Processing math: 100%

المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی دوم:دوره ی ۲۴:سوال ۶

سوال ۶

جایگشت a1,a2,,an از اعداد 1,2,,n را «سه‌گریز n تایی» می‌گوییم هرگاه 1in وجود نداشته باشد که ij=1aj بر ۳ بخش‌پذیر باشد. تعداد جایگشت‌های سه‌گریز ۷ تایی و ۸ تایی به ترتیب (از راست به چپ) چند است؟

  1. ۳۶۰ و ۰
  2. ۴۸۰ و ۰
  3. ۳۶۰ و ۱۵۱۲
  4. ۴۸۰ و ۱۵۱۲
  5. ۴۸۰ و ۴۸۰

پاسخ

گزینه‌ی ۱ درست است.

برای n=۸ این مقدار برابر صفر است. زیرا جمع اعداد 1,,8 برابر ۳۶ است که بر ۳ بخش‌پذیر است. حال n=۷ را در نظر بگیرید. اگر فقط باقیمانده‌ی اعداد بر ۳ را نگاه کنیم. به این نتیجه میرسیم که جایگشت‌های 3‌گریز باید به صورت 1,1,2,1,2 باشند که اعداد مضرب ۳، یعنی ۳ و ۶ نیز در بین این‌ها (جایگشت نباید با ۳ و ۶ شروع شود) قرار گرفته‌اند. پس با تعیین ترتیب ۵ عدد دیگر،‌ 15×2 روش برای قرار دادن ۳ و ۶ داریم. از طرفی برای قرار دادن ۵ عدد دیگر نیز 3!×2! روش وجود دارد، یعنی در کل ۳۶۰ حالت برای n=۷ داریم.


ابزار صفحه