المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی دوم:دوره ی ۳۲:سوال ۱۰

سوال ۱۰

به یک جایگشت از اعداد ۱ تا ۱۰ ملایم می‌گوییم اگر حاصل ضرب هر دو عدد متوالی در جایگشت، حداکثر ۳۰ شود. چند جایگشتِ ملایم از اعداد ۱ تا ۱۰ داریم؟

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

راهنمایی

به طور معمول، اگر بخواهیم اعداد $k$ رقمی با ارقام متمایز را با روش‌های شمارش بشماریم، ابتدا رقم اول از سمت چپ را تعیین می‌کنیم. چون این رقم دارای شرایط خاصی است و نبايد صفر باشد، بهتر است ابتدا مقدار این رقم را مشخص کنیم و از حالت‌های باقی ارقام حذف کنیم. سپس مقادیر باقی ارقام را تعیین کنیم. در این سوال نیز بهتر است برای مشخص کردن جایگشت‌ها، ترتیب و روشی برای چیدن اعداد در جایگشت تعیین کنیم به طوری که:

  • جایگشت تکراری ایجاد نشود.
  • هر جایگشت یک بار شمرده شود.
  • در هر مرحله بتوان تعداد حالت‌های ممکن برای جایگاه یکی از اعداد را با کمترین پیچیدگی و حالت‌بندی محاسبه کرد.

برای طراحی این ترتیب و روش، سعی کنید از خواص کوچک‌ترین و بزرگ‌ترین عدد استفاده کنید.

راهنمایی

به جای این که برای اعداد $10$ جایگاه در نظر بگیرید و در هر مرحله یک عدد را در یک جایگاه بگذارید، فرض کنید در هر مرحله تعدادی از اعداد را در یک ردیف داریم و می‌خواهیم عدد جدیدی را میان اعداد قبلی (و یا اول و آخر ردیف) قرار دهیم. همچنین سعی کنید اعداد را طوری درج کنید که در هر مرحله، اعدادی که در یک ردیف قرار گرفته‌اند، شرایط سوال را حفظ کنند تا در مرحله آخر نیز اطمینان داشته باشیم که شرایط مطلوب برقرار است.

راهنمایی

ثابت کنید روش زیر مطلوب است. به بیان دیگر نشان دهید که روش زیر همه‌ی جایگشت‌های مطلوب را می‌سازد و هر جایگشت نیز دقیقا یک بار ساخته می‌شود.

دنباله‌ی اعداد $S$، در ابتدا یک دنباله‌ی خالی است. سپس به روش زیر پر می‌شود:

در هر مرحله، عددی را که قرار است به $S$ اضافه شود با این قاعده انتخاب می‌کنیم:

  • اگر یک عدد باقی‌مانده (به $S$ اضافه نشده) بود، همان عدد را انتخاب می‌کنیم.
  • اگر حاصل‌ضرب کوچک‌ترین و بزرگ‌ترین اعداد باقی‌مانده از $30$ بیشتر بود، عدد بزرگ‌تر را برای اضافه کردن به $S$ انتخاب می‌کنیم.
  • اگر حاصل‌ضرب کوچک‌ترین و بزرگ‌ترین اعداد باقی‌مانده کمتر یا مساوی با $30$ بود، عدد کوچک‌تر را برای اضافه کردن به $S$ انتخاب می‌کنیم.

راهنمایی

در روش ارائه شده در راهنمایی قبل، اعداد به چه ترتیبی به $S$ اضافه می‌شوند؟ عدد اضافه شده در هر مرحله چه نسبتی (بزرگ‌تر، کوچک‌تر یا مساوی) با اعداد قبلی دارد؟

راهنمایی

در روش ارائه شده در راهنمایی قبل، در هر مرحله، اعداد استفاده شده در $S$ را می‌توان به دو دسته‌ی اعدادی که زمانی که اضافه شدند، کوچک‌ترین عدد بودند و اعدادی که زمانی که اضافه شدند، بزرگ‌ترین عدد بودند تقسیم کرد. نسبت اعداد هر یک از این دسته‌ها را با عددی که در این مرحله قرار است به $S$ اضافه شود، بررسی کنید. سپس به کمک این نسبت تعداد حالت‌های ممکن برای درج عدد جدید را به دست آورید.


ابزار صفحه