یک زبان از $n$ کلمه تشکیل شده است و هر کلمه از تعدادی حرف. مجموعه‌ی حروف ما {a,b,…,z} است و هر کدام از این حروف برای خود وزنی دارند. وزن حرف $a$ برابر $c_۱$٬ وزن حرف $b$ برابر $c_۲$ و به همین ترتیب٬ وزن حرف $z$ برابر $c_{۲۶}$ است. وزن هر کلمه هم برابر جمع وزن‌های حروف آن کلمه است و وزن یک زبان برابر جمع وزن‌های کلمات آن زبان. به عنوان مثال اگر $c_۱$٬ $c_۲$ و $c_۳$ به ترتیب برابر با ۲٬۱ و ۳ باشند. وزن زبان {$acb,abba$} برابر است با ۱۲ = (۱+۲+۲+۱) + (۲+۳+۱).

یک کلمه «پیشوند» یک کلمه‌ی دیگر است اگر و تنها اگر در ابتدای آن ظاهر شده باشد. مثلاً abzd پیشوند abzdsdf است. به همین شکل٬ یک کلمه «پسوند» یک کلمه‌ی دیگر است اگر و فقط اگر در انتهای آن ظاهر شده باشد. مثلاً sjf پسوند hgsjf است.

یک زبان را «پیشوند-آزاد» می‌گوییم اگر و فقط اگر هیچ کلمه‌ای در آن پیشوند دیگری نباشد٬ و یک زبان را «پسوند-آزاد» می‌گوییم اگر و فقط اگر هیچ کلمه‌ای در آن پسوند دیگری نباشد.

فرض کنید وزن کم‌وزن‌ترین زبانِ $n$ کلمه‌ایِ پیشوند-آزاد برابر $X$ است. ثابت کنید که وزن کم‌وزن‌ترین زبانِ $n$ کلمه‌ایِ که هم پیشوند-آزاد باشد و هم پسوند-آزاد حداکثر $۲X$ است.

• سوال بعد
• سوال قبل