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

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

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

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