Processing math: 92%

المپدیا

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

ابزار کاربر

ابزار سایت


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

دنباله‌ی زیرمجموعه‌ها

مجموعه‌ی (|M|=k2)M داده شده است. ثابت کنید سه دنباله‌ی A,B,C از زیرمجموعه‌های M‌ وجود دارد به طوری که:

A=(A1,A2,,A2k)B=(B1,B2,,B2k)C=(C1,C2,,C2k)

هر دنباله، شامل دقیقا تمام زیرمجموعه‌های مجموعه‌ی M باشد.

i,1i2k:Ai,Bi,CiM.i,j,1i<j2k:AiAj,BiBj,CiCj.

و برای هر i:

i,1i2k:(AiBi)Ci=.

توضیح: اگر S,T دو مجموعه باشند؛ ST یا همان تفاضل متقارن S و T برابر است با:

S \bigtriangleup T= S\cup T – S \cap T.


ابزار صفحه