دنبالهی A=<a1,a2,...,an> از اعداد طبیعی را در نظر بگیرید. در ابتدای کار٬ به ازای هر 1≤i≤n میدانیم که ai=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≤x,y≤n):
برای مثال اگر n=۸ و الگوریتم را دو بار٬ ابتدا به ازای (x,y)=(۲,۳) و سپس به ازای (x,y)=(۲,۷) اجرا کنیم٬ پس از اجرای الگوریتم خواهیم داشت:
A=<1,3,3,4,5,6,3,8>. همچنین مقدار B بعد از این دو اجرا برابر ۲ خواهد بود.
الف) فرض کنید n=۱۶ و میخواهیم الگوریتم را ۱۵ بار اجرا کنیم. مقدار x و y را برای هر اجرا طوری تعیین کنید که پس از پایان کار٬ مقدار B برابر ۳۲ باشد.
ب) فرض کنید n=2k و میخواهیم الگوریتم را n−1 بار اجرا کنیم (1≤k). ثابت کنید نمیتوان مقادیر x و y را در این دفعات اجرا طوری تعیین کرد که پس از پایان کار مقدار B بیشتر از k×2k شود.