المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۷

جایگشت $a_1, a_2,..., a_n$ از اعداد $1, 2 ,..., n$ را «سه‌گریز پیشرفته‌ی $n$تایی» می‌گوییم هرگاه دو شرط زیر را داشته باشد:

  • $1\leq i\leq n$ وجود نداشته باشد که $\sum _{j=1}^i a_j$ باقی‌مانده‌اش بر ۳ برابر یک باشد.
  • جمع هر ۶ عدد متوالی بر ۳ بخش‌پذیر باشد.

تعداد جایگشت‌های سه‌گریز پیشرفته‌ی ۹تایی چند است؟

  1. $9 \times 3!^3$
  2. $4 \times 3!^3$
  3. $8 \times 3!^3$
  4. ۰
  5. $27 \times 3!^3$

پاسخ

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

با استفاده از این نکته که جمع هر ۶ عدد متوالی بر ۳ بخش‌پذیر است، به راحتی مشاهده می‌شود که باقی‌مانده‌ی عدد عدد اول، دوم و سوم بر ۳ به ترتیب با باقی‌مانده‌ی عدد هفتم، هشتم و نهم برابر است. از طرفی اگر فقط باقی‌مانده‌ی اعداد ۳ را در نظر بگیریم، از گزاره‌ی قبل به این نتیجه می‌توان رسید که ۳ تایی اول، دوم هرکدام یک جایگشت از اعداد ۰ تا ۲ هستند و ۳ تایی سوم با سه تایی اول برابر است. علاوه بر این با استفاده از خاصیت اول این جایگشت‌ها به این نتیجه می‌رسیم که ۳ رقم اول و دوم هر کدام باید به یکی از سه شکل $2,0,1$، $2,1,0$ و $0,2,1$ باشند. پس در کل فقط با در نظر گرفتن باقی‌مانده‌ها ۹ حالت داریم. از طرفی برای هر کدام از ارقام $0,1,2$، $3!$ حالت برای ترتیب اعداد با آن باقی‌مانده داریم. پس تعداد جایگشت‌های کلی برابر $9\times 3!^3$ است.


ابزار صفحه