المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی اول:دوره ی ۲۲:سوال ۱۰

سوال ۱۰

دارا و سارا با هم این بازی را انجام می دهند. ابتدا دارا اعداد ٫۹… ۱٫۲٫ را به ترتیب مقابل در شکل قرار می‌دهد. سپس سارا جای تعداد دلخواهی از این اعداد را با هم عوض می کند تا اعداد حسابی بُر بخورد. اکنون دارا باید با تعدادی حرکت مجاز اعداد را به شکل اولیه (شکل مقابل) برگرداند. در هر حرکت مجاز دارا ابتدا بین سطر ۵ خانه ای شکل٬ یا ستون ۵ خانه‌ای شکل یکی را انتخاب کرده و ۵ عدد آن سطر یا ستون را برداشته و به دلخواه خودش دوباره می‌چیند.

در بدترین حالت بُر زدن سارا٬ دارا پس از چند حرکت می تواند تمام اعداد را به شکل اولیه سر جای خودش بگذارد؟

  1. ۴
  2. ۱۰
  3. ۵
  4. ۸
  5. ۹

پاسخ

گزینه‌ی «۵» درست است.

میﺑﯿﻨﯿﻢ ﮐﻪ در شکل ﻧﻬﺎﯾﯽ ﺗﻤﺎمی اﻋﺪاد ﻓﺮد یک رقمی در ﺳﻄﺮ و اﻋﺪاد زوج (ﺑﻪ اﻧﻀﻤﺎم ﻋﺪد یک در ﻣﺮﮐﺰ) در ﺳﺘﻮن ﻫﺴﺘﻨﺪ.

از ﺳﻮی دیگر، ﻫﺮ ﻋﺪد زوجی ﮐﻪ در ﺳﻄﺮ شکل ﺑﺎﺷﺪ و ﯾﺎ ﻫﺮ ﻋﺪد ﻓﺮدی ﮐﻪ در ﺳﺘﻮن ﺑﺎﺷﺪ ﺑﺮای رﺳﯿﺪن ﺑﻪ ﻣﻘﺼﺪ ﻧﻬﺎﯾﯽ ﺧﻮدش، ﺣﺘﻤﺎً ﺑﺎﯾﺪ یک ﺑﺎر ﺑﻪ وﺳﻂ شکل ﺑﯿﺎﯾﺪ و ﺳﭙﺲ ﺑﻪ ﻣﺤﻞ ﻧﻬﺎﯾﯽاش ﺑﺮود. ﺑﺎ اﯾﻦ وﺻﻒ ﮐﺎفی اﺳﺖ ﺣﺎلتی را در ﻧﻈﺮ بگیرﯾﻢ ﮐﻪ در آن ١ در وﺳﻂ ﺑﻮد و ﺗﻤﺎمی اﻋﺪاد زوج در ﺳﻄﺮ و ﺗﻤﺎمی اﻋﺪاد ﻓﺮد در ﺳﺘﻮن ﺑﺎﺷﻨﺪ.

در اﯾﻦ ﺣﺎﻟﺖ ﺑﻪ ازای ﻫﺮ یک از اﻋﺪاد ٢ ﺗﺎ ٩، اﻟﺰاﻣﺎً ﺑﺎﯾﺪ ﺣﺪاﻗﻞ یک ﺑﺎر ﻫﺮ ﮐﺪام اﯾﻦ اﻋﺪاد ﺑﻪ ﻣﺮﮐﺰ ﺑﯿﺎﯾﻨﺪ. (ﭼﺮا؟) ﭘﺲ ﺗﺎ اﯾﻦ ﺟﺎی ﮐﺎر ٨ ﺣﺮﮐﺖ اﻧﺠﺎم داده اﯾﻢ. ﭘﺲ از اﯾﻦ ٨ ﺣﺮﮐﺖ ﻧﯿﺰ، می‌داﻧﯿﻢ ﻋﺪد ﻣﺮﮐﺰی ١ ﻧﯿﺴﺖ.

ﭘﺲ یک ﺣﺮﮐﺖ ﻧﯿﺰ ﺑﺮای آوردن ١ ﺑﻪ ﻣﺮﮐﺰ ﻻزم اﺳﺖ. ﭘﺲ ﺑﺮای اﯾﻦ ﻣﺮﺗﺐ ﺳﺎزی ﺣﺪاﻗﻞ ٩ ﺣﺮﮐﺖ ﻧﯿﺎز اﺳﺖ و ﺑﺎ ٩ ﺣﺮﮐﺖ ﻫﺮ ﺗﺮﮐﯿﺒﯽ را میﺗﻮان درﺳﺖ ﮐﺮد؛ ﮐﺎفی اﺳﺖ اﻋﺪادی ﮐﻪ در ﺳﻄﺮ ﯾﺎ ﺳﺘﻮن ﻣﻨﺎﺳﺐ ﺧﻮدﺷﺎن ﻧﯿﺴﺖ را یکی یکی (ﺑﺎ ﺗﻨﺎوب ﺳﻄﺮ و ﺳﺘﻮن در ﺻﻮرت ﻧﯿﺎز) ﺑﻪ ﻣﺮﮐﺰ ﺑﯿﺎورﯾﻢ.


ابزار صفحه