المپدیا

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

ابزار کاربر

ابزار سایت


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

سوالات ۲۹ و ۳۰

باستان‌شناسان به تازگی روی سنگ‌های یک غار اشکالی از شجره‌نامه‌های یک قبیله‌ی باستانی یافته‌اند که نشان می‌دهد این قبیله در بچه‌دار شدن رسومات عجیبی داشته‌اند. در این قبیله اگر یک پدر $k$ پسر داشته باشد، پسر بزرگ‌تر خانواده $k-1$ پسر به دنیا می‌آورد، پسر دوم خانواده $k-2$ پسر و همین طور تا پسر کوچک خانواده که هیچ پسری به دنیا نمی‌آورد و نباید پسردار شود. در شکل روبه‌رو شجره‌نامه‌ی یک خاندان از این قبیله را می‌بینید که جد بزرگ آن‌ها دارای سه پسر بوده است. در این شکل پسران به ترتیب سن از چپ به راست قرار دارند (از بزرگ به کوچک). توجه داشته باشید که در این شجره‌نامه‌ها تنها اطلاعات مردان فامیل می‌آمده است.

سوال ۲۹

در یکی از شجره‌نامه‌ها که روی سنگ‌ها یافت شده است، مشخص است که جد بزرگ خاندان ۱۰ پسر داشته است، اما اطلاعات مربوط به پسر سوم جد بزرگ بر اثر مرور زمان مخدوش شده است. با استفاده از اطلاعات فوق دانشمندان می‌خواهند بدانند تعداد مردان در خاندانی که جد بزرگش این پسر بوده، چند است؟

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

سوال ۳۰

فاصله‌ی فامیلی دو فرد در یک شجره‌نامه را طول مسیری که باید روی شجره‌نامه طی کرد تا از یک فرد به فرد دیگر رسید تعریف می‌کنیم. به عنوان مثال فاصله‌ی فامیلی یک فرد با پدرش یک، با پدربزرگش دو و با عمویش سه است. حال در یک خاندان که جد بزرگش ۱۰۰ پسر دارد، فاصله‌ی فامیلی چند جفت از افراد در این خاندان برابر با ۱۹۸ می‌باشد؟ (جفت‌های $(a,b)$ و $(b,a)$ در شمارش تفاوتی ندارند و یک بار شمرده می‌شوند.)

  1. ۱۹۷
  2. ۱۹۸
  3. ۴
  4. ۵
  5. ۱۰۰

ابزار صفحه