اگر دو ورودی به دستگاه بدهیم که جواب یکی ۱ و دیگری ۱- باشد، باید حالت حافظه‌ی دستگاه بعد از خواندن دو ورودی متفاوت باشد. (چرا؟) یک دنباله‌ی $n$ تایی از ۱ و ۱- را خوب می‌نامیم اگر جمع عدد $2i$ ام و $2i-1$ ام آن ۰ شود. حال دستگاه باید برای هر دو عدد خوب حالت حافظه‌ی متفاوت داشته باشد.

در غیر این صورت فرض کنید دو عدد خوب $A$ و $B$ باشند که حالت حافظه‌ پس از خواندن آن‌ها یکسان است. آن‌قدر به دستگاه ۰ می‌دهیم که تا جایی که مثلا جواب $A$، ۱ شود و جواب $B$، ۱-. در این دو حالت، دستگاه حافظه‌ی یکسانی دارد که تناقض است. پس $2^{\frac{n}{2}}$ ورودی داریم که حالت حافظه به ازای آن‌ها متفاوت است. پس دستگاه حداقل $\frac{n}{2}$ بیت حافظه نیاز دارد.