وزنه‌ها و ماشین جادویی

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

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

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

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

1. اگر متفاوت بودند، کافی است یکی از آن‌ها ($x$) را برداشته و با ۳ سکه‌ی دیگر مقایسه کنیم. اگر در این ۳ مقایسه، دست کم ۲ تا از آن‌ها به تساوی کشید، یعنی $x$ سکه‌ای ۱-گرمی است و سکه‌ی مقابل آن در مقایسه‌ی نخست، نیم-گرمی است؛ در غیر این صورت $x$‌ سکه‌ای نیم-گرمی است.
2. اگر برابر بودند، یکی از آن‌ها را برداشته و با سکه‌ای دیگر مقایسه می‌کنیم. اگر باز هم برابر بودند، یعنی این ۳ سکه، ۱-گرمی هستند و برای بقیه‌ی سکه‌‌ها، طبق فرض استقرا می‌توان کار را انجام داد؛ اما اگر این برابر نبودند، کافی است باز هم ۳ سکه‌ی دل‌خواه دیگر انتخاب کنیم و مانند حالت قبل، کار را انجام دهیم.

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

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

ابتدا ثابت می‌کنیم این گراف حداکثر ۲ مولفه‌ی ۱ راسی دارد. فرض کنیم دست کم ۳ مولفه‌ی ۱ راسی داشته باشد. در این صورت اگر سکه‌های نیم-گرمی در بین این ۳ راس باشند، نمی‌توان با اطمینان یک سکه‌ی نیم-گرمی را تشخیص داد.

حال ثابت می‌کنیم این گراف حداکثر ۱ مولفه‌ی ۲ راسی دارد. مانند قسمت قبل فرض کنید دست کم ۲ مولفه‌ی ۲ راسی داشته باشیم. اگر سکه‌های نیم-گرمی در بین این ۴ راس باشند، نمی‌توان با اطمینان یک سکه‌ی نیم-گرمی را تشخیص داد.

حال ثابت می‌کنیم امکان ندارد هم مولفه‌ی ۲ راسی داشته باشیم و هم ۲ مولفه‌ی تک راسی وجود داشته باشد. فرض کنید هم مولفه‌ی ۲ راسی داشته باشیم و هم مولفه‌ی تک راسی وجود داشته باشد. در این صورت اگر سکه‌های نیم-گرمی در بین این ۴ سکه باشند، باز هم با اطمینان نمی‌توان سکه‌ای نیم-گرمی را پیدا کرد.

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

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

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

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

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