المپدیا

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

ابزار کاربر

ابزار سایت


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

سوالات ۱۸ و ۱۹ و ۲۰

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

  • یک مملی با دو کروموزوم آسیب دیده، ایدز دارد.
  • یک مملی که کروموزوم آسیب دیده نداشته باشد، ایدز ندارد.
  • وضعیت در مورد مملی هایی که دقیقا یک کروموزوم آسیب دیده دارند مشخص نیست، ولی می‌دانیم یا همه آنها ایدز دارند ( که در این صورت به بیماری ایدز فراگیر می گوییم ) و یا هیچ کدام ایدز ندارند.

جدول موروثی دو مملی، جدولی $2 \times 2$ می باشد که هر سطر آن مربوط به یک کروموزوم از مملی اول و هر ستون آن مربوط به یک کروموزوم از مملی دوم است. در هر خانه از جدول، وضعیت ایدز داشتن یا نداشتن فرزندی که از کروموزوم های متناظر سطر و ستونش ساخته می شود، نوشته می شود. به راحتی می توانید بررسی کنید که دو جدول موروثی زیر، نامعتبر و غیر ممکن هستند. ( علامت ✓ به معنی داشتن ایدز و علامت ✕ به معنی نداشتن ایدز است ) : بنابراین در کل $2^4-2=14$ جدول موروثی ممکن وجود دارد.

سوال ۱۸

دو مملی با هم ازدواج کرده و چهار فرزند مختلف به وجود آورده‌اند. به ما گفته اند دقیقا $k$ تا از این فرزند ها ایدز دارند. ما هیچ اطلاعات دیگری مانند این که والدین ایدز دارند یا خیر نداریم. به ازای چند مقدار $k$ از $0$ تا $4$ می توانیم متوجه شویم ایدز یک بیماری فراگیر است یا خیر؟

  1. $1$
  2. $5$
  3. $3$
  4. $2$
  5. $0$

پاسخ

سوال ۱۹

فرض کنید $A$ و $B$ دو مملی با جدول موروثی $T$ باشند. فرض کنید وضعیت ایدز داشتن یا نداشتن $A$ و $B$ را نمی دانیم. اگر با استفاده از جدول $T$ بتوانیم وضعیت ایدز داشتن یا نداشتن هر دو $A$ و $B$ را بفهمیم، دو امتیاز می گیریم؛ اگر بتوانیم فقط وضعیت ایدز داشتن یا نداشتن یکی از آنها را بفهمیم، یک امتیاز می گیریم و اگر هم هیچ کدام را نتوانیم بفهمیم امتیازی نمی گیریم. تمام $14$ حالت $T$ را در نظر بگیرید. در مجموع این حالات، چند امتیاز می توانیم بگیریم؟

  1. $16$
  2. $8$
  3. $20$
  4. $0$
  5. $28$

پاسخ

سوال ۲۰

سلطان دستگاهی ساخته که دو مملی از ورودی می گیرد و جدول موروثی آن‌ها را تحویل می دهد ( حتی اگر دو مملی ازدواج نکرده باشند، با فرض ازدواج آنها جدول را می سازد ). فرض کنید $A$ و $B$ دو مملی با چهار فرزند مختلف و جدول موروثی $T$ باشند. به ازای هر دو فرزند از $A$ و $B$ آن ها را به دستگاه می دهیم و یک جدول تحویل می گیریم. فرض کنید می‌دانیم هر خانه از $T$ مربوط به کدام فرزند است. به ازای چند حالت از $T$، با استفاده از $\binom 42$ جدول موروثی دستگاه و همچنین خود $T$ می توانیم فراگیر بودن یا نبودن ایدز را تشخیص دهیم؟

  1. $2$
  2. $10$
  3. $0$
  4. $8$
  5. $14$

پاسخ


ابزار صفحه