====== سوال ۱ ======

می‌دانیم ‎$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‎ برو.
  * پایان.

  * [[سوال ۲|سوال بعد]]