الف:

عدد $n$ را خوب مینامیم اگر فرض این قسمت برای آن درست باشد.

میدانیم که ترنیب قرار گرفتن اعداد روی کارت ها بر خوب بودن عدد $n$ تاثیری ندارد از طرفی میدانیم تعداد حالات چینش $2n$ کارت متناهی است($(2n)!$). حال فرض کنید عدد $n$ خوب نیست با هر بار بر زدن کارت ها به دسته ای با چینش جدید میرسیم و چون تعداد حالات چینش محدود است پس قطعا به حالتی تکراری میرسیم. این نشان میدهد که این حالتی که به آن دوباره رسیده ایم خوب است. پس عدد $n$ خوب است. یعنی این امکان وجود ندارد که عددی پیدا شود که خوب نباشد.

ب:

اصل 1: اگر جایگاه کارت ها را از 0 تا $2n-1$ شماره گذاری کنیم، به ازای هر جایگاه $i$ ، اگر $0 \le i \le n-1$ باشد آنگاه کارت جایگاه $i$ام پس از برخوردن در جایگاه $2i$ قرار میگیرد و اگر $n \le i \le 2n-1$ باشد آنگاه کارت جایگاه $i$ ام، در جایگاه $2(i-n)+1$ قرار میگیرد.چون $j$امین کارت دسته ی اول در $j$امین جایگاه زوج و $j$امین کارت درسته ی دوم در $j$ امین جایگاه فرد قرار میگیرد.

با توجه به اصل 1 در زیر آمده است که کارت هر جایگاه در مرحله ی بعد در کدام جایگاه قرار میگیرد:

$1 \to 2 \to 4 \to 8 \to 16 \to 13 \to 7 \to 14 \to 9 \to$

$18 \to 17 \to 15 \to 11 \to 3 \to 6 \to 12 \to 5 \to 10 \to 1 \to ...$

با توجه به اینکه کارت جایگاه 0ام و 19ام تغییری نمیکند، پس بعد از 17 بار برزدن به حالت اول برمیگردیم.

ج:

با توجه به اصل 1 ثابت میکنیم به ازای هر $n=2^k$ و به ازای هر جایگاه مانند $x$ ($1 \le x \le 2^k-1$) بعد از $k+1$ بار برزدن کارتی که در بتدا در جایگاه $x$ بوده به جای اولش باز میگردد. نمایش عدد $x$ در مبنای 2 را در نظر بگیرید. چون $n=2^k$ پس اگر این عدد در مبنای 2 دارای $t$ رقم باشد، آنقدر در 2 ضرب میشود تا تعداد ارقامش برابر $k+1$ شود. در واقع $k+1-t$ بار در 2 ضرب میشود. پس به انتهای آن $k+1-t$ صفر اضافه میشود. حال در اینجا عدد $x$ بزرگتر مساوی $2^k$ میشود و جزء دسته ی دوم کارت ها قرار میگیرد. با توجه به اصل یک اگر جایگاه $i$ در دسته ی دوم قرار داشت کارت موجود در آن به جایگاه $2(i-n)+1$ میرود. میتوان دید برای $n=2^k$ این عمل اینگونه تعریف میشود که ابتدا رقم یکمان را از ابتدا بر میداریم (در عملیات $i-n$. زیرا رقم $k+1$ام عدد $i$ یک است) سپس یک رقم صفر به انتهای آن اضافه میشود (وقتی در 2 ضرب میکنیم) و بعد آن را با یک جمع میکنیم. یعنی درواقع رقم صفری که به انتهای آن اضافه کردیم به یک تبدیل میشود. پس مانند آن است که رقم یک را از ابتدای آن برمیداریم و به انتهای آن اضافه میکنیم. پس به عبارتی اگر در ابتدای کار ما به ابتدای عدد $x$ ، $k+1-t$ تا رقم صفر اضافه میکنیم، هر عمل ضربدر دو کردن مانند آن است که یک صفر از ابتدای آن برمیداریم و انتهای آن میگذاریم و وقتی در دسته دوم است (در واقع رقم $k+1$ ام 1 است) رقم یک را از ابتدای آن برداشته و به انتهای آن می افزاییم. پس بعد از $k+1$ بار به ازای هر جایگاه به خود آن برمیگردیم و حکم ثابت میشود.

د:

اصل 2: به دلیل اینکه $2^{2k+2}-1=(2^{k+1}-1) \times (2^{k+1}+1)$ پس $= 0$ $(2^{k+1}+1)$ $mod$ $(2^{2k+2}-1)$.

لم1: به ازای هر $i$ داریم: $(i \times 2^{2k+2}) mod (2(2^{k}+1)-1)=i$

اثبات: با توجه به اصل2 داریم:

$(2^{2k+2}-1) mod (2^{k+1}+1) =0 \to (2^{2k+2})mod(2^{k+1}+1)=1$

$ \to (i \times 2^{2k+2})mod(2^{k+1}+1)=i \to (i \times 2^{2k+2}) mod (2(2^k+1)-1)=i$

در اینجا میگوییم هر در هر مرحله اگر کارتی در جایگاه $i$ ام باشد به جایگاه $(2n-1)$ $mod$ $(2 \times i)$ میرود. اگر در دسته ی اول باشد چون کوچکتر از $n-1$ است، واضح است چرا اینگونه است. اگرهم در دسته ی دوم باشد میدانیم باید به جایگاه $2(i-n)+1 = 2i-2n+1=2i-(2n-1)$ برود. از آنجا کارت $2n-1$ ام در هر بار بر زدن در جای خود ثابت است پس کارت هایی را در دسته ی دوم در نظر میگیریم که شماره ی آنها کوچکتر از $2n-1$ است. چون $i$ در این مرحله کوچکتر از $2n-1$، این عدد برابر همان $(2n-1)$ $mod$ $(2 \times i)$ میشود. پس اگر $(2n-1)=i$ $mod$ $(i \times 2^a)$ بود یعنی کارت جایگاه $i$ام پس از $a$ بار دوباره به جایگاه اولش بر میگردد.که با توجه به لم1 اگر $a=2k+2$ باشد به ازای تمامی کارت ها رابطه ی گفته شده برقرار است. در نتیجه پس از $2k+2$ بار برزدن کارت ها به جایگاه اولیه خوب بازمیگردند و حکم ثابت میشود.