الف) ثابت می‌کنیم پاسخ مسئله برابر با

$$\lfloor max_{1 \le i \le k} lg(a_k + 1) \rfloor$$

است.

ابتدا ثابت می‌کنیم، اگر شکل گراف شهرهای یک کشور، یک مسیر به ترتیب با شهرهای $v_1, v_2, \ldots, v_p$ باشد، حداقل $\lfloor lg(p) \rfloor$ مرحله، لازم است. برای این کار، کافی است ثابت کنیم اگر $p \ge 2^q$ باشد، حداقل $q$ مرحله، لازم است. از استقرای قوی روی $p$ استفاده می‌کنیم. برای پایه‌ی استقرا، $p=1$ را در نظر می‌گیریم. داریم $p \ge 2^0$ و تعداد مراحل لازم برای انجام کار، ۰ است. فرض کنید حکم برای $<p$ برقرار باشد. ثابت می‌کنیم حکم برای $p$ نیز برقرار است. فرض کنید در مرحله‌ی ابتدایی، شهر $v_i$ را انتخاب کنیم. اگر $i \le 2^{q-1}$ باشد؛ ممکن است دست‌گاه شهر $v_{i+1}$ را نشان دهد، متوجه می‌شویم بمب در یکی از شهرهای $v_{i+1}, v_{i+2}, \ldots, v_{p}$ است و طبق فرض استقرا دست کم $q-1$ مرحله لازم است (زیرا $p - i \ge 2^{q-1}$). پس با یک مرحله‌ی ابتدایی، دست کم $q$ مرحله لازم است و حکم ثابت می‌شود. در حالتی که $i >2^{q-1}$ نیز به طریق مشابه اثبات انجام می‌شود.

به روشی مشابه روند بالا، می‌توان به راحتی ثابت کرد برای یک مسیر $p$ رأسی، $\lfloor lg(p) \rfloor$ مرحله کافی نیز هست (روش جست‌وجوی دودویی).

حال فرض کنید شکل گراف شهرهای یک کشور، به صورت یک دور به طور $p$ باشد. هر رأسی در ابتدا انتخاب شود، نیمی از رأس‌ها حذف می‌شوند و تنها یک مسیر به طور $\lfloor \frac{p}{2} \rfloor$ باقی می‌ماند. انتخاب هر شهر دیگر به جز این مسیر، اطلاعاتی در مورد شهر بمب‌گذاری شده به ما اضافه نمی‌کند و یک مسیر باقی می‌ماند. پس طبق قسمت قبل، برای یک دور به طول $p$، کمینه‌ی تعداد مراحل برابر $1 + \lfloor lg(\frac{p}{2}) \rfloor = \lfloor lg(p) \rfloor$ است.

حال ثابت می‌کنیم علی‌رضا و فرهاد، دست کم به

$$\lfloor max_{1 \le i \le k} lg(a_k+1) \rfloor$$

مرحله در کشور واس‌ماس نیاز دارند. بدون از دست دادن کلیت مسئله فرض کنید $a_1 \ge a_2, a_3, \ldots, a_k$ باشد. فرض کنید بمب در یکی از شهرهای استان ۱ باشد و علی‌رضا و فرهاد این اطلاعات اضافه را از ابتدا بدانند. انتخاب هر شهر جز پایتخت و شهرهای استان ۱، پاسخ مشخصی دارد و اطلاعات جدیدی اضافه نمی‌کند. پس یک دور باقی می‌ماند و فرهاد و علی‌رضا طبق قسمت قبل حداقل به

$$\lfloor lg(a_1+1) \rfloor = \lfloor max_{1 \le i \le k} lg(a_k+1) \rfloor$$

مرحله نیاز دارند.

پس فقط کافی است ثابت کنیم

$$\lfloor max_{1 \le i \le k} lg(a_k+1) \rfloor$$

