پلیس و شاهدان
در جریان یک سرقت از یک شعبه‌ی بانک، سارقان از دو راه متفاوت از یازده راهی که به بانک ختم می‌شد گریختند. بعد از این سرقت پلیس برای شناسایی دو مسیری که دزدها از طریق آن‌ها فرار کرده بودند، شروع به جمع‌آوری اطلاعات از شاهدان حادثه کرد و برای تشویق شاهدان به گزارش دادن، برای هر شاهدی که یکی از دو مسیر را درست گزارش کرده باشد، یک جایزه و برای هر شاهدی که هر دو مسیر را درست نشان دهد، دو جایزه تعیین کرد. به همین دلیل، برخی از شاهدان سرقت، حتی اگر فقط یکی از دو راه فرار دزدان را دیده بودند، به امید دریافت جایزه‌ی دوم، مسیر دیگری را نیز به صورت تصادفی گزارش می‌دادند. البته ممکن است برخی از شاهدان فقط یک مسیر را گزارش کنند. به هر حال، هر شاهد حداقل یک مسیر فرار را به درستی گزارش می‌کند.
الف) پلیس حداقل چند گزارش متفاوت باید دریافت کند تا مطمئن باشد که می‌تواند دو مسیر را به درستی شناسایی کند؟ توضیح دهید.
ب) پلیس با حداقل چند گزارش از گزارش‌هایی که دریافت کرده است می‌تواند مسیر فرار دزدان را برای دادگاه اثبات کند؟ توضیح دهید.
پاسخ
الف) پلیس در بدترین حالت با ۱۳ گزارش متفاوت می‌تواند مسیر فرار دزدان را شناسایی کند. واضح است که هر سه گزارش دوتایی که شامل یک مسیر مشخص (مثلا $a_1$) باشند، نشان می‌دهند که $a_1$ یکی از راه‌های فرار دزدان بوده است. از سوی دیگر ممکن است پلیس در بدترین حالت ۱۱ گزارش دریافت کند که فقط مشخص‌کننده‌ی $a_1$ باشند:
$$(a_1,a_2),(a_1,a_3),…,(a_1,a_{11}),(a_1)$$
با این یازده گزارش پلیس فقط می‌تواند $a_1$ را شناسایی کند. برای شناسایی مسیر دوم (مثلا $a_2$) پلیس در بدترین حالت به ۲ گزارش دیگر احتیاج دارد که مطمئنا هر دو شامل $a_2$ خواهند بود.
با توجه به استدلال فوق، واضح است که با ۱۲ گزارش متفاوت ممکن است پلیس نتواند یکی از راه‌ها را شناسایی کند.
ب) در بدترین حالت پلیس با ۵ گزارش متفاوت می‌تواند مسیرهایی را که شناسایی کرده است را به دادگاه اثبات کند. اگر پلیس گزارش تک عضوی داشته باشد، با دو گزارش $(a_2),(a_1)$ یا با چهار گزارش $(a_1),(a_2,a_m),(a_2,a_n),(a_2,a_p)$ خواهد توانست راه‌ها را اثبات کند. ولی اگر پلیس هیچ گزارش تک عضوی دریافت نکرده باشد، با سه گزارش شامل $a_1$ که در صورت امکان یکی شامل $a_2$ نیز هست، $a_1$را با دو گزارش دیگر که شامل $a_2$ هستند (جمعا سه گزارش شامل $a_2$) $a_2$ را به دادگاه اثبات می‌کند. اگر نتواند ۳ گزارش شامل $a_1$ را طوری انتخاب کند که یکی شامل $a_2$ باشد، فقط دو گزارش شامل $a_2$ برای اثبات کافی است.
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
