سوال ۶
جایگشت $a_1,a_2,\ldots,a_n$ از اعداد $1,2,\ldots,n$ را «سه‌گریز $n$ تایی» می‌گوییم هرگاه $1\leq i\leq n$ وجود نداشته باشد که $\sum _{j=1}^i a_j$ بر ۳ بخش‌پذیر باشد. تعداد جایگشت‌های سه‌گریز ۷ تایی و ۸ تایی به ترتیب (از راست به چپ) چند است؟
- ۳۶۰ و ۰
- ۴۸۰ و ۰
- ۳۶۰ و ۱۵۱۲
- ۴۸۰ و ۱۵۱۲
- ۴۸۰ و ۴۸۰
پاسخ
گزینه‌ی ۱ درست است.
برای n=۸ این مقدار برابر صفر است. زیرا جمع اعداد $1,\ldots,8$ برابر ۳۶ است که بر ۳ بخش‌پذیر است. حال n=۷ را در نظر بگیرید. اگر فقط باقیمانده‌ی اعداد بر ۳ را نگاه کنیم. به این نتیجه میرسیم که جایگشت‌های 3گریز باید به صورت $1,1,2,1,2$ باشند که اعداد مضرب ۳، یعنی ۳ و ۶ نیز در بین این‌ها (جایگشت نباید با ۳ و ۶ شروع شود) قرار گرفته‌اند. پس با تعیین ترتیب ۵ عدد دیگر، $15 \times 2$ روش برای قرار دادن ۳ و ۶ داریم. از طرفی برای قرار دادن ۵ عدد دیگر نیز $3! \times 2!$ روش وجود دارد، یعنی در کل ۳۶۰ حالت برای n=۷ داریم.
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
