$n$ پردازنده در اختیار داریم که بعضی درست و بعضی خراب هستند. دستگاه تست‌کننده‌ای در اختیار داریم که نحوه‌ی استفاده از آن به این شکل است: دو پردازنده‌ی دلخواه $A$ و $B$ را در دستگاه می‌گذاریم. $A$ و $B$ هر یک دیگری را تست می‌کنند و گزارش می‌دهد که آیا دیگری درست است یا خراب. گزارش یک پردازنده‌ی درست حتما صحیح است، ولی نمی‌توان به گزارش یک پردازنده‌ی خراب اعتماد کرد.

فرض کنید تعداد پردازنده‌های خراب کم‌تر از تعداد پردازنده‌های درست است.

1. مسئله‌ی پیدا کردن یک پردازنده‌ی درست از بین $n$ پردازنده را در نظر بگیرید. نشان دهید با $\lfloor \frac{n}{2} \rfloor$ بار استفاده از دستگاه تست‌کننده، می‌توان مسئله را به مسئله مشابه با تعداد پردازنده‌های تقریبا برابر $\frac{n}{2}$ تبدیل کرد به طوری که همچنان تعداد پردازنده‌های خراب کم‌تر از تعداد پردازنده‌های درست باشد.
2. با استفاده از قسمت قبل، نشان دهید می‌توان تمام پردازنده‌های درست را با $\Theta(n)$ بار استفاده از دستگاه تست‌کننده شناسایی کرد.

• سوال بعد
• سوال قبل