المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله‌ی دوم:دوره‌ی ۱۱:سوال ۸

استان‌ها

کشوری شامل دو استان است و هر استان از $2^n$ شهر تشکیل شده است. به هر شهر یک کد $n+1$ رقمی با ارقام صفر و یک اختصاص داده‌ایم، به طوری که کد هر شهر از استان اول شامل تعداد فردی رقم یک و کد هر شهر از استان دوم شامل تعداد زوجی رقم یک است ونیز کد هیچ دو شهری یکسان نیست.

در این کشور بین هر دو شهر که کد آن‌ها دقیقا در یک رقم تفاوت دارد، یک خط تلفن مستقیم کشیده شده است. اگر مجموعه‌ی $A$ از تعدادی از شهرهای این کشور تشکیل شده باشد، $F(A)$ مجموعه‌ی شهرهایی است که بین هر کدام از آن‌ها و تعداد فردی از شهرهای مجموعه‌ی $A$‌ مستقیما خط تلفن موجود باشد.

ثابت کنید اگر $n$ زوج باشد و تمام اعضای $A$‌ را از استان اول انتخاب کنیم، آن‌گاه $F(F(A))=A$.


ابزار صفحه