به محفل ریاضی ایرانیان خوش آمدید! لطفا برای استفاده از تمامی امکانات عضو شوید
سایت پرسش و پاسخ ریاضی
+1 امتیاز
296 بازدید
در دبیرستان توسط Zeinab589 (24 امتیاز)
ویرایش شده توسط AmirHosein

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

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

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

توسط AmirHosein (19,620 امتیاز)
+1
@Zeinab589 مشخصات کتاب را هم در بخش مرجع بنویسید.

1 پاسخ

+3 امتیاز
توسط amir7788 (2,972 امتیاز)
ویرایش شده توسط AmirHosein

مهمترین نکته، عبارت «هیچ واژه‌ای از این زبان در آغاز واژۀ دیگری قرار نگرفته‌است» است. در نتیجه واژه‌های مقبول واژه‌های متفاوت از واژه‌هایی هستند که با تبدیلِ واژه‌های 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 حرفی در این زبان می‌تواند وجود داشته‌باشد.


حمایت مالی

کانال تلگرام محفل ریاضی
امروز : تاریخ شمسی اینجا نمایش داده می‌شود
...