====== پارکینگ‌های مشکوک ======

آرمان در شرکت خود یک پارکینگ دارد که مدیریت آن را به پیام و حسام، واگذار کرده است. این پارکینگ دارای $n$ جای‌گاه با شماره‌های $1, 2, \ldots, n$ است. شرکت نیز،  $n$ کارمند با شماره‌های $1, 2, \ldots, n$ دارد. می‌دانیم عدد $n$ به صورت $2^k+1$ است. هر روز این کارمند‌ها طبق دستور حسام برای پارک کردن اتومبیل‌های‌شان طبق الگوریتم زیر عمل می‌کنند:


کارمندها به ترتیب شماره‌ پارک می‌کنند؛ یعنی ابتدا کارمند شماره ۱، سپس کارمند شماره ۲ و  $\ldots$ و در انتها کارمند شماره $n$ پارک می‌کند. کارمندهای بازار به طرز عجیبی تنّوع‌طلب و البته تنبل هستند! بنابراین هر کارمند در هنگام پارک کردن، مجموعه‌ی جای‌گاه‌های خالی را که تاکنون کم‌تر در آن‌ها رفته است، در نظر می‌گیرد و در میان آن‌ها جای‌گاهی را انتخاب می‌کند که کم‌ترین شماره را دارد.


برای مثال اگر $n=3$ باشد، کارمندان در سه روز نخست به ترتیب زیر در جای‌گاه‌ها پارک می‌کنند:


{{ :سوالات_المپیاد:مرحله‌ی_دوم:دوره‌ی_۲۶:45645645.png |}}

به روزهایی شماره‌ی تمام کارمندان با شماره‌ی جای‌گاه اتومبیل‌شان یک‌سان باشد، روزهای **منظّم** می‌گوییم! برای مثال روز یکم یک روز منظّم است. ثابت کنید بعد از روز یکم، نخستین باری که یک روز منظّم دیگر رخ می‌دهد، روز
$n(n-1) + 1$
است.

<پاسخ>



ابتدا به استقرای ضعیف روی $n$ ثابت می‌کنیم اگر $n$ به صورت $2^q$ باشد، در $n$ روز نخست هر یک از کارمندها در هر یک از جای‌گاه‌ها دقیقن یک بار پارک می‌کنند. برای پایه‌ی استقرا $n=1$ را در نظر می‌گیریم که حکم واضح است. فرض کنید حکم برای 
$n=2^k$
 درست باشد. ثابت می‌کنیم حکم برای 
$n=2^{k + 1}$
 نیز درست است. 
 
فرض کنید شرکت دارای $n$ کارمند باشد که
$n=2^{k+1}$
است. به کارمند‌های $1, 2, \ldots, 2^k$
کارمند‌های **قدیمی** و به دیگران، کارمندهای **جدید** می‌گوییم. به همین ترتیب جای‌گاه‌های قدیمی و جدید را تعریف می‌کنیم. در $2^k$ روز نخست، به ازای هر کارمند قدیمی در هنگام پارک کردن، دست کم یک جای‌گاه قدیمی وجود دارد که تاکنون در آن پارک نکرده است؛ پس در $2^k$ روز نخست کارمندهای قدیمی در جای‌گاه‌های قدیمی پارک می‌کنند و در نتیجه کارمندهای جدید باید در جای‌گاه‌های جدید پارک کنند. بنابراین طبق فرض استقرا در $2^k$ روز نخست هر کارمند قدیمی دقیقن یک بار در هر یک از جای‌گاه‌های قدیمی و هر کارمند جدید دقیقن یک بار در هر یک از جای‌گاه‌های جدید قرار می‌گیرد. در $2^k$ روز دیگر، به ازای هر کارمند قدیمی در هنگام پارک کردن، دست کم یک جای‌گاه جدید وجود دارد که تاکنون در آن پارک نکرده است و از طرفی قبلن در هر یک از جای‌گاه‌های قدیمی دقیقن یک بار پارک کرده است؛ پس در $2^k$ روز دوم کارمندهای قدیمی در جای‌گاه‌های جدید و کارمندهای جدید در جای‌گاه‌های قدیمی پارک می‌کنند. بنابراین طبق فرض استقرا در $2^k$ روز دوم هر کارمند قدیمی در هر جای‌گاه جدید دقیقن یک بار و هر کارمند جدید در هر جای‌گاه قدیمی دقیقن یک بار پارک می‌کند. به این ترتیب در $n$ روز نخست هر یک از کارمندان در هر یک از جای‌گاه‌ها دقیقن یک بار پارک می‌کنند و حکم استقرا ثابت می‌شود.
$\blacksquare$

حال حکم اصلی مسئله را در نظر می‌گیریم و فرض می‌کنیم $n$ به صورت $2^q+1$ باشد. کارمند شماره $n$ را **نخودی** و بقیه‌ی کارمندها را **عادی** می‌نامیم. به استقرای قوی روی $k$ که $1 \le k \le n$ ثابت می‌کنیم در روزهای 
$$(n-1)(k-1) + 1, (n-1)(k-1)+2, \ldots, (n-1)k$$
کارمند نخودی در جای‌گاه $n-k+1$ پارک می‌کند و هر یک از کارمندهای عادی در هر یک از جای‌گاه‌ها به جز جای‌گاه $n-k+1$ دقیقن یک بار پارک می‌کنند.

