المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی دوم:دوره ی ۴:سوال ۸

سوال ۸

یک دسته کارت شامل $2n$ کارت که روی آن‌ها عددهای $0,1,…,2n-1 $ نوشته شده است، داده شده است. می‌توانیم با انجام عمل زیر روی این دسته کارت، یک دسته کارت دیگر که در آن ترتیب قرار گرفتن کارت‌ها تغییر کرده است، بسازیم:

ابتدا دسته کارت را به دو دسته که اولی شامل $n$ کارت اول و دومی شامل $n$ کارت باقیمانده است، تقسیم می‌کنیم. سپس به ترتیب یک کارت از دسته‌ی اول و یک کارت از دسته دوم برمی‌داریم و این کار را آن‌قدر تکرار می‌کنیم تا تمام کارت‌ها برداشته شوند.

به‌عنوان مثال اگر شماره‌ی کارت‌های قرارگرفته در دسته‌ی اول به ترتیب برابر با ۷، ۱، ۶، ۲، ۵، ۴، ۳، ۸ باشد، پس از انجام عمل فوق، ترتیب قرار گرفتن کارت‌ها به‌ صورت ۷، ۵، ۱، ۴، ۶، ۳، ۲، ۸ خواهد بود.

عمل فوق را «بُر زدن» دسته کارت می‌نامیم.

الف) ثابت کنید که برای هر $n$، اگر دسته کارت را بُر بزنیم، سپس دسته کارت حاصل را دوباره بُر بزنیم و همین کار را تکرار کنیم، بالاخره پس از مدتی به همان دسته کارت اولیه می‌رسیم.

پاسخ

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

ب) برای $n=10 $ چند بار باید عمل بُر زدن را تکرار کنیم تا به دسته کارت اولیه برسیم؟ (برای جواب خود دلیل بیاورید.)

پاسخ

قضیه: اگر جایگاه کارت ها را از $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$ پس از $k+1 $ بار بُر زدن به دسته کارت اولیه می‌رسیم.

پاسخ

با توجه به قضیه قسمت ب ثابت میکنیم به ازای هر $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$ بار به ازای هر جایگاه به خود آن برمیگردیم و حکم ثابت میشود.

د) ثابت کنید که برای $n=2^k+1 $ پس از $2k+2 $ بار بُر زدن به دسته کارت اولیه می‌رسیم.

پاسخ

قضیه:
$(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$ تکان نمی خورند حکم ثابت شده است.


ابزار صفحه