Profesor Diogenes ma \(\displaystyle{ n}\) przypuszczalnie identycznych układów scalonych, które w założeniu są zdolne testować się nawzajem. Urządzenie, którym dysponuje profesor, może sprawdzić jednocześnie dwa układy: każdy z nich sprawdza, czy drugi jest dobry. Dobry układ zawsze stwierdza poprawnie, czy drugi jest dobry, natomiast zły układ może dać dowolną (być może niepoprawną odpowiedź). Są możliwe zatem cztery następujące wyniki testu;
\(\displaystyle{ A}\) stwierdza, że \(\displaystyle{ B}\) dobry i \(\displaystyle{ B}\) stwierdza, że \(\displaystyle{ A}\) dobry, więc oba są dobre lub oba są złe.
\(\displaystyle{ A}\) stwierdza, że \(\displaystyle{ B}\) dobry i \(\displaystyle{ B}\) stwierdza, że \(\displaystyle{ A}\) zły, więc co najmniej jeden jest zły.
\(\displaystyle{ A}\) stwierdza, że \(\displaystyle{ B}\) zły i \(\displaystyle{ B}\) stwierdza, że \(\displaystyle{ A}\) dobry, więc co najmniej jeden jest zły.
\(\displaystyle{ A}\) stwierdza, że \(\displaystyle{ B}\) zły i \(\displaystyle{ B}\) stwierdza, że \(\displaystyle{ A}\) zły, więc co najmniej jeden jest zły.
Polecenie:
Wykaż, że jeśli jest co najmniej \(\displaystyle{ \frac{n}{2}}\) złych układów, to profesor nie zawsze może stwierdzić, które układy są dobre, opierając się na testach powyższego typu. Zakładamy, że złe układy mogą w pewnym sensie współdziałać, żeby oszukać profesora.