سوال ۸

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

قضیه: اگر جایگاه کارت ها را از $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−>2−>4−>8−>16−>13−>7−>14−>9−>18−>17−>15−>11−>3−>6−>12−>5−>10−>1−>…

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

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

قضیه:
$(2^{2k+2}-1) mod (2^{k+1}+1) = 0$
اثبات:

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