در این مسئله با تعدادی گیت سر و کار داریم. هر گیت یک یا چند ورودی و یک خروجی دارد. ورودی و خروجی یک گیت فقط مقادیر ۰ و ۱ است. سه نوع گیت $or،not$ و $and$ در اختیار داریم.

• گیت $and$ دو ورودی و یک خروجی دارد. خروجی آن ۱ است اگر و تنها اگر هر دو ورودی آن ۱ باشند.
• گیت $or$ دو ورودی و یک خروجی دارد. خروجی آن ۰ است اگر و تنها اگر هر دو ورودی آن ۰ باشد.
• گیت $not$ یک ورودی و یک خروجی دارد. اگر ورودی‌ آن ۱ باشد، خروجی آن ۰ و اگر ورودی آن ۰ باشد خروجی آن ۱ است.
• یک مدار شامل تعدادی گیت است که ورودی‌ها و خروجی‌های آن‌ها به هم متصل شده است!

مثلا شکل زیر یک مدار است.

1. در یک جعبه اندازه‌ی کافی گیت $and$ داریم. می‌دانیم حداکثر $k$‌ تا از این گیت‌ها خراب شده‌اند و مثل گیت $or$ عمل می‌کنند ($k$ یک عدد ثابت است). مداری طراحی کنید که کار گیت $and$ را انجام دهد. مدار شما باید دارای ۲ ورودی و ۱ خروجی باشد. به جز این دو ورودی هیچ مقدار دیگری در اختیار نداریم مگر اینکه با گیت‌های موجود در جعبه ساخته شود.
2. در یک جعبه به اندازه‌ی کافی گیت از هر سه نوع داریم. هر گیت برچسب مخصوص به خود را دارد. یعنی گیت‌ها ازهم متمایزند. حداکثر $k$ تا ا ز گیت‌ها خراب هستند و خروجی آن‌ها یکی از ورودی‌های آن‌ها به دل‌خواه است. مداری طراحی کنید که کار گیت $not$ را انجام دهد. توجه کنید که در هر دو قسمت این مسئله نمی‌دانیم کدام گیت‌ها خراب هستند!

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