المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۱۴

در هریک از خانه های یک جدول $۴\times ۴$ یکی از اعداد صفر یا یک را می نویسیم. سپس در کنار هر سطر حاصل جمع اعداد آن سطر را می نویسیم. سپس $t$ را برابر حاصل ضرب اعداد کنار سطرها قرار می دهیم. به ازای چند حالت از جدول اولیه مقدار $t$ برابر صفر می شود؟

  1. $۲^{۱۶} - ۱۵^۴$
  2. $۲^{۱۵} - ۱$
  3. $۲^{۱۵}$
  4. $۲^{۱۵} + ۱$
  5. $۲^{۱۶} - ۱۵$

پاسخ

گزینه‌ی ۱ درست است.

تنها در صورتی $t$ صفر خواهد شد که حداقل یکی از اعدادِ کنار سطرها صفر شود. برای محاسبه بهتر است که حالات متمم آن را محاسبه کنیم.

تعداد حالاتی که هیچ کدام از اعداد کنار سطرها صفر نشود، بدین معنی است که در هر سطر حداقل یک عدد ۱ داشته باشیم. یعنی تعداد حالات هر سطر برابر ۱۵ خواهد بود (همه‌ی حالات بجز اینکه همه‌ی خانه‌ها صفر باشند). پس کل حالات متمم برابر $15^4$ می‌شود و جواب مسئله‌ی اصلی برابر خواهد بود با:

$$2^{16}-15^4$$


ابزار صفحه