روی مجموعهی متناهی S، تابع f تعریف شده است؛ به نحوی که به ازای هر x∈S،f(x) وجود دارد و عضوی از S است.
برای عنصر دلخواه z از مجموعهی S میتوان دنبالهی زیر را در نظر گرفت:
z,f(z),f(f(z)),f(f(f(z))),…
همهی عناصر این دنباله متعلق به S هستند و با شروع از z و استفاده از تابع f مرتبا عنصر جدیدی حاصل میشود. در دنبالهی فوق با به وجود آمدن اولین عنصر تکراری قسمتی از دنباله حالت تناوبی به خود میگیرد. مثلا:
si1,si2,…,sia,sia+1,…,sib=sia
در دنبالهی فوق bامین عنصر برابر aامین عنصر شده است، بنابراین در دنباله مرتبا قسمت sia,…,sib−1 تکرار خواهد شد.
در آغاز si1 را داریم و هدف یافتن عددهای b و a است به طوری که b اولین جایی باشد که sib با یکی از عناصر قبلی دنباله برابر است و a عددی است که 1≤a<b و sia=sib. تابع f در دسترس ما قرار ندارد و تنها میدانیم که اگر عنصر x را داشته باشیم، پیدا کردن f(x) از مرتبهی زمانی O(1) است. اما حافظه نیز کم است، مجموعا تعداد عددها و تعداد عناصری از S که در حافظه ذخیره شدهاند باید از O(1) باشد.
پاسخ