المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۳

یک جدول $۵\times ۵$ را «منظم» می‌گوییم اگر و فقط اگر در هر خانه‌اش یک عدد نوشته شده باشد و در ۲۵ خانه‌اش همه‌ی اعداد ۱ تا ۲۵ آمده باشند. یک جدول $۵\times ۵$ را «خوش‌سطر» می‌گوییم اگر و فقط اگر حاصل ضرب ۵ عدد واقع در هر سطرش نه بر ۳۴ بخش‌پذیر باشد و نه بر ۳۸. به همین صورت یک جدول $۵\times ۵$ را «خوش‌ستون» می‌گوییم اگر و فقط اگر حاصل‌ضرب ۵ عدد واقع در هر ستونش نه بر ۳۴ بخش‌پذیر باشد و نه بر ۳۸. چند جدول مختلف $۵\times ۵$ منظم داریم که هم خوش‌سطر باشد و هم خوش‌ستون؟

  1. $۲۰۰ \times ۱۲! \times ۱۱!$
  2. !۲۵
  3. ۱۰
  4. $۱۲ \times ۱۰! \times ۱۳!$

پاسخ

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

عددی بر ۳۴ بخش‌پذیر است که بر ۱۷ و ۲ بخش‌پذیر باشد و نیز عددی بر ۳۸ بخش‌پذیر است که بر ۱۹ و ۲ بخش‌پذیر باشد. اگر در جدول $5\times5$، دو عدد ۱۷ و ۱۹ هم‌سطر و یا هم‌ستون نباشند٬ آن‌گاه منظم کردن آن جدول غیر ممکن است زیرا مجموع تعداد کل خانه‌هایی که حداقل با یکی از آن دو عدد هم‌سطر و یا هم ستون هستند برابر ۱۴ می‌باشد که برای منظم شدن آن جدول لازم است هر یک از آن ۱۴ خانه عددی فرد باشد٬ در حالی که تعداد اعداد فرد باقی‌مانده برابر ۱۱ می‌باشد. و اما اگر در جدول $5\times5$، دو عدد ۱۷ و ۱۹ هم‌سطر و هم‌ستون باشند(که این کار به ۲۰۰ طریق ممکن است٬ زیرا عدد ۱۷، ۲۵ انتخاب و سپس عدد ۱۹، ۸انتخاب در پیش روی خود دارند)٬ آن‌گاه مجموع تعداد کل خانه‌هایی که حداقل با یکی از آن دو عدد هم‌سطر و یا هم‌ستون هستند برابر ۱۱ می‌باشد(در جدول مقابل آن خانه‌ها با $\bigcirc$ نشان داده شده‌اند) که پر کردن آن ۱۱ خانه با۱۱ عدد فرد به !۱۱ طریق ممکن است. پر کردن ۱۲ خانه باقی‌مانده با ۱۲ عدد زوج نیز به !۱۲ طریق انجام می‌شود که در کل جواب مورد نظر $8\times25\times11!\times12!$ به‌دست می‌آید.


ابزار صفحه