چطور به راه حل قسمت اول برسیم

وقتی $3n$ وزنه داریم و حدود $2n$ مقایسه، مشخصا باید به ازای هر ۳ وزنه ۲ مقایسه بکنیم.

راه حل قسمت اول

وزنه ها را به دلخواه در $n$ دسته ی ۳ تایی با شماره های ۱ تا $n$ تقسیم میکنیم. از دسته ی اول شروع میکنیم و یکی از وزنه ها را با دو وزنه ی دیگر مقایسه میکنیم (دو بار استفاده از ماشین). بدیهی است که دو وزنه فقط و فقط در شرایطی یکسان (هر دو یک گرمی یا هر دو نیم گرمی) هستند که مجموع وزن آنها طبیعی باشد. این کار را تا دسته ی شماره $n-1$ ادامه میدهیم (تا اینجا $2n-2$ بار از ماشین استفاده کرده ایم). دو حالت پیش می آید:

• تا اینجا ماشین همیشه اعلام کرده «عدد طبیعی». این بدین معنی است که هر سه وزنه در هر دسته که مقایسه شده اند (به جز دسته ی آخر) یکسان بوده اند. چون تنها دو وزنه نیم گرمی داریم، هیچ یک از دسته های ۱ تا $n-1$ نمیتواند شامل وزنه نیم گرمی باشد. پس هر دو وزنه نیم گرمی در دسته ی آخر هستند. کافی است یکی از وزنه های دسته ی آخر (مثلا $a$) را با یکی از وزنه های دسته ی اول (مثلا $b$)مقایسه کنیم. اگر $a$ و $b$ یکسان بودند بدان معنی است که $a$ هم یک گرمی است، پس دو وزنه باقیمانده از دسته ی آخر نیم گرمی هستند. اگر $a$ و $b$ متفاوت بودند چون مطمین هستیم که وزنه های گروه اول همگی یک گرمی بوده اند، قطعا $a$ نیم گرمی است. پس در این حالت کلا $2n-۱$ مقایسه انجام دادیم.
• حداقل در یکی از دسته ها دو وزنه متفاوت (که هنگام مقایسه، مجموع وزنشان طبیعی نبوده) یافته شده اند. این دو وزنه را $a$ و $b$ می نامیم. چون $n>۲$ پس حتما دسته ای وجود دارد که هیچ وزنه ی نیم گرمی در آن وجود ندارد (یعنی یا هر دو مقایسه مربوط به آن دسته یکسان بوده اند، یا اگر $n=3$ و هم در گروه ۱ و هم گروه ۲ مقایسه نابرابر داشته ایم قطعا هر سه وزنه مقایسه نشده در گروه آخر یک گرمی هستند). کافی است $a$ را با یکی از وزنه های دسته مذکور (مثلا $c$) مقایسه کنیم، اگر متفاوت بودند حتما $a$ نیم گرمی است و در صورتی که یکسان بودند $b$ نیم گرمی است. در این حالت هم $2n-1$ مقایسه انجام دادیم.

چطور به راه حل قسمت دوم برسیم

کافی است دقت کنیم که دسته هایی که شامل سه یا بیشتر وزنه هستند که بین آنها مقایسه شده، منجر به یافتن این میشوند که یا تمامی وزنه ها یک گرمی هستند (در حالتی که همه مقایسه ها یکسان باشند) یا اگر یک مقایسه منجر به متفاوت بودن دو وزنه شده باشد یکی از آن دو وزنه نیم گرمی است که به راحتی تشخیص داده میشود. پس باید ثابت کنیم با $2n-2$ مقایسه به اندازه کافی دسته های ۳ تایی تشکیل نمیشود.

راه حل قسمت دوم

فرض کنید ما به جای ماشین جادویی هستیم. کافی است با هر مقایسه اعلام کنیم مجموع دو وزنه مقایسه شده طبیعی است. حال ثابت میکنیم با این روش اولا ما میتوانیم راست بگوییم (یعنی تمام زوج وزنه های مقایسه شده را طوری تعیین کنیم که یکسان باشند) و دوم آن که گاوی قادر به تعیین وزنه های نیم گرمی نباشد.

ابتدا دو لم زیر را ثابت میکنیم:

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

حال فرض کنید گاوی $2n-2$ مقایسه خود را انجام داده و ما همه آنها را طبیعی اعلام کرده ایم. هر زوج وزنه مقایسه شده را با یک نخ به هم وصل کنید. به این صورت دسته هایی از وزنه های متصل به هم تشکیل خواهد شد. اگر یک دسته شامل $i$ وزنه باشد، حداقل $i-1$ مقایسه در آن دسته انجام شده (چرا که اگر وزنه های یک دسته را به دلخواه با اعداد ۱ تا $i$ شماره گذاری کنیم، به جز وزنه اول هر وزنه با حداقل یک مقایسه به وزنه های با شماره کوچکتر از خود متصل است).

