به محفل ریاضی ایرانیان خوش آمدید! لطفا برای استفاده از تمامی امکانات عضو شوید
سایت پرسش و پاسخ ریاضی
+4 امتیاز
275 بازدید
در دبیرستان و دانشگاه توسط erfanm

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

مرجع: 102 مساله ی ترکیبیات تالیف: تیتو آندریسکو/ زومینگ فنگ
توسط fardina
+2
من اصلا متوجه سوال نمیشم.
میشه بیشتر توضیح بدید.
توسط erfanm
برای حرکت اول میتوانیم حالت پشت یا روی یک سکه را تغییر بدیم برای حرکت دوم، حالت دو سکه،...برای حرکت $2001$ ، باید حالت تمام سکه ها را عوض کنیم.

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

1 پاسخ

0 امتیاز
توسط salar

کلید مسئله فرد بودن گام آخر است که با گام اول که $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$ بار برمیگردانیم تا همه سکه ها در حالت رو باقی بمانند.

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

حمایت مالی


کانال تلگرام محفل ریاضی
امروز : تاریخ شمسی اینجا نمایش داده می‌شود
...