برای پایه‌ی استقرا $k=1$ را در نظر بگیرید. در روزهای
$1, 2, \ldots, n-1$
به ازای هر یک از کارمندهای عادی دست کم یکی از جای‌گاه‌های
 $1, 2, \ldots, n-1$
وجود دارد که تاکنون در آن پارک نکرده است. بنابراین در $n-1$ روز نخست کارمند نخودی در جای‌گاه $n$ وکارمندهای عادی در جای‌گاه‌های 
$1, 2, \ldots, n-1$
 پارک می‌کنند. با توجه به حکم اثبات شده در ابتدای نوشته هر یک از کارمندهای 
 $1, 2, \ldots, n-1$
 دقیقاً یک بار در هر یک از جای‌گاه‌های
$1, 2 , \ldots, n-1$
 پارک می‌کنند و پایه‌ی استقرا ثابت می‌شود.

حال فرض کنید حکم برای $<k$ برقرار باشد. ثابت می‌کنیم حکم برای $k$ نیز برقرار است. روزهای 
$$(n-1)(k-1)+1, (n-1)(k-1)+2, \ldots, (n-1)k$$
را روزهای **طلایی** می‌نامیم.
تا قبل از شروع روزهای طلایی
طبق فرض استقرا هر یک از کارمندهای عادی دقیقن $k-1$ بار در هر یک از جای‌گاه‌های
$1, 2, \ldots, n-k$
و دقیقاً $k-2$ بار در هر یک از جای‌گاه‌های
$n-k+2, n-k+3, \ldots, n$
پارک کرده‌اند. در هر یک از روزهای طلایی،
به ازای هر یک از کارمندهای عادی در هنگام پارک کردن، جای‌گاهی به جز جای‌گاه $n-k+1$ وجود دارد که در هیچ روز طلایی در آن پارک نکرده است و چنین جای‌گاهی در هنگام پارک کردن به جای‌گاه $n-k+1$ اولویت دارد؛ پس در روزهای طلایی کارمند نخودی در جای‌گاه $n-k+1$ و کارمندهای عادی در جای‌گاه‌های دیگر پارک می‌کنند. 

حال شرکتی مشابه با $n-1$ جای‌گاه با شماره‌های $1,2, \ldots, n-1$ در نظر بگیرید که در شروع روزهای طلایی شرکت ما، تأسیس می‌شود. ادّعا می‌کنیم برای کارمندان شرکت ما، اولویت جای‌گاه‌های
$$n-k+2, n-k+3, \ldots, n, 1, 2, \ldots, n-k$$
به ترتیب برابر اولویت جای‌گاه‌های
$$1, 2, \ldots, n-1$$
برای کارمندان شرکت تازه‌ تأسیس است. دو جای‌گاه با شماره‌های $i, j$ در شرکت ما در نظر بگیرید. سه حالت داریم:

  * $1 \le i < j \le n-k$ باشد. در این صورت اگر تاکنون در جای‌گاه $i$ بیش‌تر پارک کرده باشیم، اولویت با جای‌گاه $j$ و در غیر این صورت اولویت با جای‌گاه $i$ است. در شرکت تازه تأسیس نیز اولویت‌های جای‌گاه‌های متناظر ($k-1+i, k-1+j$) به همین صورت است.
  * $n-k+2 \le i < j \le n$ باشد. در این صورت اگر تاکنون در جای‌گاه $i$ بیش‌تر پارک کرده باشیم، اولویت با جای‌گاه $j$ و در غیر این صورت اولویت با جای‌گاه $i$ است. در شرکت تازه تأسیس نیز اولویت‌های جای‌گاه‌های متناظر $\big(i-(n-k+1), j - (n-k+1)\big)$ به همین صورت است.
  * $1 \le i \le n-k < j \le n$ باشد. در این صورت اگر تاکنون در جای‌گاه $i$ بیش‌تر پارک کرده باشیم اولویت با جای‌گاه $j$ در غیر این صورت اولویت با جای‌گاه $i$ است. در شرکت تازه تأسیس نیز اولویت جای‌گاه‌های متناظر $\big(k-1+i, j-(n+k-1)\big)$ به همین صورت است.

به این ترتیب ادّعای ما ثابت می‌شود و کارمندان ما در روزهای طلایی به مانند کارمندهای شرکت تازه‌تأسیس در جای‌گاه‌های متناظر پارک می‌کنند که طبق حکم ثابت شده در ابتدای نوشته هر کارمند در هر یک از جای‌گاه‌ها به جز جای‌گاه $n-k+1$ دقیقاً یک بار پارک می‌کند و حکم استقرا ثابت می‌شود.
$\blacksquare$

با توجه به روند اثبات‌شده‌ی بالا در $n$ دور نخست - که هر دور شامل $n-1$ روز است - روز منظّمی به جز روز نخست رخ نمی‌دهد؛ امّا پس از این $n$ دوره هر کس در هر جای‌گاه دقیقن $n-1$ بار پارک کرده است و روز بعدی روزی منظّم خواهد بود و حکم ثابت می‌شود.


</پاسخ>
  * [[سوال چهار|سوال بعد]]
  * [[سوال دو|سوال قبل]]