وجود روشی که بتوان تمام $2001$ سکه ی دلخواه چیده شده روی یک میز را یا به پشت یا به رو تبدیل کنیم

Question

$2001$ سکه روی میز قرار دارد به ازای $i=0,1,2,...2001$ میتوان( پشت سر هم) دقیقا $i$ سکه را پشت و رو کرد. ثابت کنید همواره میتوان همه ی سکه ها را به رو یا همه را به پشت کرد. اما فقط یکی از این کارها میسر است.(نمیتوان الگوهایی پیدا کرد که طبق یکی سکه ها همه رو باشند و طبق الگوی دیگر همه پشت شوند.

Comments

من اصلا متوجه سوال نمیشم.
میشه بیشتر توضیح بدید.

---

برای حرکت اول میتوانیم حالت پشت یا روی یک سکه را تغییر بدیم برای حرکت دوم، حالت دو سکه،...برای حرکت $2001$ ، باید حالت تمام سکه ها را عوض کنیم.

ودر هر مرحله سکه هایی رو انتخاب کنیم که در آخر حالت تمام سکه ها مثل هم باشد.

---

@erfanm ببینید آیا منظورتان را درست متوجه شده‌ام. یعنی الگوریتم‌ها محدود به این هستند که حتما ۲۰۰۱ گام داشته باشند (در گام ۰ چون ۰ سکه انتخاب می‌شود و رویش عوض می‌شود پس وجودش عبث است همان گام ۱ تا ۲۰۰۱ در نظر می‌گیریم) و در هر گام به تعداد اندیسِ گام، سکه انتخاب شده و جهتش را عوض می‌کنیم. حالا تنها چیزی که از الگوریتم برای ما آزاد است این است که سکه‌های مورد انتخاب گام‌ها را با توجه به حالت اولیهٔ سکه‌ها (ورودیِ الگوریتم) تعیین کنیم. بلی؟ و پرسش این را می‌خواهد که ثابت کنیم برای هر یک از ورودی‌ها دقیقا فقط یکی از دو حالتِ همه رو یا همه پشت را می‌توان با چنین الگوریتم‌هایی می‌توان تولید کرد. بلی؟

---

سلام
بلی دقیقا همین است.
کاملا درست متوجه شدید@amirhosein

Answer 1

کلید مسئله فرد بودن گام آخر است که با گام اول که $0$ است استتار میکند.

در واقع به کمک فرد بودن تعداد سکه ها مسئله حل میشود.

تعداد سکه های پشت را میشماریم و $J$ قرار میدهیم.

حال تمام مراحل را بغیر از سه مرحلهء ($2001,2001-J,J$) طبق روال زیر انجام میدهیم.

در گام $i$ فقط $i$ سکه نزدیک را برمیگردانیم و در گام $2001-i$ فقط $2001-i$ سکه دور را برمیگردانیم.

پس ترکیب گام $i$ با گام $2001-i$ یعنی تمام سکه ها یکبار برمیگردند.

حال در کل ما تغییری انجام نداده ایم و در واقع تمام گام ها را غیر از سه گام حذف کرده ایم تا با این سه گام مسئله را حل کنیم.

گام $J$ را برای سکه هایی که به پشت هستند، که در اول کار شمارش کرده بودیم انجام میدهیم تا همه سکه ها رو شوند.

حال اگر $2001-J$ زوج باشد، سکه اول را $2001-J$ بار برمیگردانیم و در گام $2001$ تمام سکه ها را به پشت تغییر میدهیم.

در غیر این صورت $2001-J$ فرد است، پس دو گام باقی مانده را روی سکه اول انجام میدهیم؛ درنتیجه سکه اول را در دو گام باقی مانده $4002-J$ بار برمیگردانیم تا همه سکه ها در حالت رو باقی بمانند.

نتیجه:حالتی که تعداد آن فرد است خروجی نهایی ما خواهد بود.