در دوران کودکی (وقتی که حدودن ده ساله بودم) یک بازی داشتم: موقع قدم زدن، اول پای راست رو بر می‌داشتم و بعد پای چپ (تا این‌جا که طبیعیه. به قول استادم این بازی نیست: به این می‌گن قدم زدن!). اما برای قدم سوم، چون دفعه‌ی قبلی اول پای راست رو برداشته بودم، این بار اول پای چپ رو بر می‌داشتم و بعد پای راست که عدالت برقرار شده باشه. اگر برای پای راست از «ر» و برای پای چپ از «چ» استفاده کنیم، ترتیب‌اش میشه رچ‌چ‌ر. حالا برای چهارتایی بعدی، چون چهارتایی قبلی با راست شروع شده، این یکی باید با چپ شروع بشه. پس چهار قدم بعدی خواهند بود چ‌ررچ و در نتیجه کل هشت قدم خواهند بود رچ‌چ‌رچ‌ررچ و به همین ترتیب یک مجموعه‌ی شونزده قدمی برابر می‌شد با رچ‌چ‌رچ‌ررچ‌چ‌ررچ‌رچ‌چ‌ر و به همین ترتیب. این کار رو تا جایی ادامه می‌دادم که ذهنم کشش می‌داشت و می‌دونستم کجای این سری هستم. نتیجه‌اش این می‌شد که راه رفتن‌ام کمی غیرعادی می‌شد چرا که گاهی دو تا راست یا دو تا چپ پشت هم قرار می‌گرفتن و مجبور بودم هر از گاهی وسط قدم برداشتن با همون پا بپرم تا ترتیب و عدالت رعایت شده باشن.
در ضمن در کل این سری می‌تونیم جای چپ و راست رو عوض کنیم و عدالت هم‌چنان برقرار باشه (یعنی اولین قدم رو با پای چپ شروع کنیم و بقیه‌اش هم مشخصه). اگر ترکیب تمام قدم‌های ممکن رو به شکل یک درخت دودویی رسم کنیم، شکل بالا حاصل میشه (در این شکل در هر راس شاخه‌ی سمت چپ به معنای قدم چپ و شاخه‌ی سمت راست به معنای قدم راسته). برای برآورده کردن شرط عدالت در این بازی، در این درخت تنها دو مجموعه از راس‌ها قابل قبول خواهند بود که من با رنگ قرمز نشون‌شون داده‌ام (برای دیدن شکل بزرگ‌تر روی اون کلیک کنین).
در تلاش بودم که این الگو رو به شکل واضح‌تر (و شاید به شکل یک عبارت ریاضی) بنویسم که هنوز موفق نشده‌ام. حالت مطلوب اینه که بتونیم بدون ساختن کل جمله از پیش بگیم که مثلن n امین حرکت من با پای چپ خواهد بود یا راست. یک سوال دیگه هم برام ایجاد شد: چه طور میشه برای تولید جملات معتبر با این خصوصیت، یک عبارت باقاعده نوشت (اگر که باقاعده است) و یا به طور کلی چه طور میشه این رشته‌ها رو با زبان صوری تعریف کرد. در ضمن صحبت از نظریه‌ی زبان‌ها و ماشین‌ها شد و جا داره یادی کنیم از آلن تورینگ که امروز صدمین سال تولدشه.
در پایان این رو هم اضافه کنم که این عادت راه رفتن در اون زمان به نوعی وسواس تبدیل شده بود که خوشبختانه در بزرگ‌سالی ترک شد.
روزبه جان من با چیزی که از بازی فهمیدم و تا حالت 32 چک کردم (بیش از اون دقیق نمی دونستم با چپ باید شروع کنم یا راست) تابع XOR می تونه جواب رو به شما بده
قدم ها رو از صفر شماره گذاری کن، برای راست عدد صفر (باینری) و برای چپ عدد یک (باینری) درنظر بگیر. هر عددی دلخواه یه معادل باینری داره، XOR همه ی بیت های عدد مورد نظرت میشه وضعیت پا در اون قدم.
مثال1: قدم اول شماره ی صفر است که معادل باینری اون هم چند بیت صفر میشه (تعداد بیتها لگاریتم مبنای دو طولانی ترین قدم هست) و XOR همه ی بیت ها هم صفر میشه پس پای راست
مثال2: قدم چهارم (شماره ی 3 چون از صفر شروع کردیم) میشه 101 که XOR بیتهاش بازم صفر میشه، یعنی پای راست
مثال 3: قدم سی و دوم (یعنی شماره ی 31) معادل باینریش 11111 میشه که خروجی XOR اون میشه 1 یعنی پای چپ
پ.ن. تنها مساله ی کامپیوتری که می تونه 3 صبح من رو بیدار نگه داره مساله ی جبر بول هست
به امین: عالی بود! :)