بمب‌گذاری واس اوناس
در یک دنیا، هر کشور تعدادی شهر دارد و بین هر دو شهر یا جاده‌ی مستقیم دوطرفه وجود دارد یا ندارد. دو شهر را مجاور می‌گوییم، اگر با جاده‌ی مستقیم به هم وصل باشند. می‌دانیم از هر شهر می‌توان با طی کردن تعدادی جاده، به هر شهر دیگر رسید. فاصله‌ی بین دو شهر را کم‌ترین تعداد جاده‌هایی در نظر می‌گیریم که برای رفتن از یکی از این دو شهر به دیگری، باید طی کرد.
الف) علی‌رضا و فرهاد، در کشور واس‌ماس زندگی می‌کنند. این کشور، از یک پایتخت و $k$ استان با شماره‌های $1, 2, \ldots, k$ تشکیل شده است. استان $i$، $a_i$ شهر با شماره‌های $1, 2, \ldots, a_i$ دارد. در هر استان $i$، شهرهای ۱ و ۲ به هم، شهرهای ۲ و ۳ به هم، … و شهرهای $a_{i}-1$ و $a_i$ به هم جاده دارند. هم‌چنین در هر استان $i$، شهرهای ۱ و $a_i$ به پایتخت، جاده دارند. در واقع جاده‌های این کشور، مانند شکل زیر است:
یک تروریست، در یکی از شهرهای این کشور، بمب‌گذاری کرده است. علی‌رضا و فرهاد که به تازگی پلیس شده‌اند، برای پیدا کردن شهر بمب‌گذاری شده، مأمور شده‌اند. آن‌ها یک دستگاه بمب‌یاب دارند. اگر در شهری مانند $T$، این دستگاه را استفاده کنند، چنان‌چه شهر $T$ بمب‌گذاری شده باشد، دستگاه به ما می‌گوید و اگر شهر $T$ بمب‌گذاری نشده باشد، دستگاه در میان شهرهای مجاور $T$، شهری را نشان می‌دهد که کم‌ترین فاصله را با شهر بمب‌گذاری شده دارد (اگر چند شهر با این خاصیت وجود داشت، دستگاه به طور تصادفی یکی از آن‌ها را نشان می‌دهد). استفاده از این دستگاه، بسیار هزینه‌بر است؛ پس علی‌رضا و فرهاد می‌خواهند با کم‌ترین تعداد استفاده از دستگاه، شهر بمب‌گذاری شده را پیدا کنند. کم‌ترین تعداد دفعاتی که آن‌ها باید از دستگاه استفاده کنند، تا به طور مطمئن بتوانند بمب را پیدا کنند، چقدر است؟ پاسخ را بر حسب اعداد $a_1, a_2, \ldots, a_k$ بیان کنید.
ب) اتفاق ناگوار بمب‌گذاری، در کشور ماس‌ماس نیز رخ داد. پادشاه کشور ماس‌ماس تصمیم گرفته است از گروهی زبده برای خنثی کردن این بمب استفاده کند. پس از عمل‌کرد فوق‌العاده‌ی علی‌رضا و فرهاد در خنثی کردن بمب کشور واس‌ماس، پادشاه کشور ماس‌ماس تصمیم گرفت مأموریت را به این دو نفر و دستگاه عجیب‌شان بسپارد. پادشاه کشور ماس‌ماس، به هر شهر یک عدد نسبت داده است و آن عدد، برابر با فاصله‌ی دورترین شهر کشور تا شهر مذکور است. علی‌رضا و فرهاد، اطلاعاتی در مورد تعداد شهرها و نحوه‌ی جاده‌کشی کشور ماس‌ماس ندارند. آن‌ها فقط می‌دانند کم‌ترین عدد نسبت داده شده به شهرها، $r$ است. قرار است هزینه‌ی دستگاه را پادشاه بدهد. علی‌رضا و فرهاد ادعا می‌کنند پس از گرفتن نقشه‌ی جاده‌کشی کشور، خواهند توانست با حداکثر $f(r)$ بار استفاده از دستگاه، شهر بمب‌گذاری شده را پیدا کنند. پادشاه نیز پس از شنیدن این حرف، نقشه را به آن‌ها می‌دهد. با توجه به نداشتن تعداد شهرها و نقشه‌ی جاده‌کشی شهرها قبل از بیان ادعا، کمینه‌ی $f(r)$ را بیابید.
ج) عصبانیت بمب‌گذاران پس از خنثی شدن دو عملیات قبلی، دو چندان شد و آن‌ها این بار تصمیم گرفتند در کشور دوست و هم‌سایه (باس‌ماس) بمب‌گذاری کنند! این کشور $n$ شهر دارد. ثابت کنید هر گونه شهرهای این کشور، جاده‌کشی شده باشند، علی‌رضا و فرهاد می‌توانند با کم‌تر از $\lfloor lg(n) \rfloor + 1$ بار استفاده از دستگاه، شهر بمب‌گذاری شده را پیدا کنند.
توجه: منظور از $lg(n)$، لگاریتم $n$ در مبنای ۲ است. برای مثال $lg(1024) = 10$ و $lg(20) = 4.32192\ldots$ است. هم‌چنین منظور از $\lfloor x \rfloor$ بزرگ‌ترین عدد صحیحی است که از $x$ بیش‌تر نیست. برای مثال $\lfloor 2.3 \rfloor = 2$ و $\lfloor 5 \rfloor = 5$ است.
پاسخ
الف) ثابت می‌کنیم پاسخ مسئله برابر با
$$\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$ در این مرحله کم‌تر بوده است و به تناقض می‌رسیم. پس فرض خلف باطل است و حکم ثابت می‌شود.