حمید میخواهد یک دستگاه بامزه طراحی کند. هر دستگاه بامزه این خصوصیات را دارد:
عدد 0≤e≤1 روی آن نوشته شده زیر آن عدد N نوشته شده یک دریچه ورودی دارد که از آن دریچه اعداد ۱ یا ۱- به دستگاه داده میشود. یک دکمه دارد که هر وقت آن دکمه را فشار بدهیم، مجموع N عدد آخری که به دستگاه داده شده است را با تقریب e نمایش می دهد. یعنی در صورتی که مجموع N عدد آخر، k باشد عددی که دستگاه اعلام میکند بین (یا برابر) k(1+e) و k (1−e) میباشد.
حمید میخواهد یک e پیدا کند به صورتی که برای تمام N ها بتواند دستگاهی با این اعداد بسازد. ثابت کنید هر دستگاه با اعداد e و N، حداقل Ω(N) لازم دارد.
پاسخ
اگر دو ورودی به دستگاه بدهیم که جواب یکی ۱ و دیگری ۱- باشد، باید حالت حافظهی دستگاه بعد از خواندن دو ورودی متفاوت باشد. (چرا؟) یک دنبالهی n تایی از ۱ و ۱- را خوب مینامیم اگر جمع عدد 2i ام و 2i−1 ام آن ۰ شود. حال دستگاه باید برای هر دو عدد خوب حالت حافظهی متفاوت داشته باشد.
در غیر این صورت فرض کنید دو عدد خوب A و B باشند که حالت حافظه پس از خواندن آنها یکسان است. آنقدر به دستگاه ۰ میدهیم که تا جایی که مثلا جواب A، ۱ شود و جواب B، ۱-. در این دو حالت، دستگاه حافظهی یکسانی دارد که تناقض است. پس 2n2 ورودی داریم که حالت حافظه به ازای آنها متفاوت است. پس دستگاه حداقل n2 بیت حافظه نیاز دارد.