با ۲ حرف و شرط اینکه هیچ واژه ای نتواند ابتدای واژهٔ دیگری باشد و به ترتیب ۳، ۱۰ و ۳۰ واژهٔ ۴، ۵ و ۶ حرفی داشته باشیم، حداکثر چند واژهٔ ۷ حرفی هست؟

Question

پرسش زیر پیرامون اصل ضرب برای المپیاد آورده‌شده‌است:

در زبانی تنها دو حرف وجود دارد. هیچ واژه‌ای از این زبان در آغاز واژۀ دیگری قرار نگرفته‌است. این زبان شامل سه واژۀ چهار حرفی، ۱۰ واژۀ پنج حرفی و ۳۰ واژۀ شش حرفی است. حداکثر چند واژۀ هفت حرفی داریم؟

پی‌نوشت: کتاب حاصل رو ۴ آورده ولی توضیح ننوشته، راه حل رو می‌خواهم.

Comments

@Zeinab589 مشخصات کتاب را هم در بخش مرجع بنویسید.

Answer 1

مهمترین نکته، عبارت «هیچ واژه‌ای از این زبان در آغاز واژۀ دیگری قرار نگرفته‌است» است. در نتیجه واژه‌های مقبول واژه‌های متفاوت از واژه‌هایی هستند که با تبدیلِ واژه‌های 4، 5 و 6 حرفی به واژهٔ 7 حرفی ساخته می‌شوند.

• تعداد کل واژه‌های 7 حرفی با استفاده از ۲ حرف برابر است با $2^7=128$.
• برای تبدیل یک واژهٔ 4 حرفی به یک واژهٔ 7 حرفی، سه حرف باید به جلوی آن اضافه کنیم. برای هر حرف 2 انتخاب داریم، پس به 8 طریق می‌توان به هر واژه 4 حرفی، ۳ حرف اضافه کرد. درنتیجه $3\times 8=24$ واژهٔ 7 حرفی به این روش می‌توان ساخت. به همین ترتیب $4\times 10=40$ واژهٔ 7 حرفی با گسترشِ واژه‌های 5 حرفی می‌توان ساخت. و در نهایت $2\times 30=60$ واژهٔ 7 حرفی از واژه‌های 6 حرفی می‌توان ساخت.
• در نتیجه با واژه های 4،5 و 6 حرفی تعداد $24+40+60=124$ واژهٔ 7 حرفیِ متفاوت می‌توان ساخت.

پس تعداد واژه‌های مورد پذیرش برابر است با:

$$128-124=4$$

بنابراین حداکثر 4 واژهٔ 7 حرفی در این زبان می‌تواند وجود داشته‌باشد.