You are not allowed to perform this action

مسأله‌ی یکم

پوپک، پونه و پرند می‌خواهند روی یک دور $n$ رأسی که رئوس آن با اعداد ۱ تا $n$ شماره‌گذاری شده‌اند بازی کنند.

پونه یک مهره‌ی سفید و پوپک یک مهره‌ی سیاه دارد که در ابتدا هر دوی این مهره‌ها روی رأس شماره‌ی ۱ هستند.

پونه و پوپک یکی در میان (با شروع از پونه) روی این دور بازی می‌کنند طوری که هر کس در نوبتش مهره‌ی خود را از روی رأس فعلی برداشته و روی یکی از رؤوس همسایه‌اش قرار می‌دهد. در ابتدای بازی و نیز پس از حرکت هر کدام از این دو نفر، پرند یک «عکس» از وضعیت مهره‌ها روی دور می‌گیرد. دو عکس متفاوت اگر حداقل یکی از دو شرط زیر برقرار باشد:

  1. شماره رأسی که مهره‌ی پونه (مهره‌ی سفید) روی آن قرار دارد در این دو عکس متفاوت باشد.
  2. شماره رأسی که مهره‌ی پوپک (مهره‌ی سیاه) روی آن قرار دارد در این دو عکس متفاوت باشد.

پوپک و پونه می‌خواهند همه‌ی عکس‌ها متفاوت ثبت شوند، حداکثر چند مرحله می‌توانند بازی کنند؟

راهنمایی

ابتدا سعی کنید برای $n$ زوج سوال را حل کنید.

راهنمایی

برای $n$ زوج می‌توان تمام $ \binom{n}{2} $ عکس مختلف را دید

راهنمایی

عدد یک عکس را، تعداد حرکات ساعتگرد مهره‌ی سیاه برای رسیدن به مهره‌ی سفید در نظر گیرید.

راهنمایی

سعی کنید تمام عکس‌هایی که عددشان $2i-1$ و $2i-2$ است را به صورت یکی‌درمیان و متوالیا بگیرید. $i=1, 2, \dots, \frac{n}{2}$

راهنمایی

تا زمانی که به عکس تکراری نمی‌رسید، مهره‌ها را یکی در میان در نوبت خود یک واحد در جهت ساعت‌گرد حرکت دهید.

راهنمایی

پس از گام نهایی دیدن تمام عکس‌های با عدد $2i$ و $2i-1$، نوبت مهره‌ی سیاه است. آن را یک واحد پادساعتگرد حرکت دهید.

راهنمایی

برای $n$ فرد نمی‌توان تمام عکس‌ها را گرفت.

راهنمایی

از زوجیت عدد عکس‌ها (به تعریف راهنمایی‌های گذشته) استفاده کنید.

راهنمایی

بعد از هر عکس با عدد فرد، لزوما عکسی با عدد زوج گرفته می‌شود. همچنین بعد از هر عکس با عدد زوج، عکسی با عدد فرد گرفته می‌شود.

راهنمایی

اختلاف تعداد عکس‌های ممکن با عدد زوج و تعداد عکس‌های ممکن با عدد فرد، $n$ است.

راهنمایی

برای ارائه‌ی مثال، همان کاری که برای $n$ زوج انجام دادید را انجام دهید.