دنباله

دنباله‌ی $A= <a_1,a_2,...,a_n>$ از اعداد طبیعی را در نظر بگیرید. در ابتدای کار٬ به ازای هر $1\le i \le n$ می‌دانیم که $a_i=i$. هم‌چنین یک متغیر $b$ تعریف می‌کنیم و مقدار اولیه‌ی آن را برابر ۰ می‌گذاریم.

فرض کنید $f(z)$ برابر تعداد اعدادی از دنباله‌ی $A$ است که مقدارشان برابر $z$ است. مثلاً اگر $n= ۸$ در ابتدای کار داریم: $A= <1,2,3,4,5,6,7,8>$ و هم‌چنین $f(8)=1$ و $f(9)=0$. الگوریتم زیر را در نظر بگیرید که در هر بار اجرا٬ دو عدد طبیعی $x$ و $y$ را از ورودی می‌گیرد و پردازش می‌کند ($1 \le x , y \le n$):

  1. مقدار $x$ و $y$ را از ورودی دریافت کن.
  2. اگر $a_x= a_y$٬ به مرحله‌ی ۹ برو٬ در غیر این صورت به مرحله‌ی ۳ برو.
  3. اگر $f(a_x) \le f(a_y)$٬ به مرحله‌ی ۴ برو٬ در غیر این صورت به مرحله‌ی ۷ برو.
  4. $B$ را به اندازه‌ی $f(a_x)$ واحد اضافه کن.
  5. تمام اعداد دنباله‌ی $A$ که مقدارشان برابر $a_x$ است را به $a_y$ تبدیل کن.
  6. به مرحله‌ی ۹ برو.
  7. $B$ را به اندازه‌ی $f(a_y)$ واحد اضافه کن.
  8. تمام اعداد دنباله‌ی $A$ که مقدارشان برابر $a_y$ است را به $a_x$ تبدیل کن.
  9. پایان.

برای مثال اگر $n=۸$ و الگوریتم را دو بار٬ ابتدا به ازای $(x,y)=(۲,۳)$ و سپس به ازای $(x,y)=(۲,۷)$ اجرا کنیم٬ پس از اجرای الگوریتم خواهیم داشت:

$A= <1,3,3,4,5,6,3,8>$. هم‌چنین مقدار $B$ بعد از این دو اجرا برابر ۲ خواهد بود.

الف) فرض کنید $n=۱۶$ و می‌خواهیم الگوریتم را ۱۵ بار اجرا کنیم. مقدار $x$ و $y$ را برای هر اجرا طوری تعیین کنید که پس از پایان کار٬ مقدار $B$ برابر ۳۲ باشد.

ب) فرض کنید $n=2^k$ و می‌خواهیم الگوریتم را $n-1$ بار اجرا کنیم ($1 \le k$). ثابت کنید نمی‌توان مقادیر $x$ و $y$ را در این دفعات اجرا طوری تعیین کرد که پس از پایان کار مقدار $B$ بیش‌تر از $k \times 2^k$ شود.