همان طور که گفتیم دسته هایی که شامل سه وزنه یا بیتشر هستند برای ما اهمیت دارند. تعداد چنین دسته هایی را $k$ و تعداد وزنه های قرار گرفته داخل آن را $m$ بنامیم. همچنین تعداد کل مقایسه های انجام شده در این دسته ها را $a$ می نامیم. سه معادله زیر داریم:

• چون در هر یک از این دسته ها حداقل سه وزنه داریم، لذا $m \geq 3k$
• چون تعداد مقایسه های انجام شده در هر دسته حداقل به اندازه تعداد وزنه آن دسته منهای ۱ است، پس تعداد کل مقایسه های انجام شده در این دسته ها حداقل به اندازه مجموع تعداد وزنه های این دسته ها منهای تعداد دسته ها است، یعنی $a \geq m-k$
• چون حداکثر $2n-2$ مقایسه انجام شده پس $2n-2\geq a$

با حل این معادلات خواهیم داشت:

$2n-2 \geq a \geq m-k \geq 3k - k=2k$ در نتیجه خواهیم داشت $n-1 \geq k$ . حال دو حالت داریم:

حالت اول اگر کل مقایسه ها در همین دسته ها (شامل حداقل ۳ وزنه) استفاده شده باشد داریم $a=2n-2$ در نتیجه خواهیم داشت :

$m\leq a+k\leq (2n-2) + (n-1) = 3n-3$ و لذا کل عناصر قرار گرفته در دسته های حداقل سه تایی کمتر یا مساوی $3n-3$ خواهد بود. یعنی حداقل ۳ وزنه در این دسته ها قرار نگرفته اند. از سوی دیگر همه مقایسه ها برای دسته ها استفاده شده بود، پس در مورد این سه وزنه هیچ مقایسه ای انجام نشده، لذا طبق لم ۱ گاوی می بازد.

حالت دوم اگر کل مقایسه ها در همین دسته ها استفاده نشده باشد داریم $a <2n-2$ در نتیجه خواهیم داشت:

$m \leq a+k < 3n-3$. این بدان معنا است که حداقل ۴ وزنه در آن دسته ها قرار نگرفته اند. با استفاده از لم زیر ثابت میکنیم در این حالت هم گاوی بازنده است.

لم ۲ اگر چهار وزنه داشته باشیم که هیچ یک از آنها در دسته های حداقل ۳ تایی قرار نگرفته باشند گاوی میبازد. این بدان معنی است که این چهار وزنه یا در دسته های یک تایی (بدون مقایسه با هیچ وزنه دیگری) قرار دارند، یا در دسته های دو تایی (دو وزنه که در مورد آنها فقط یک مقایسه بین خودشان شده باشد). اگر سه وزنه بی مقایسه داشته باشیم که طبق لم ۱ گاوی می بازد. اگر حداقل یک دسته دوتایی داشته باشیم میتوانیم وزنه های این دسته را یکسان، و دو وزنه باقیمانده را هم یکسان در نظر بگیریم. حال اولا با اعلام یکسان بودن وزنه ها در مقایسه ها راست گفته ایم، ثانیا گاوی نمیتواند معلوم کند که کدام یک از این دو زوج شامل وزنه های نیم گرمی است.

بیشتر بخوانیم

بسیاری از توضیحات این مساله با نظریه گراف ها ساده تر قابل بیان هستند. مثلا جایی که از وصل کردن وزنه ها با نخ و تشکیل دسته ها صحبت کردیم، در واقع مولفه های همبندی (دسته ها) را در گرافی که راسهای آن وزنه ها و یال های آن مقایسه ها هستند مشخص کردیم.

یا مثلا جای دیگری که گفتیم برای هر دسته حداقل به تعداد وزنه های آن منهای یک مقایسه لازم است به یک قضیه خیلی معروف از نظریه گرافها اشاره کردیم که تعداد راسهای هر مولفه همبندی از یک گراف حداکثر یکی بیشتر از تعداد یالهای آن مولفه است.

پس مطالعه نظریه گرافها را برای حل این سوال و سوالهای مشابه توصیه میکنم.

سلام

پاسخ رسمی کمیته ی المپیاد کامپیوتر:

