سوال ۱

می‌دانیم ‎$2^n$‎ عدد باینری به طول ‎$n$‎ داریم. ‎$e(m)$‎ را جایگاه اولین رقم ‎$1$‎ ازسمت راست عدد ‎$m$‎ در مبنای ‎$2$‎ فرض کنید. برای مثال ‎$e(3)=1$‎ و ‎$e(12)=3$‎ . ثابت کنید خروجی الگوریتم زیر دنباله‌ی ‎$w_1,w_2,\ldots,w_{2^n-1}$‎ است که ‎$w_j$‎ دنباله‌ای ‎$n$‎ کاراکتری و باینری است و ثابت کنید به ازای هر ‎$a‎, ‎b$‎ متفاوت، ‎$w_a$‎ و ‎$w_{b}$‎ متفاوت اند. ‎

• ‎$w_0=(000\ldots0)$‎ (تعداد صفرها ‎$n$‌تا)‎
• ‎$k=1$‎
• ‎$j$‎ را برابر با ‎$e(k)$‎ قرار بده.
• در دنباله $w_{k-1}$‎ ‎، $a_j$ (رقمی که در مکان ‎$j$‎ام از راست قرار دارد) را با ‎$(1-a_j)$‎ عوض کن و آن را ‎$w_k$‎ نام‌گذاری کن.
• به مقدار ‎$k$‎ یکی اضافه کن.
• اگر ‎$k<2^n$‎ به خط ‎3‎ برو.
• پایان.

• سوال بعد