المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۶

جایگشت $a_1,a_2,\ldots,a_n$ از اعداد $1,2,\ldots,n$ را «سه‌گریز $n$ تایی» می‌گوییم هرگاه $1\leq i\leq n$ وجود نداشته باشد که $\sum _{j=1}^i a_j$ بر ۳ بخش‌پذیر باشد. تعداد جایگشت‌های سه‌گریز ۷ تایی و ۸ تایی به ترتیب (از راست به چپ) چند است؟

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

پاسخ

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

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


ابزار صفحه