المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی دوم:دوره ی ۱۴:سوال ۴

خاطره‌نویسی بارون

پس از این که «ویولانته دو ریوالنده» (Violante de Rivalonde) برای همیشه از نزد «بارون کوزیمو لاورس دو روندو» (Baron CosimoLaverse du Rondo) رفت، بارون از فرط ناراحتی خاطره‌نویسی‌های روزانه خود را متوقف کرد. اما پس از مدتی تصمیم گرفت دوباره آن را آغاز کند. اما این بار می‌خواست طوری بنویسد که تنها خودش بفهمد. بنابراین یک زبان رمز ابداع کرد که فقط از دو علامت X و O تشکیل شده بود و از این علائم برای نشان دادن حروف، فواصل خالی و نشانه‌های سجاوندی زبان مادری خود (که از این به بعد به آن‌ها هم حروف می‌گوییم) استفاده می‌کرد. به‌این‌ ترتیب که برای هرکدام از این حروف، رمزی از علائم X و O تعیین کرد، مثلا برای حرف d از رمز OX، برای s از رمز OOX، برای n از OXO، برای l از XO، برای a از XX، برای p از OO و برای e از X استفاده کرد. او برای نشان دادن یک کلمه، رمزهای تک‌تک حروف آن کلمه را به ترتیب پشت سر هم می‌نوشت.

یک روز که بارون یادداشت‌هایش را مرور می‌کرد به کلمه‌ی OOXXXOXOOX برخورد و نفهمید که این کلمه در اصل sand بوده یا pales. (شما هم امتحان کنید)

پس تصمیم گرفت رمزهای حروف را طوری تغییر دهد که هیچ دو ترتیب متفاوت از حروف (با معنی یا بی‌معنی) پس از رمز شدن به رشته‌ی یکسانی از علائم تبدیل نشود و در این کار موفق شد.

اگر در زبان مادری بارون $k$ حرف وجود داشته باشد، و طول رمزهای جدید مربوط به این حروف برابر$l_1$، $l_2$، … $l_k$ شده باشند، نشان دهید:

$$\frac1{2^{l_1}} + \frac1{2^{l_2}} + ⋯ + \frac1{2^{l_k}} ≤1$$


ابزار صفحه