المپدیا

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

ابزار کاربر

ابزار سایت


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

سوالات ۲۸ تا ۳۰

باکتری فلاجلا به هنگام تولید مثل به سه باکتری تقسیم شده و خودش از بین می‌رود. به باکتری‌ای که تولید مثل می‌کند، والد و به سه باکتری به وجود آمده، فرزندان او می‌گوییم. ممکن است یک باکتری قبل از تولید مثل بمیرد که در این صورت به سرعت تجزیه شده و اثری از او باقی نمی‌ماند.

مدت‌ها پیش، سلطان یک باکتری فلاجلا به نام آر.بی.جی خرید و آن را در قفس نگه‌داری می‌کرد! پس از مدتی این باکتری از بین رفته است، اما قفس تعدادی باکتری دارد که طبیعتاً از نوادگان آر.بی.جی هستند. سلطان دل‌ش برای آر.بی.جی تنگ شده و می‌خواهد ژن آر.بی.جی را بازیابی کند. زیست‌شناسان به تکنولوژی‌ای دست پیدا کرده‌اند که با استفاده از ژن دو تا از فرزندان یک باکتری والد، می‌توانند ژن او را بازیابی کنند.

فرض کنید تعداد باکتری‌های درون قفس $n$ باشد. به یک وضعیت بحرانی گوییم، اگر بتوانیم ژن آر.بی.جی را بازیابی کنیم، اما در این بازیابی به همه‌ی $n$ باکتری نیاز داشته باشیم.

سوال ۲۸

در این سوال فرض کنید نتایج تحقیقات این باشد که هیچ کدام از فرزندان آر.بی.جی و فرزندان فرزندان او در قفس نیستند. در بین تمام حالات ممکن که امکان بازیابی ژن آر.بی.جی وجود دارد، کمینه‌ی تعداد باکتری‌های درون قفس چیست؟

  1. ۴
  2. ۶
  3. ۹
  4. ۸
  5. ۷

پاسخ

گزینه‌ی ۴ درست است.

دست کم به ژن دو فرزند آر.بی‌جی نیاز داریم. هر فرزند نیز دست کم به ژن دو فرزندش نیاز دارد. هر کدام از آن‌ها نیز دست کم ژن دو فرزندشان را می‌خواهند. پس دست کم $2 \times 2 \times 2 = 8$ باکتری نیاز است. روش ممکن با ۸ باکتری نیز مشابه استدلال گفته شده به دست می‌آید.

سوال ۲۹

به ازای چند $n$ از ۲ تا ۱۰ می‌توان وضعیتی بحرانی با $n$ باکتری درون قفس داشت؟

  1. ۱
  2. ۲
  3. ۵
  4. ۷
  5. ۹

پاسخ

گزینه‌ی ۵ درست است.

برای تمام $n$ ها ممکن است. برای ۲ باکتری که وضعیت واضح است (تنها ژن دو فرزند آر.بی.جی موجود باشد). فرض کنید برای $n$ باکتری ممکن باشد. برای $n+1$ باکتری کافی است یک باکتری بدون فرزند (برای مثال جوان‌ترین باکتری!) را در نظر گرفته و به جای او، دو فرزند از او در قفس بگذاریم. پس با استقرا ثابت می‌شود تمام $n$ ها ممکن است.

سوال ۳۰

کدام گزاره یا گزاره‌های زیر درست هستند؟

آ)وضعیتی با شش باکتری درون قفس وجود دارد که با استفاده از هر پنج باکتری می‌توانیم ژن آر.بی.جی را بازیابی کنیم، اما چهار باکتری وجود دارند که نمی‌توان فقط با استفاده از آن‌ها ژن آر.بی.جی را بازیابی کرد.

ب)وضعیتی با چهار باکتری درون قفس وجود دارد که به ازای هر دو باکتری، با استفاده از فقط همان دو باکتری می‌توان ژن آر.بی.جی را بازیابی کرد.

ج)وضعیتی بحرانی با پنج باکتری وجود دارد که هر باکتری فرزند یا فرزند فرزند آر.بی.جی باشد.

  1. آ
  2. آ و ج
  3. آ و ب
  4. ب و ج
  5. ب

پاسخ

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

  • گزاره‌ی (آ) صحیح است. فرض کنید از هر فرزند آر.بی.جی دو فرزند در قفس باشند و باکتری دیگری نیز نباشد.
  • گزاره‌ی (ب) صحیح نیست. اگر با استفاده از فقط دو باکتری بتوان ژن آر.بی.جی را شناسایی کرد باید آن دو، فرزندان آر.بی.جی باشند. پس گزاره ممکن نیست.
  • گزاره‌ی (ج) صحیح نیست. اثبات با بررسی حالات انجام می‌شود.

ابزار صفحه