دنباله‌ای از اعداد طبیعی داریم. می‌خواهیم تعدادی رابطه بین اعداد این دنباله با شرایط زیر تعریف کنیم:

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

به یک عدد بدسگال گوییم، اگر در هیچ رابطه‌ای فرزند نباشد. هدف، تعریف تعدادی رابطه بین اعداد دنباله است، طوری که تعداد عددهای بدسگال کمینه شود. به‌عنوان مثال، اگر دنباله‌ی اعداد برابر $\langle 1,1,3,3,7,9 \rangle$ باشد، می‌توانیم به شکل زیر، رابطه‌ها را طوری تعریف کنیم که فقط یک عدد بدسگال داشته باشیم (هر پارەخط جهت‌دار نشانگر یک رابطه است که از پدر به فرزند کشیده شده است):

با توجه به توضیحات بالا به ۲ سوال زیر پاسخ دهید.

اگر دنباله‌ی اعداد برابر $\langle 1,1,1,1,1,2,2,2,2,3,3,3,4,4,5 \rangle$ باشد، حداقل چند عدد بدسگال خواهیم داشت؟

1. ۲
2. ۴
3. ۳
4. ۱
5. ۵

الگوریتم‌های زیر را در نظر بگیرید:

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

کدام الگوریتم‌ها به ازای هر دنباله‌ی اولیه‌ای از اعداد، کمترین تعداد بدسگال ممکن را ایجاد می‌کنند؟

1. ب و پ
2. آ و پ
3. هر سه
4. هیچ صدام
5. فقط پ

• سوال قبل