المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۸

یک شبکه ‎$n \times n$‎ مجموعه نقاطی از صفحه است که دارای مختصات صحیح هستند و هر یک از مختصات آن‌ها عددی بزرگ‌تر یا مساوی با ‎۱‎ و کوچک‌تر یا مساوی با ‎$n$‎ است. یک زیرمجموعه از نقاط یک شبکه را یک مجموعه‌عجیب می‌نامیم اگر در بین تمام پاره خط‌هایی که می‌توان بین دو به دوی آن‌ها کشید هیچ دو تایی دارای طول مساوی نباشند. به عنوان مثال شکل زیر یک مجموعه عجیب در شبکه ‎$3 \times 3$‎ را نشان می‌دهد:

  1. در یک شبکه ‎$4 \times 4$‎ یک مجموعه عجیب شامل ‎۴‎ نقطه پیدا کنید.
  2. ثابت کنید که در هر شبکه ‎$n \times n$‎ هر مجموعه عجیب حداکثر دارای ‎$n$‎ نقطه است.

پاسخ


ابزار صفحه