مرحله برای پیدا کردن بمب کافی است. اگر فرهاد و علی‌رضا در ابتدا پایتخت را انتخاب کنند و پایتخت یکی از شهرهای استان $i$ را به آن‌ها نشان بدهد (بدون از دست دادن کلیت مسئله فرض کنید شهر شماره ۱ از این استان)، آن‌گاه بمب در یکی از شهرهای $1, 2, \ldots, a_{\lfloor \frac{a_i + 1}{2} \rfloor}$ است و طبق قسمت‌های گفته شده می‌توان با حداکثر $\lfloor max_{1 \le i \le k} lg(\frac{a_k + 1}{2}) \rfloor$ مرحله بمب را پیدا کرد. با احتساب یک مرحله‌ی اولیه، می‌توان نتیجه گرفت با حداکثر

$$\lfloor max_{1 \le i \le k} lg(a_k + 1) \rfloor$$

می‌توان بمب را پیدا کرد.

ب) ثابت می‌کنیم پاسخ برابر $r$ است.

ابتدا ثابت می‌کنیم $r$ مرحله برای پیدا کردن بمب، کافی است. آن شهری که کم‌ترین عدد نسبت داده شده را دارد، در ابتدا انتخاب می‌کنیم. سپس در هر مرحله همان شهری را انتخاب می‌کنیم که دست‌گاه به ما نشان می‌دهد. به این ترتیب پس از حداکثر $r$ مرحله، شهر بمب‌گذاری شده پیدا می‌شود (توجه کنید اگر $r$-امین مرحله انجام شد و هنوز بمب پیدا نشده بود، بمب حتمن در شهر بعدی است و نیازی به چک کردن آن نیست).

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

با استقرا روی $r$ ثابت می‌کنیم برای پیدا کردن بمب، حداقل $r$ مرحله لازم است. برای پایه‌ی استقرا $r=0$ (درخت تک‌رأسی) را در نظر می‌گیریم و حکم واضح است. فرض کنید حکم برای $r-1$ برقرار باشد؛ ثابت می‌کنیم حکم برای $r$ نیز برقرار است.

• اگر در ابتدا ریشه‌ی درخت انتخاب شود، زیردرختی که بمب در آن است، مشخص می‌شود. انتخاب هر شهر از زیردرخت دیگر در ادامه، اطلاعاتی اضافه نمی‌کند؛ زیرا پاسخ آن مشخص است. پس طبق فرض استقرا در ادامه حداقل به $r-1$ مرحله نیاز داریم و حکم ثابت می‌شود.
• اما اگر در ابتدا ریشه را انتخاب نکنیم، ممکن است بمب در زیردرخت دیگر باشد. فرض کنید علاوه بر این که بمب، یک شهر را نشان می‌دهد، پس از این انتخاب، این اطلاعات اضافی نیز به علی‌رضا و فرهاد داده شود که بمب در زیردرخت دیگر است. پس انتخاب هر شهر جز زیردرخت دیگر، اطلاعاتی به آن دو اضافه نمی‌کند و پاسخ آن مشخص است. پس طبق فرض استقرا باز هم در ادامه نیاز به حداقل $r-1$ مرحله داریم و حکم ثابت می‌شود.

پس ثابت کردیم گرافی داریم که در آن حداقل $r$ مرحله لازم است.

پس پاسخ برابر $r$ است.

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

برهان خلف می‌زنیم. فرض کنید یکی از شهرهای مجاور $v(S)$ مانند $u$ انتخاب شود و تعداد شهرهای نامزد برای بمب داشتن، بیش از نصف $S$ بماند. پس $u$ به ازای بیش از $\frac{|S|}{2}$ شهر، فاصله‌ی کم‌تری از آن شهرها نسبت به $v(S)$ دارد و فاصله‌ی دیگر شهرهای $S$ نیز از $u$، حداکثر یکی بیش‌تر از فاصله‌ی‌شان از $v(S)$ است. پس مجموع فواصل $u$ از بقیه‌ی شهرهای $S$ در این مرحله کم‌تر بوده است و به تناقض می‌رسیم. پس فرض خلف باطل است و حکم ثابت می‌شود.