رشته‌ي نزدیک
۱۳۹۲ رشته به طول ۱۳۹۲ از حروف کوچک انگلیسی با نام‌های $p_1, p_2, ..., p_{1392}$ در اختیار داریم.
فاصله دو رشته $A= a_1, a_2, ..., a_n$ و $B= b_1, b_2, ..., b_n$ را با $d(A,B)$ نمایش می‌دهیم و این مقدار برابر است با تعداد اندیس‌های $i$ که $a_i≠ b_i$ . به عنوان مثال فاصله‌ی دو رشته $salam$ و $palas$ برابر با ۲ است زیرا تنها در مکان‌های اول و آخر با هم تفاوت دارند.
برای رشته‌ی $x$ به طول ۱۳۹۲ مجموع فاصله‌هایش از این ۱۳۹۲ رشته را $D_x$ می نامیم. به رشته‌ای مانند $M$ به طول ۱۳۹۲،نزدیک می‌گوییم اگر به ازای هر رشته $x$ به طول ۱۳۹۲: $$Dm≤Dx$$
الف) به ازای هر سه رشته هم طول دلخواه A,B,C نشان دهید $d(A,B)\le d(A,C)+ d(B,C)$ (۵ نمره)
ب) نشان دهید رشته‌ای مانند $\pi_i$ از این ۱۳۹۲ رشته وجود دارد به طوری که $D_m\le D_{p_i}\le 2D_m$ (۱۰نمره)
پاسخ
الف) کافی است توجه کنیم که اگر دو رشته $A$ و $C$ در جایگاه i ام با هم اختلاف داشته باشند حداقل یکی از دو جفت $(A,B)$ یا $(B,C)$ در جایگاه $i$ ام با هم اختلاف دارند. در نتیجه هر اختلافی که در $d(A,C)$ شمرده می‌شود حداقل در یکی از $d(A,B)$ یا $d(B,C)$ نیز شمرده می‌شود که حکم مسئله را نتیجه می‌دهد.
ب) $p_j$ را نزدیک‌ترین رشته به رشته $M$ در بین ۱۳۹۲ رشته در نظر می‌گیریم و $D_{p_j }$ را محاسبه می‌کنیم:
$$D_{p_j}=\sum_{i=۱}^{1392} d(p_i,p_j ) ≤\sum_{i=۱}^{1392} d(p_i,M)+d(M,p_j ) =D_M+\sum_{i=۱}^{1392} d(M,p_j ) \quad\quad\quad (1)$$
اما با توجه به نحوه انتخاب $p_j$به ازای هر $i$ می‌دانیم $d(M,p_j )≤d(M,p_i)$ و از این موضوع نتیجه می‌گیریم
$$\sum_{i=۱}^{1392} d(M,p_j ) ≤\sum_{i=۱}^{1392} d(M,p_i ) =D_M \quad \quad \quad (2)$$
از $(1)$ و $(2)$ خواهیم داشت $D_{p_j }≤2D_M$.
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
