سوال ۴

گزینه (۱) درست است.

لم ۱: در حالت بهینه روی هر خانه یک عدد اول قرار می‌گیرد. اگر حالت بهینه‌ای وجود دارد که عددی در آن اول نیست، آن عدد را تقسیم بر یکی از عوامل اولش می‌کنیم. همچنان هر دو همسایه نسبت به هم اول هستند اما مجموع کاهش یافته است.

لم ۲: اگر از عدد اول $i$ تعداد $c_i$ تا داشته باشیم. اگر $x < y$ باشد آنگاه $c_x \geq c_y$. اگر حالت بهینه این خلاف شرایط ذکر شده وجود داشته باشد اگر مقادیر تمامی رئوس $x$ و $y$ را برعکس کنیم (یعنی اگر $x$ بود $y$ و اگر $y$ بود $x$ کنیم). آنگاه مجموع کاهش می‌یابد چون $x < y, c_x < c_y \implies x \times c_x + y \times c_y > x \times c_y + y \times c_x$
برای ادامه اثبات دو دور از گراف پترسن‌ را در نظر می‌گیریم. یکی دور بیرونی که به شکل پنج‌ضلعی است. دیگری دور درونی که به شکل ستاره است.

لم ۳: در عددگذاری بیش از ۴ راس با یک عدد وجود ندارد. اگر حداقل ۵ راس با یک عدد داشته باشیم، طبق اصل لانه کبوتری حداقل ۳ تا از آن‌ها در یک دور و از میان آن‌ها ۲ تا کنار هم هستند. پس دوعدد وجود دارد که نسبت به هم اول نخواهند بود.

لم ۴: در عددگذاری نمی‌توان دو عدد داشت که هر یک روی ۴ راس نوشته شده باشند. در هر دور از هر عدد دوتا داریم (در هر دور ۳ تا از یک عدد نداریم). فرض کنید اعداد ۲ و ۳ باشند. بدون کم شدن از کلیت فرض کنید اعداد در دور بیرونی مطابق شکل زیر قرار گرفته‌‌اند. می‌دانیم در دایره‌های آبی تنها یک عدد ۲، در دایره‌های قرمز تنها‌ یک عدد ۳ و در دایره زرد می‌توان ۲ یا ۳ نوشت. پس سه عدد می‌توان نوشت. پس نمی‌توان چهار عدد ۲ و ۳ در خانه‌های دور درونی قرار داد.

طبق لم ۱، ۲ هر حالت معتبر را می‌توان با یک دنباله نزولی $c_2, c_3, c_5, ...$ نشان داد که تعداد موجود از هر عدد اول را مشخص می‌کند.طبق لم ۳ و ۴ اعداد کوچک تر مساوی ۴ است و حداکثر یک عدد ۴ داریم. مطابق گراف زیر می‌دانیم دنباله‌ی $c = 4, 3, 3, 0, 0, ...$ معتبر است:

به ازای هر دنباله معتبر دیگر می‌دانیم هر یک از سه عنصر اول، از متناظر آن‌ها در دنباله c کوچک‌تر مساوی است، پس مجموع اعداد استفاده شده در هر حالت دیگر کمتر نخواهد بود. پس جواب ۳۲ است.