المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۱۴

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

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

راهنمایی

ابتدا سوال را برای یک سطر حل کنید.

راهنمایی

تعداد حالاتی که حاصل ضرب اعداد یادداشت شده صفر نشود را بشمارید.

راهنمایی

برای اینکه حاصل ضرب صفر نشود، هیچ مقدار صفری نباید کنار سطری یادداشت شود.

راهنمایی

برای آنکه کنار سطری عدد صفر یادداشت نشود، ۱۵ حالت نوشتن اعداد در یک سطر دارد.

پاسخ

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

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

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

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


ابزار صفحه