المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله‌ی سوم:دوره‌ی ۲۲:سوال ۵

ﺷﻨﮕﻮل و ﮐﺎرت‌های ﺧﺒﯿﺚ!

ﺷﻨﮕﻮل ﺑﺮای هر ﯾﮏ از اﻋﺪاد ١ ﺗﺎ ١٠ (ﺷﺎﻣﻞ ﺧﻮد اﯾﻦ اﻋﺪاد)، ﻧﻤﺎﯾﺶ ﻣﺒﻨﺎی دوی آن ﻋﺪد را روی ﯾﮏ ﮐﺎرت ﺳﻔﯿﺪ ﻧﻮﺷﺘﻪ اﺳﺖ. او ﺑﺎ ﭘﺸﺖ ﺳﺮ هم ﻗﺮار دادن اﯾﻦ ١٠ ﮐﺎرت در ﯾﮏ ردﯾﻒ ﻣﯽﺗﻮاﻧﺪ اﻋﺪاد ٢٩ ﺑﯿﺘﯽ ﻣﺨﺘﻠﻔﯽ ﺑﺴﺎزد. دﻗﺖ ﮐﻨﯿﺪ ﮐﻪ ﺳﻤﺖ ﭼﭗ ﺗﺮﯾﻦ ﺑﯿﺖ هر ﮐﺎرت ﺣﺘﻤﺎً ١ اﺳﺖ. همﭼﻨﯿﻦ ﺷﻨﮕﻮل ﻣﺠﺎز ﺑﻪ ﭼﺮﺧﺎﻧﺪن ﯾﺎ ﺑﺮﮔﺮداﻧﺪن ﮐﺎرت ها ﻧﺒﻮدﻩ و ﻓﻘﻂ ﻣﯽﺗﻮاﻧﺪ ﺗﺮﺗﯿﺐ ﮐﺎرت‌ها را ﺟﺎﺑﺠﺎ ﮐﻨﺪ.

اﻟﻒ): اﮔﺮ کوچک‌ترین ﻋﺪد ٢٩ ﺑﯿﺘﯽای ﮐﻪ ﺷﻨﮕﻮل ﻣﯽﺗﻮاﻧﺪ ﺑﺎ اﺳﺘﻔﺎدﻩ از ﺗﻤﺎم ١٠ ﮐﺎرت ﺑﺴﺎزد $M_1$ ﺑﺎﺷﺪ و ﺑﺰرگ‌ترین ﻋﺪد ٢٩ ﺑﯿﺘﯽای ﮐﻪ ﺷﻨﮕﻮل ﻣﯽﺗﻮاﻧﺪ ﺑﺎ اﺳﺘﻔﺎدﻩ از ﺗﻤﺎم ١٠ ﮐﺎرت ﺑﺴﺎزد $M_2$ ﺑﺎﺷﺪ، در اﯾﻦﺻﻮرت ﺑﺎﻗﯽﻣﺎﻧﺪﻩی ﺗﻘﺴﯿﻢ $M_1 \times M_2$ ﺑﺮ $\Delta$ ﭼﻨﺪ اﺳﺖ؟

ب): اﮔﺮ ﺗﻌﺪاد اﻋﺪاد ٢٩ ﺑﯿﺘﯽای ﮐﻪ ﺷﻨﮕﻮل ﻧﻤﯽﺗﻮاﻧﺪ ﺑﺎ اﯾﻦ ١٠ ﮐﺎرت آن‌ها را ﺑﺴﺎزد را $P$ ﺑﻨﺎﻣﯿﻢ، ﺑﺎﻗﯽﻣﺎﻧﺪﻩی ﺗﻘﺴﯿﻢ $P_2$ ﺑﺮ $\Delta$ ﭼﻨﺪ اﺳﺖ؟

ج): اﮐﻨﻮن ﻓﺮض ﮐﻨﯿﺪ ﺑﻪﺟﺎی ١٠ ﮐﺎرت ﺑﺎ ﺷﻤﺎرﻩهﺎی ١ ﺗﺎ ١٠، ﺷﻨﮕﻮل هﻤﻪی اﯾﻦ ﮐﺎرهﺎ را ﺑﺎ ١٦ ﮐﺎرت ﺑﺎ ﺷﻤﺎرﻩهای ١ ﺗﺎ ١٦ ﺑﺨﻮاهد اﻧﺠﺎم ﺑﺪهد ﺗﺎ اﻋﺪاد ٥٤ ﺑﯿﺘﯽ ﺑﺴﺎزد. در اﯾﻦ ﺻﻮرت اﮔﺮ کوچک‌ترین ﻋﺪدی ﮐﻪ ﺷﻨﮕﻮل ﻣﯽﺗﻮاﻧﺪ ﺑﺎ اﺳﺘﻔﺎدﻩ از ﺗﻤﺎم ١٦ ﮐﺎرت ﺑﺴﺎزد $M$ ﺑﺎﺷﺪ و اﯾﻦ ﻋﺪد ﺑﻪ $K$ ﻃﺮﯾﻖ (از !١٦ ﻃﺮﯾﻖ ﻣﻤﮑﻦ) ﻗﺎﺑﻞ ﺳﺎﺧﺘﻦ ﺑﺎﺷﺪ، در اﯾﻦﺻﻮرت ﺑﺎﻗﯽﻣﺎﻧﺪﻩی ﺗﻘﺴﯿﻢ $K \times M$ ﺑﺮ $\Delta$ ﭼﻨﺪ اﺳﺖ؟


ابزار صفحه