انتقال مهره‌های گاوی

جواب ماشین گاوی را در نظر بگیرید. چون در ماشین او در یک لحظه می‌تواند در یک خانه بیش از یک مهره باشد، پس می‌توان فرض کرد که اگر مهره‌ای با مختصات $(x_1,y_1)$ را بخواهیم به نقطه‌ای با مختصات $(x_2, y_2)$ انتقال دهیم، می‌توانیم ابتدا این مهره را به نقطه‌ی $(x_1,y_2)$ برده و سپس آن را به خانه‌ی $(x_2,y_2)$ ببریم. به حرکات موجود در انتقال اول، حرکت عمودی و به حرکات موجود در انتقال دوم حرکت افقی می‌گوییم. به عبارتی ابتد مهره را با تعدادی حرکت عمودی به سطر مورد نظر انتقال می‌دهیم و سپس با تعدادی حرکت افقی به ستون مورد نظر می‌بریم. همچنین به هر مهره زوج مرتب $(c,d)$ را نسبت می‌دهیم که در آن $c$ به معنای تعداد حرکت‌های عمودی لازم برای این نقطه و $d$ برابر با تعداد حرکت‌های افقی لازم به ازای این نقطه است.

لم۱

به ازای یک بعد سوال درست است. فرض کنید دو مهره در مسیر حرکت خود با هم برخورد باشند (مثلا مهره‌های $a$ و $b$ که $a$ می‌خواهد به خانه‌ی $A$ برود و $b$ به خانه‌ی $B$). مقصد این دو مهره را با هم عوض کنید ($a$ به $B$ برود و $b$ به $A$ برود). با این کار حداقل یک واحد از تعداد برخورد‌ها کاسته می‌شود. در ضمن می‌دانیم با این کار جواب ما از حالت قبلی‌اش بیش‌تر نمی‌شود. این کار را آن‌قدر تکرار کنید که دیگر برخوردی نداشته باشیم. پس جواب ماشین ببعی و گاوی به ازای یک بعد برابر است.

حل نصف نمره

به ازای مهره $i$ام ($1\leq i\leq n$) $e_i$ را برابر $max(c_i,d_i)$‌تعریف کنید. حال فرض کنید $F=max_{i}^n=1^{(e_i)}$. واضح است که $t_1\geq F$ است. حال جواب ماشین گاوی را در نظر بگیرید. طبق لم ۱، ماشین گاوی می‌تواند به ما جوابی بدهد که هیچ برخوردی بین دو مهره که در حال انجام حرکات عمودی خود هستند رخ ندهد. حال هر مهره‌ای، حرکت عمودی خود را انجام دهد و صبر کند تا تمامی مهره‌ها حرکت‌های عمودی خود را انجام دهند. سپس هر مهره‌ای حرکت افقی خود را انجام دهد. اکنون هرکس به خانه‌ی مورد نظر خود رسیده است. حال خواهیم داشت:

$$t_2\leq max(c_i) +max(d_i)\leq F+F \leq 2t_1$$

حل کامل

از بین جواب‌های موجود برای ماشین گاوی جوابی را در نظر بگیرید که $\sum_{i=1}^n c_{i}^2$ در آن کمینه شود. می‌خواهیم ثابت کنیم که اگر همچین جوابی را در نظر بگیریم، در هیچ لحظه‌ای دو مهره در یک خانه نخواهند بود. فرض کنید دو مهره در یک ستون باشند و هنگامی که حرکت عمودی انجام می‌دهند به یک نقطه برسند. فرض کنید مهره‌ی $a$ بخواهد به نقطه‌ی $A$ انتقال یابد و مهره‌ی $b$ نیز به خانه‌ی $B$ انتقال یابد. حال مهره‌ی $a$ را به نقطه‌ی $B$ انتقال دهید و مهره‌ی $b$ را به خانه‌ی $A$. $c_a$ و $c_b$ هر دو کم‌تر شده است چون هیچ دو نقطه‌ی آبی‌ای در یک سطر نیستند. پس مجموع مورد نظر ما کم‌تر شده است. حال فرض کنید دو مهره از دو ستون مختلف به هم برخورد کنند. در این صورت یکی از آن‌ها در حال انجام حرکت عمودی خود بوده است و دیگری در حال انجام حرکت افقی خود، زیرا اولا هیچ دو نقطه آبی‌ای در سطر یکسانی نیستند، ثانیا این دو مهره در یک ستون نبودند و قرار بود هر مهره‌ای که می‌خواهد به مقصد خود برود، اول حرکات عمودی‌اش را نجام دهد، سپس حرکات افقی‌‌اش را. اکنون مقصد این دو مهره را با هم عوض کنید. از آن‌جایی که این دو مهره در یک زمان در یک نقطه بوده‌اند و همچنین یکی از آن‌ها در حال حرکت افقی بوده و دیگری در حال حرکت عمودی، پس جواب ما بیش‌تر نشده است. هم‌چنین اثبات می‌کنیم که مجموع مورد نظر ما کم‌تر شده است. اگر جهت حرکت‌های این دو مهره باهم متفاوت باشد که از $c$ هر دوی آن‌ها کاسته شده است پس مجموع نیز کم‌تر شده است (دقت کنید نقطه‌های نهایی در یک سطر نیستند). حال اگر جهت حرکت این دو مهره یکسان باشد، بدون این که از کلیت سوال کاسته شود فرض کنید که جهت حرکت هر دوی آن‌ها به بالا بوده باشد. حال این مهره‌ها را با ۱ و ۲ نشان دهید. همچنین فرض کنید:

$$c_1<c_2 \Rightarrow y_1>y_2 \\ p=c_2+y_2-(c_1+y_1)$$

حال قرار است مهره ۱، $c_1+p$ حرکت عمودی انجام دهد و مهره ۲، $c_2-p$ حرکت عمودی انجام دهد. مجموع ما به اندازه‌ی $2p(c_1+p-c_2)<0$ است و مجموع ما کم‌تر شده است. پس اگر مجموع ما کمینه شود، ماشین به ما جوابی را می‌دهد که درهیچ لحظه‌ای دو مهره در یک نقطه نباشند که این همان خواسته‌ی ماشین ببعی است.