Processing math: 100%

المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۱۳:تئوری:سوال ۶

سوال ۶

فرض کنید A{0,1}n و |A|=a و vA.(پس بردار v دارای n مولفه است که می‌توانیم آن‌ها را با اعداد {1,2,,n} شماره‌گذاری کنیم.) می‌گوییم مجموعه‌ی S از مولفه‌ها بردار v را تعیین می‌کند، اگر تو تنها اگر نتوانیم عضوی غیر از v در A پیدا کنیم که در تمام مولفه‌های عضو S مانند v باشد.

  1. ثابت کنید عضوی در A‌ هست که حداکثر با lg2a مولفه قابل تعیین است.
  2. ثابت کنید که می‌توان مجموعه‌ای از مولفه‌ها مثل S پیدا کرد که اولا |S|a1 و ثانیا S برای تمام اعضای A تعیین‌کننده باشد.

ابزار صفحه