======سوال ۱۹======

فرض کنید آرایه‌ای به طول ۱۰۰۰ از بیت‌های ۰ و ۱ داریم. می‌گوییم این آرایه «۰- غالب» است اگر دست کم ٪۹۰ اعداد آن ۰ باشد (و در نتیجه حداکثر ٪۱۰ آن ۱ باشد). هم‌چنین آرایه «۱- غالب» است اگر دست کم ٪۹۰ اعداد آن ۱ باشد (و در نتیجه حداکثر ٪۱۰ آن ۰ باشد). می‌دانیم که آرایه یا ۰- غالب است یا ۱- غالب٬ ولی نمی‌دانیم کدام‌یک. چندتا از درایه‌های این آرایه را باید بررسی کنیم تا به طور قطع بتوانیم بگوییم که آرایه ۰- غالب است یا ۱- غالب؟

  - ۱۹۱
  - ۲۰۱
  - ۲۱۰
  - ۵۰۱
  - ۹۰۱


<پاسخ>
گزینه (۲) درست است.


اگر آرایه صفر غالب باشد حداکثر ۱۰٪ آن یعنی ۱۰۰ تا یک و اگر ۱-غالب باشد حداکثر ۱۰۰ تا صفر دارد. حال چون می‌دانیم آرایه یا ۰-غالب است و یا ۱-غالب اگر در بررسی‌مان از هرکدام از صفرها یا یک‌ها بیش‌تر از ۱۰۰ تا داشته باشیم می‌توانیم با قطعیت بگوییم که آن غالب است. پس در بدترین شرایط $100+100+1$ یعنی ۲۰۱ بررسی لازم داریم.

</پاسخ>
  * [[سوال ۲۰|سوال بعد]]
  * [[سوال ۱۸|سوال قبل]]