به وضوع هنگام استفاده از ماشین اگر مجموع وزن دو سکه طبیعی بود، یعنی دو سکه هم نوع هستند و در غیر این صورت یعنی هم نوع نیستند. پس می توان عمل استفاده از ماشین را یک عمل مقایسه نامید که در پایان آن می توان فهمید دو سکه ی گذاشته شده، هم نوع هستند یا خیر.

الف)

با استقرا روی $n$ ثابت می کنیم گاوی با حداکثر $2n-1$ بار استفاده از ماشین جادویی می تواند یک سکه ی نیم-گرمی از بین $3n$ سکه، پیدا کند.

برای پایه، $n=3$ را در نظر می گیریم. با کمی حالت بندی می توان نشان داد با حداکثر 5 حرکت می توان سکه ای نیم-گرمی را مشخص کرد.

حال فرض می کنیم حکم برای $n=k$ برقرار باشد؛ ثابت می کنیم حکم برای $n=k+1$ نیز برقرار است. برای اثبات حکم، $3k+3$ سکه را در نظر می گیریم. 2 سکه را با هم مقایسه می کنیم. دو حالت می توان متصور بود:

• اگر متفاوت بودند، کافی است یکی از آن ها ($x$) را برداشته و با 3 سکه ی دیگر مقایسه کنیم. اگر در این 3 مقایسه دست کم 2 تا از آن ها به تساوی کشید، یعنی $x$ سکه ای 1-گرمی است و سکه ی مقابل آن در مقایسه ی نخست نیم-گرمی است؛ در غیر این صورت $x$ سکه ای نیم-گرمی است.

• اگر برابر بودند، یکی از آن ها را برداشته و با سکه ای دیگر مقایسه می کنیم. اگر باز هم برابر بودند، یعنی این 3 سکه، 1-گرمی هستند و برای بقیه ی سکه ها، طبق فرض استقرا می توان کار را انجام داد؛ اما اگر این 2 برابر نبودند، کافی است باز هم 3 سکه ی دل خواه دیگر انتخاب کنیم و مانند حالت قبل، این کار را انجام دهیم.

ب)

ابتدا ثابت می کنیم هر گراف ساده ی $n$ رأسی با $k$ مولفه، دست کم $n-k$ یال دارد. ابتدا یال ها را در نظر نمی گیریم و یکی پس از دیگری یال ها را می گذاریم. هر یالی که می گذاریم، حداکثر یکی از تعداد مولفه ها کم می کند. پس گراف $n$ رأسی با $k$ مولفه ، دست کم $n-k$ یال دارد.

فرض کنید گاوی با تعدادی مقایسه، سکه ای نیم-گرمی را پیداکرده باشد. گرافی ساده با $3n$ رأس می سازیم که هر رأس آن یک سکه باشد و بین دو رأس آن، یال می کشیم اگر و تنها اگر گاوی بین سکه های متناظر با آن ها، مقایسه انجام داده باشد.

ابتدا ثابت می کنیم این گراف حداکثر 2 مولفه ی 1 رأسی دارد. فرض کنیم دست کم 3 مولفه ی 1 رأسی داشته باشد. در این صورت اگر سکه های نیم-گرمی در بین این 3 رأس باشند، نمی توان با اطمینان یک سکه ی نیم-گرمی را تشخیص داد.

حال ثابت می کنیم این گراف حداکثر 1 مولفه ی 2 رأسی دارد. مانند قسمت قبل فرض کنید دست کم 2 مولفه ی 2 رأسی داشته باشیم. اگر سکه های نیم-گرمی در بین این 4 رأس باشند، نمی توان با اطمینان یک سکه ی نیم-گرمی را تشخیص داد.

حال ثابت می کنیم امکان ندارد هم مولفه ی 2 رأسی داشته باشیم و هم 2 مولفه ی تک رأسیوجود داشته باشد. فرض کنیم هم مولفه ی 2 رأسی داشته باشیم و هم 2 مولفه ی تک رأسی وجود داشته باشد.در این صورت اگر سکه های نیم-گرمی در بین این 4 سکه باشند، بار هم با اطمینان نمی توان سکه ای نیم-گرمی را پیدا کرد.

حال اگر در گراف مورد نظر، 2 مولفه ی تک راسی داشته باشیم، گراف ما حداکثر

$$\lfloor \frac{3n-2}{3} \rfloor + 2 =n+1$$

مولفه دارد؛ در غیر این صورت نیز گراف ما حداکثر

$$\lceil \frac{3n-3}{3} \rceil+1+1=n+1$$

مولفه خواهد داشت. پس گراف ما دسته کم $3n-(n+1)=2n-1$ یال لازم دارد که حکم مسئله را ثابت می کند.