المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۱۳

حداکثر چندتا از دایره‌های شکل مقابل را می‌توان پر کرد به طوری که هیچ چهار دایره‌ی پر شده‌ای رئوس یک مربع یا مستطیل با اضلاع افقی و عمودی نباشند؟

  1. ۶
  2. ۷
  3. ۸
  4. ۹
  5. ۱۰

پاسخ

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

اگر ستونی هر سه دایره‌اش پر باشد دراین صورت واضح است که از هر کدام از چهار ستون دیگر فقط یکی از دایره‌هایشان می‌تواند پر باشد زیرا در غیر این صورت مربع یا مستطیل با چهار راس پر پیدا خواهد شد. دراین صورت $4\times2$ دایره سفید موجود خواهد بود که معلوم می‌شود ۷ دایره‌ی پر وجود دارد. و اما اگر هیچ ستونی هر سه دایره‌اش پر نباشد در این صورت یکی از ستون‌ها (مثلا اول) که دو دایره‌اش پر می‌‌باشد را در نظر می‌گیریم. به عنوان مثال فرض می‌کنیم دو سطر اول ستون اول پر باشند بدیهی است که در چهار ستون دیگر دو سطر اول و دوم تواما نباید پر باشند و همچنین از ۴ دایره‌ی مربوط به سطر آخر چهار ستون پایانی حداکثر ۲ دایره می‌تواند پر باشد. پس کل دایره‌های پر $2+4+2$ یعنی ۸ دایره می‌تواند باشد که نمونه‌ای از آن در شکل زیر نمایان است:


ابزار صفحه